二叉查找树

  1 #include <iostream>
  2 #include <crtdbg.h>
  3 using namespace std;
  4 /*二叉查找树*/
  5 /*实现中假设关键元素互不相同*/
  6 typedef int DataType;
  7 
  8 struct TreeNode
  9 {
 10      TreeNode()
 11      {
 12         right = NULL;
 13         left  = NULL;
 14      }
 15      DataType data;
 16      TreeNode *right;
 17      TreeNode *left;
 18 };
 19 
 20 struct BiTree
 21 {
 22     TreeNode *root;
 23 
 24     BiTree()
 25     {
 26         root=NULL;
 27     }
 28     ~BiTree()
 29     {
 30         Destroy(root);
 31         root = NULL;
 32     }
 33     void Destroy(TreeNode *p)
 34     {
 35         if (p == NULL) return;
 36 
 37         Destroy(p->left);
 38         Destroy(p->right);
 39         delete p;
 40     }
 41     /*先确定父结点位置，在确定子节点位置*/
 42     void Insert(DataType data)
 43     {
 44         TreeNode *pTemp = NULL;
 45         TreeNode *p = root;
 46         while(p != NULL)
 47         {
 48              pTemp = p;
 49             if (data < p->data)
 50             {
 51                 p = p->left;
 52             }
 53             else
 54             {
 55                 p = p->right;
 56             }
 57         }
 58         TreeNode *pNew = new TreeNode;
 59         pNew->data = data;
 60         if (pTemp == NULL)
 61         {
 62             root = pNew;
 63         }
 64         else
 65         {
 66             if (data < pTemp->data)
 67             {
 68                 pTemp->left = pNew;
 69             }
 70             else
 71             {
 72                 pTemp->right = pNew;
 73             }
 74         }
 75     }
 76     /*考虑3种情况，要删除的结点有两子节点，只有一个子节点，没有子节点*/
 77     void Delete(DataType data)
 78     {
 79         TreeNode *p = Find(data);
 80         TreeNode *parent = GetParent(root,p);
 81 
 82         if (p->left == NULL && p->right == NULL)/*子结点都为空*/
 83         {
 84             if (parent !=NULL)
 85             {
 86                 if (parent->left == p)
 87                 {
 88                     parent->left = NULL;
 89                 }
 90                 else
 91                 {
 92                     parent->right = NULL;
 93                 }
 94             }
 95             else
 96             {
 97                 root = NULL;
 98             }
 99             delete p;
100         }
101         else if (p->left == NULL || p->right == NULL)/*只有一个子结点为空*/
102         {
103             if (parent != NULL)
104             {
105                 if (p->left != NULL)
106                 {
107                     if (parent->left == p)
108                     {
109                         parent->left = p->left;
110                     }
111                     else
112                     {
113                         parent->right = p->left;
114                     }
115                 }
116                 else 
117                 {
118                     if (parent->left == p)
119                     {
120                         parent->left = p->right;
121                     }
122                     else
123                     {
124                         parent->right = p->right;
125                     }
126                 }
127                 delete p;
128                 p = NULL;
129             }
130             else/*要删除的结点为根结点*/
131             {
132                 if (p->left != NULL)
133                 {
134                     p->data = p->left->data;
135                     delete p->left;
136                     p->left = NULL;
137                 }
138                 else
139                 {
140                     p->data = p->right->data;
141                     delete p->right;
142                     p->right = NULL;
143                 }
144             }
145         }
146         else/*子结点都不为空*/
147         {
148             TreeNode *pAfter = TreeAfter(p);
149             TreeNode *pAfterParent = GetParent(root, pAfter);
150 
151             if (pAfterParent != NULL)/*不为头结点*/
152             {
153                 if (pAfter->right != NULL)/* p的后继结点不可能有左子结点*/
154                 {
155                     if (pAfterParent->left == pAfter)
156                     {
157                         pAfterParent->left = pAfter->right;
158                     }
159                     else
160                     {
161                         pAfterParent->right = pAfter->right;
162                     }
163                 }
164                 else
165                 {
166                     if (pAfterParent->left == pAfter)
167                     {
168                         pAfterParent->left = NULL;
169                     }
170                     else
171                     {
172                         pAfterParent->right = NULL;
173                     }
174                 }
175                 p->data = pAfter->data;
176             }
177             else
178             {
179                 p->data = pAfter->data;
180                 p->right = NULL;
181             }
182             delete pAfter;
183         }
184     }
185     /*非线性结构转换成线性结构（内存是线性的） 有3种方法 先序 中序 后序*/
186     /*中序遍历*/
187     void InOrderTree(TreeNode *p)
188     {
189         if (p == NULL) return ;
190         
191         InOrderTree(p->left);
192         cout << p->data << endl;
193         InOrderTree(p->right);
194     }
195     /*递归版本*/
196     TreeNode* Search(TreeNode *p, DataType key)
197     {
198         if (p == NULL || p->data == key)
199             return p;
200 
201         if (key < p->data)
202         {
203             return Search(p->left, key);
204         }
205         else
206         {
207             return Search(p->right, key);
208         }
209     }
210     /*非递归版本*/
211     TreeNode* Find(DataType key)
212     {
213         TreeNode *p = root;
214         while(p != NULL && p->data != key)
215         {
216             if (key < p->data)
217             {
218                 p = p->left;
219             }
220             else
221             {
222                 p = p->right;
223             }
224         }
225         return p;
226     }
227     /*寻找最小值*/
228     TreeNode* Minimum(TreeNode *p)
229     {
230         TreeNode *pTemp = p;
231         while(pTemp != NULL)
232         {
233             p = pTemp;
234             pTemp = p->left;
235         }
236         return p;
237     }
238     /*寻找最大值*/
239     TreeNode* Maximum(TreeNode *p)
240     {
241         TreeNode *pTemp = p;
242         while(pTemp != NULL)
243         {
244             p = pTemp;
245             pTemp = p->right;
246         }
247         return p;
248     }
249     /*获取父节点*/
250     TreeNode * GetParent(TreeNode *parent, TreeNode *p)
251     {
252         if (parent == NULL || parent == p)
253             return NULL;
254         if (parent->left == p || parent->right == p)
255         {
256             return parent;
257         }
258         TreeNode *ret = GetParent(parent->left, p);
259         if(ret)
260             return ret;
261         return GetParent(parent->right, p);
262     }
263     /*寻找前趋(关键字都不相同) x的前趋为小于key[x]的 最大关键值
264       考虑两种情况
265       1 如果结点x的左子树非空，则x的前趋为左子树中的右结点
266       2 如果结点x的左子树为空，则x的前趋为x的祖先结点，即x的父节点且父结点为其父结点的右子结点    
267    */
268     TreeNode *TreePre(TreeNode *p)
269     {
270         if (p->left)
271         {
272             return Maximum(p->left);
273         }
274         TreeNode *parent = GetParent(root,p);
275         while(parent != NULL && p == parent->left)
276         {
277             p = parent;
278             parent = GetParent(root,parent);
279         }
280         return parent;
281     }
282     /*寻找后继(关键字都不相同) x的后继为大于key[x]的 最小关键值
283       考虑两种情况 
284       1 如果结点x的右子树非空，则x的后继为右子树中的左结点
285       2 如果结点x的右子树为空，则x的后继为x的祖先结点，即x的父节点且父结点为其父结点的左子结点          
286     */
287     TreeNode *TreeAfter(TreeNode *p)
288     {
289         if (p->right)
290         {
291             return Minimum(p->right);
292         }
293         TreeNode *parent = GetParent(root,p);
294         while(parent != NULL && p == parent->right)
295         {
296             p = parent;
297             parent = GetParent(root,parent);
298         }
299         return parent;
300     }
301 };
302 void main()
303 {
304     _CrtSetDbgFlag(_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF);
305 
306     BiTree biTree;
307     /*测试插入*/
308     biTree.Insert(15);
309     biTree.Insert(6);
310     biTree.Insert(3);
311     biTree.Insert(7);
312     biTree.Insert(2);
313     biTree.Insert(4);
314     biTree.Insert(13);
315     biTree.Insert(9);
316     biTree.Insert(18);
317     biTree.Insert(17);
318     biTree.Insert(20);
319     biTree.InOrderTree(biTree.root);
320 
321     /*测试最大最小*/
322     cout << endl;
323     TreeNode * p = NULL;
324     p = biTree.Maximum(biTree.root);
325     cout << p->data << endl;
326     p = biTree.Minimum(biTree.root);
327     cout << p->data << endl;
328 
329     /*测试两种find 以及获取父节点GetParent*/
330     cout <<endl;
331     TreeNode *p2 = NULL;
332     p = biTree.Find(17);
333     if (p != NULL)
334     {
335         p2 = biTree.GetParent(biTree.root, p);
336         cout << p2->data << endl;
337     }
338     p = biTree.Find(20);
339     if (p != NULL)
340     {
341         cout << biTree.GetParent(biTree.root, p)->data << endl;
342     }
343 
344     /*测试 9前趋、 13后继*/
345     cout <<endl;
346     TreeNode *p3 = NULL;
347     p3 = biTree.TreePre(biTree.Find(9));
348     if ( p3 != NULL)
349     {
350         cout << p3->data << endl;
351     }
352     p3 = biTree.TreeAfter(biTree.Find(13));
353     if ( p3 != NULL)
354     {
355         cout << p3->data << endl;
356     }
357     
358     /*测试 删除 3中情况*/
359     cout <<endl;
360     biTree.Delete(6);    /*有两结点*/
361     biTree.Delete(13);  /*只有一个子节点*/
362     biTree.Delete(20);  /*没有子节点*/
363     biTree.InOrderTree(biTree.root);
364 
365     system("pause");
366 }