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

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

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

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