1、序

     詳細(xì)實(shí)現(xiàn)了二叉查找樹的各種操作：插入結(jié)點(diǎn)、構(gòu)造二叉樹、刪除結(jié)點(diǎn)、查找、  查找最大值、查找最小值、查找指定結(jié)點(diǎn)的前驅(qū)和后繼

2、二叉查找樹簡介

     它或者是一棵空樹；或者是具有下列性質(zhì)的二叉樹： （1）若左子樹不空，則左子樹上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值； （2）若右子樹不空，則右子樹上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值； （3）左、右子樹也分別為二叉排序樹

3、二叉查找樹的各種操作

        此處給出代碼，注釋非常詳細(xì)，具體操作請參考代碼：

[cpp] view plaincopy?

1. /************************************************************************* 
2.   這是一個(gè)二叉查找樹，實(shí)現(xiàn)了以下操作：插入結(jié)點(diǎn)、構(gòu)造二叉樹、刪除結(jié)點(diǎn)、查找、 
3.   查找最大值、查找最小值、查找指定結(jié)點(diǎn)的前驅(qū)和后繼。上述所有操作時(shí)間復(fù)雜度 
4.   均為o(h),其中h是樹的高度 
5.   注釋很詳細(xì)，具體內(nèi)容就看代碼吧 
6. *************************************************************************/  
7.   
8. #include<stdio.h>  
9. #include<stdlib.h>  
10.   
11. //二叉查找樹結(jié)點(diǎn)描述  
12. typedef int KeyType;  
13. typedef struct Node  
14. {  
15.     KeyType key;          //關(guān)鍵字  
16.     struct Node * left;   //左孩子指針  
17.     struct Node * right;  //右孩子指針  
18.     struct Node * parent; //指向父節(jié)點(diǎn)指針  
19. }Node,*PNode;  
20.   
21. //往二叉查找樹中插入結(jié)點(diǎn)  
22. //插入的話，可能要改變根結(jié)點(diǎn)的地址，所以傳的是二級(jí)指針  
23. void inseart(PNode * root,KeyType key)  
24. {  
25.     //初始化插入結(jié)點(diǎn)  
26.     PNode p=(PNode)malloc(sizeof(Node));  
27.     p->key=key;  
28.     p->left=p->right=p->parent=NULL;  
29.     //空樹時(shí)，直接作為根結(jié)點(diǎn)  
30.     if((*root)==NULL){  
31.         *root=p;  
32.         return;  
33.     }  
34.     //插入到當(dāng)前結(jié)點(diǎn)（*root）的左孩子  
35.     if((*root)->left == NULL && (*root)->key > key){  
36.         p->parent=(*root);  
37.         (*root)->left=p;  
38.         return;  
39.     }  
40.     //插入到當(dāng)前結(jié)點(diǎn)（*root）的右孩子  
41.     if((*root)->right == NULL && (*root)->key < key){  
42.         p->parent=(*root);  
43.         (*root)->right=p;  
44.         return;  
45.     }  
46.     if((*root)->key > key)  
47.         inseart(&(*root)->left,key);  
48.     else if((*root)->key < key)  
49.         inseart(&(*root)->right,key);  
50.     else  
51.         return;  
52. }  
53.   
54. //查找元素,找到返回關(guān)鍵字的結(jié)點(diǎn)指針，沒找到返回NULL  
55. PNode search(PNode root,KeyType key)  
56. {  
57.     if(root == NULL)  
58.         return NULL;  
59.     if(key > root->key) //查找右子樹  
60.         return search(root->right,key);  
61.     else if(key < root->key) //查找左子樹  
62.         return search(root->left,key);  
63.     else  
64.         return root;  
65. }  
66.   
67. //查找最小關(guān)鍵字,空樹時(shí)返回NULL  
68. PNode searchMin(PNode root)  
69. {  
70.     if(root == NULL)  
71.         return NULL;  
72.     if(root->left == NULL)  
73.         return root;  
74.     else  //一直往左孩子找，直到?jīng)]有左孩子的結(jié)點(diǎn)  
75.         return searchMin(root->left);  
76. }  
77.   
78. //查找最大關(guān)鍵字,空樹時(shí)返回NULL  
79. PNode searchMax(PNode root)  
80. {  
81.     if(root == NULL)  
82.         return NULL;  
83.     if(root->right == NULL)  
84.         return root;  
85.     else  //一直往右孩子找，直到?jīng)]有右孩子的結(jié)點(diǎn)  
86.         return searchMax(root->right);  
87. }  
88.   
89. //查找某個(gè)結(jié)點(diǎn)的前驅(qū)  
90. PNode searchPredecessor(PNode p)  
91. {  
92.     //空樹  
93.     if(p==NULL)  
94.         return p;  
95.     //有左子樹、左子樹中最大的那個(gè)  
96.     if(p->left)  
97.         return searchMax(p->left);  
98.     //無左子樹,查找某個(gè)結(jié)點(diǎn)的右子樹遍歷完了  
99.     else{  
100.         if(p->parent == NULL)  
101.             return NULL;  
102.         //向上尋找前驅(qū)  
103.         while(p){  
104.             if(p->parent->right == p)  
105.                 break;  
106.             p=p->parent;  
107.         }  
108.         return p->parent;  
109.     }  
110. }  
111.   
112. //查找某個(gè)結(jié)點(diǎn)的后繼  
113. PNode searchSuccessor(PNode p)  
114. {  
115.     //空樹  
116.     if(p==NULL)  
117.         return p;  
118.     //有右子樹、右子樹中最小的那個(gè)  
119.     if(p->right)  
120.         return searchMin(p->right);  
121.     //無右子樹,查找某個(gè)結(jié)點(diǎn)的左子樹遍歷完了  
122.     else{  
123.         if(p->parent == NULL)  
124.             return NULL;  
125.         //向上尋找后繼  
126.         while(p){  
127.             if(p->parent->left == p)  
128.                 break;  
129.             p=p->parent;  
130.         }  
131.         return p->parent;  
132.     }  
133. }  
134.   
135. //根據(jù)關(guān)鍵字刪除某個(gè)結(jié)點(diǎn),刪除成功返回1,否則返回0  
136. //如果把根結(jié)點(diǎn)刪掉，那么要改變根結(jié)點(diǎn)的地址，所以傳二級(jí)指針  
137. int deleteNode(PNode* root,KeyType key)  
138. {  
139.     PNode q;  
140.     //查找到要?jiǎng)h除的結(jié)點(diǎn)  
141.     PNode p=search(*root,key);  
142.     KeyType temp;    //暫存后繼結(jié)點(diǎn)的值  
143.     //沒查到此關(guān)鍵字  
144.     if(!p)  
145.         return 0;  
146.     //1.被刪結(jié)點(diǎn)是葉子結(jié)點(diǎn)，直接刪除  
147.     if(p->left == NULL && p->right == NULL){  
148.         //只有一個(gè)元素，刪完之后變成一顆空樹  
149.         if(p->parent == NULL){  
150.             free(p);  
151.             (*root)=NULL;  
152.         }else{  
153.             //刪除的結(jié)點(diǎn)是父節(jié)點(diǎn)的左孩子  
154.             if(p->parent->left == p)  
155.                 p->parent->left=NULL;  
156.             else  //刪除的結(jié)點(diǎn)是父節(jié)點(diǎn)的右孩子  
157.                 p->parent->right=NULL;  
158.             free(p);  
159.         }  
160.     }  
161.   
162.     //2.被刪結(jié)點(diǎn)只有左子樹  
163.     else if(p->left && !(p->right)){  
164.         p->left->parent=p->parent;  
165.         //如果刪除是父結(jié)點(diǎn)，要改變父節(jié)點(diǎn)指針  
166.         if(p->parent == NULL)  
167.             *root=p->left;  
168.         //刪除的結(jié)點(diǎn)是父節(jié)點(diǎn)的左孩子  
169.         else if(p->parent->left == p)  
170.             p->parent->left=p->left;  
171.         else //刪除的結(jié)點(diǎn)是父節(jié)點(diǎn)的右孩子  
172.             p->parent->right=p->left;  
173.         free(p);  
174.     }  
175.     //3.被刪結(jié)點(diǎn)只有右孩子  
176.     else if(p->right && !(p->left)){  
177.         p->right->parent=p->parent;  
178.         //如果刪除是父結(jié)點(diǎn)，要改變父節(jié)點(diǎn)指針  
179.         if(p->parent == NULL)  
180.             *root=p->right;  
181.         //刪除的結(jié)點(diǎn)是父節(jié)點(diǎn)的左孩子  
182.         else if(p->parent->left == p)  
183.             p->parent->left=p->right;  
184.         else //刪除的結(jié)點(diǎn)是父節(jié)點(diǎn)的右孩子  
185.             p->parent->right=p->right;  
186.         free(p);  
187.     }  
188.     //4.被刪除的結(jié)點(diǎn)既有左孩子，又有右孩子  
189.     //該結(jié)點(diǎn)的后繼結(jié)點(diǎn)肯定無左子樹(參考上面查找后繼結(jié)點(diǎn)函數(shù))  
190.     //刪掉后繼結(jié)點(diǎn),后繼結(jié)點(diǎn)的值代替該結(jié)點(diǎn)  
191.     else{  
192.         //找到要?jiǎng)h除結(jié)點(diǎn)的后繼  
193.         q=searchSuccessor(p);  
194.         temp=q->key;  
195.         //刪除后繼結(jié)點(diǎn)  
196.         deleteNode(root,q->key);  
197.         p->key=temp;  
198.     }  
199.     return 1;  
200. }  
201.   
202. //創(chuàng)建一棵二叉查找樹  
203. void create(PNode* root,KeyType *keyArray,int length)  
204. {  
205.     int i;  
206.     //逐個(gè)結(jié)點(diǎn)插入二叉樹中  
207.     for(i=0;i<length;i++)  
208.         inseart(root,keyArray[i]);  
209. }  
210.   
211. int main(void)  
212. {  
213.     int i;  
214.     PNode root=NULL;  
215.     KeyType nodeArray[11]={15,6,18,3,7,17,20,2,4,13,9};  
216.     create(&root,nodeArray,11);  
217.     for(i=0;i<2;i++)  
218.         deleteNode(&root,nodeArray[i]);  
219.     printf("%d\n",searchPredecessor(root)->key);  
220.     printf("%d\n",searchSuccessor(root)->key);  
221.     printf("%d\n",searchMin(root)->key);  
222.     printf("%d\n",searchMax(root)->key);  
223.     printf("%d\n",search(root,13)->key);  
224.     return 0;  
225. }  

4、附錄

        參考書籍     《算法導(dǎo)論》