二叉排序樹思想及C語言實作

轉自：

http://blog.chinaunix.net/uid-22663647-id-1771796.html 1.二叉排序樹的定義 　　二叉排序樹(Binary

Sort Tree)又稱二叉查找(搜尋)樹(Binary Search Tree)。其定義為：二叉排序樹或者是空樹，或者是滿足如下性質的二叉樹：

①若它的左子樹非空，則左子樹上所有結點的值均小于根結點的值；②若它的右子樹非空，則右子樹上所有結點的值均大于根結點的值；③左、右子樹本身又各是一棵二叉排序樹。

　　上述性質簡稱二叉排序樹性質(BST性質)，故二叉排序樹實際上是滿足BST性質的二叉樹。2.二叉排序樹的性質

按中序周遊二叉排序樹，所得到的中序周遊序列是一個遞增有序序列。3.二叉排序樹的插入 在二叉排序樹中插入新結點，要保證插入後的二叉樹仍符合二叉排序樹的定義。

　　 插入過程： 若二叉排序樹為空，則待插入結點*S作為根結點插入到空樹中； 　　

當非空時，将待插結點關鍵字S->key和樹根關鍵字t->key進行比較，若s->key =

t->key,則無須插入，若s->key< t->key,則插入到根的左子樹中，若s->key>

t->key,則插入到根的右子樹中。而子樹中的插入過程和在樹中的插入過程相同，如此進行下去，直到把結點*s作為一個新的樹葉插入到二叉排序樹中，或者直到發現樹已有相同關鍵字的結點為止。

4.二叉排序樹的查找 假定二叉排序樹的根結點指針為 root ，給定的關鍵字值為 K ，則查找算法可描述為： 　　① 置初值： q ＝ root ； 　　②

如果 K ＝ q －＞ key ，則查找成功，算法結束； 　　③ 否則，如果 K ＜ q －＞ key ，而且 q 的左子樹非空，則将 q 的左子樹根送 q

，轉步驟②；否則，查找失敗，結束算法； 　　④ 否則，如果 K ＞ q －＞ key ，而且 q 的右子樹非空，則将 q 的右子樹根送 q

，轉步驟②；否則，查找失敗，算法結束。5.二叉排序樹的删除 假設被删結點是*p，其雙親是*f，不失一般性，設*p是*f的左孩子，下面分三種情況讨論： 　　

⑴ 若結點*p是葉子結點，則隻需修改其雙親結點*f的指針即可。 　　 ⑵ 若結點*p隻有左子樹PL或者隻有右子樹PR，則隻要使PL或PR

成為其雙親結點的左子樹即可。 　　 ⑶

若結點*p的左、右子樹均非空，先找到*p的中序前趨(或後繼)結點*s（注意*s是*p的左子樹中的最右下的結點，它的右鍊域為空），然後有兩種做法：①

令*p的左子樹直接鍊到*p的雙親結點*f的左鍊上,而*p的右子樹鍊到*p的中序前趨結點*s的右鍊上。②

以*p的中序前趨結點*s代替*p（即把*s的資料複制到*p中），将*s的左子樹鍊到*s的雙親結點*q的左（或右）鍊上。 代碼實作：

bi_search_tree.h #ifndef __BI_SEARCH_TREE_H__ #define __BI_SEARCH_TREE_H__ /*

*說明：定義了二叉查找樹的相關資料結構和幾個基本操作 *作者：leaf *時間：2010-09-08 15:55:37 */ typedef int

datatype; struct bi_search_tree { datatype key; struct bi_search_tree

*left,*right; }; typedef struct bi_search_tree bst_tree; /*插入操作，value是待插入的值*/

bst_tree *bst_insert(bst_tree *root, datatype value); /*查找，找到傳回1，否則，傳回0*/ int

bst_search(bst_tree *root, datatype value); /*删除節點值為value的節點，成功傳回1，否則，傳回0*/ int

bst_delete(bst_tree *root, datatype value); /*中序輸出bst樹*/void bst_print(bst_tree

*root); #endif bi_search_tree.c #include #include #include

"bi_search_tree.h" /*插入操作，value是待插入的值*/bst_tree *bst_insert(bst_tree *root,

datatype value) { bst_tree *parent, *node, *child; /*樹為空，建立根節點*/

if(root == NULL) { root = (bst_tree *)malloc(sizeof(bst_tree));

root->key = value; root->left = NULL; root->right = NULL;

return root; } parent = root; /*記錄下根節點的位置*/ node = root;

while(node != NULL) { /*待插入資料已經存在，則傳回*/ if(node->key ==

value) return root; else { parent = node;

/*若小于節點的值，則檢視節點的左孩子，否則，檢視右孩子*/ if(node->key < value)

node = node->right; else node =

node->left; } } child = (bst_tree *)malloc(sizeof(bst_tree));

child->key = value; child->left = NULL; child->right = NULL;

if(value > parent->key) parent->right = child; else

parent->left = child; return root; } /*查找，找到傳回1，否則，傳回0*/ int

bst_search(bst_tree *root, datatype value) { bst_tree *p; p = root;

if(p == NULL) return 0; if(p->key == value) return 1;

else if(p->key > value) return bst_search(p->left, value);

else return bst_search(p->right, value); } /*删除節點值為value的節點*/int

bst_delete(bst_tree *root, datatype value) { bst_tree *p, *pre=NULL, *mid;

p = root; if(root == NULL) return 0; /*找到該節點*/

while((p != NULL) && (p->key != value)) { pre = p;

if(p->key < value) { p = p->right; }

else p = p->left; } if(p == NULL) return 0;

/*至少有一個子節點為空*/ if( (p->left == NULL) || (p->right == NULL) ) {

if( pre->left == p ) { pre->left = ( (p->left ==

NULL) ? p->right : p->left ); } else

pre->right = ( (p->left == NULL) ? p->right : p->left );

free(p); /*釋放節點*/ } else { /*删除的節點有2個子女*/ mid =

p->right; pre = p; /*尋找中序的第一個節點*/ while(mid->left !=

NULL) { pre = mid; mid = mid->left; }

/*移花接木，直接指派，避免交換節點*/ p->key = mid->key;

/*将mid節點的子節點作為pre的子節點，并将mid所指向的節點删除*/ if(pre->right == mid)

pre->right = mid->right; else pre->left =

mid->right; free(mid); } return 1; } /*中序輸出bst樹*/void

bst_print(bst_tree *root) { if(root == NULL) return;

bst_print(root->left); printf(" %d ", root->key);

bst_print(root->right); }測試代碼：main.c #include #include

"bi_search_tree.h" int main() { int a[10] = {5,4,2,8,7,1,9,3,6,10}; int

i=0; bst_tree *root=NULL; for(i=0; i<10; i++) root =

bst_insert(root, a[i]); bst_delete(root, 5); bst_print(root);

printf("\n%d %s\n", root->key, bst_search(root, 10) ? "yes":"no"); return

0; }