《數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言描述）（第2版）》教學(xué)課件7-04二叉排序樹(shù)及其描述

1、2016數(shù)據(jù)結(jié)構(gòu)Data structure講授：賀寧 二叉排序樹(shù)及其描述常州信息職業(yè)技術(shù)學(xué)院0203二叉排序樹(shù) 當(dāng)用線性表作為表的組織形式時(shí)，可以有三種查找法。其中以二分查找效率最高。但由于二分查找要求表中結(jié)點(diǎn)按關(guān)鍵字有序，且不能用鏈表作存儲(chǔ)結(jié)構(gòu)，因此，當(dāng)表的插入或刪除操作頻繁時(shí)，為維護(hù)表的有序性，必須移動(dòng)表中很多結(jié)點(diǎn)。這種由移動(dòng)結(jié)點(diǎn)引起的額外時(shí)間開(kāi)銷(xiāo)，就會(huì)抵消二分查找的優(yōu)點(diǎn)。因此，二分查找只適用于順序表的靜態(tài)查找。若要對(duì)動(dòng)態(tài)查找表進(jìn)行高效率的查找，可采用二叉排序樹(shù)作為存儲(chǔ)結(jié)構(gòu)。下面將討論在二叉排序樹(shù)上進(jìn)行查找和修改操作的方法。04二叉排序樹(shù) 二叉排序樹(shù)（Binary Sort Tree）又

2、稱二叉查找搜索樹(shù)（Binary Search Tree）。二叉排序樹(shù)或者是空樹(shù)，或者是滿足如下性質(zhì)的二叉樹(shù)：（1）若它的左子樹(shù)非空，則左子樹(shù)上所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值；（2）若它的右子樹(shù)非空，則右子樹(shù)上所有結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值；（3）左、右子樹(shù)本身又各是一棵二叉排序樹(shù)。 上述性質(zhì)簡(jiǎn)稱二叉排序樹(shù)性質(zhì)（BST性質(zhì)），故二叉排序樹(shù)實(shí)際上是滿足BST性質(zhì)的二叉樹(shù)。1、定義05二叉排序樹(shù)（1）二叉排序樹(shù)中任一結(jié)點(diǎn)的關(guān)鍵字，必大于其左子樹(shù)所有結(jié)點(diǎn)的關(guān)鍵字，小于右子樹(shù)所有結(jié)點(diǎn)的關(guān)鍵字。（2）二叉排序樹(shù)中，各結(jié)點(diǎn)關(guān)鍵字是唯一的，即除該結(jié)點(diǎn)的關(guān)鍵字外，其它結(jié)點(diǎn)的關(guān)鍵字均不等于該結(jié)點(diǎn)的關(guān)鍵字。（3）按中序

3、遍歷該樹(shù)所得到的中序序列是一個(gè)遞增有序序列。2、特點(diǎn)06二叉排序樹(shù)2、特點(diǎn)(a)532478(b)258374上圖所示的兩棵二叉樹(shù)均是二叉排序樹(shù)，滿足BST性質(zhì)，它們的中序序列均為有序序列2，3，4，5，7，8。均滿足三個(gè)特點(diǎn)07二叉排序樹(shù)3、二叉排序樹(shù)的結(jié)構(gòu)描述typedef int KeyType;/關(guān)鍵字類(lèi)型定義typedef char OtherdataType;/非關(guān)鍵字字段類(lèi)型定義typedef struct node /結(jié)點(diǎn)類(lèi)型KeyType key;/關(guān)鍵字域OtherdataType data;/其它數(shù)據(jù)域struct node *lchild,*rchild;/左右孩子指針BSTNode