當用線性表作為表的組織形式時可以有三種查找法其中以二分查找效率最高但由於二分查找要求表中結點按關鍵字有序且不能用鏈表作存儲結構因此當表的插入或刪除操作頻繁時為維護表的有序性勢必要移動表中很多結點這種由移動結點引起的額外時間開銷就會抵消二分查找的優點也就是說二分查找只適用於靜態查找表若要對動態查找表進行高效率的查找可采用下面介紹的幾種特殊的二叉樹或樹作為表的組織形式不妨將它們統稱為樹表下面將分別討論在這些樹表上進行查找和修改操作的方法
二叉排序樹
二叉排序樹的定義
二叉排序樹(Binary Sort Tree)又稱二叉查找(搜索)樹(Binary Search Tree)其定義為二叉排序樹或者是空樹或者是滿足
如下性質的二叉樹
①若它的左子樹非空則左子樹上所有結點的值均小於根結點的值;
②若它的右子樹非空則右子樹上所有結點的值均大於根結點的值;
③左右子樹本身又各是一棵二叉排序樹
上述性質簡稱二叉排序樹性質(BST性質)故二叉排序樹實際上是滿足BST性質的二叉樹
二叉排序樹的特點
由BST性質可得
() 二叉排序樹中任一結點x其左(右)子樹中任一結點y(若存在)的關鍵字必小(大)於x的關鍵字
() 二叉排序樹中各結點關鍵字是惟一的
注意
實際應用中不能保證被查找的數據集中各元素的關鍵字互不相同所以可將二叉排序樹定義中BST性質()裡的小於改為大於等於或將BST性質()裡的大於改為小於等於甚至可同時修改這兩個性質
() 按中序遍歷該樹所得到的中序序列是一個遞增有序序列
【例】下圖所示的兩棵樹均是二叉排序樹它們的中序序列均為有序序列
二叉排序樹的存儲結構
typedef int KeyType; //假定關鍵字類型為整數
typedef struct node { //結點類型
KeyType key; //關鍵字項
InfoType otherinfo; //其它數據域InfoType視應用情況而定下面不處理它
struct node *lchild*rchild; //左右孩子指針
} BSTNode;
typedef BSTNode *BSTree; //BSTree是二叉排序樹的類型
From:http://tw.wingwit.com/Article/program/sjjg/201311/23832.html
