二叉查找树c语言实现

1. typedef int ElementType;
   
2. 
   
3. #ifndef _SEARCH_TREE_
   
4. #define _SEARCH_TREE_
   
5. 
   
6. struct TreeNode;
   
7. typedef TreeNode *Position;
   
8. typedef TreeNode *SearchTree;
   
9. 
   
10. SearchTree MakeEmpty( SearchTree T );           //释放树中的所有元素
    
11. Position Find( ElementType X, SearchTree T );   
    
12. Position FindMin( SearchTree T );              //查找最小值
    
13. Position FindMax( SearchTree T );
    
14. SearchTree Insert( ElementType X, SearchTree T );
    
15. SearchTree Delete( ElementType X, SearchTree T );
    
16. ElementType Retrieve( Position P );          //提取该位置上关键字
    
17. void PrintTree( SearchTree T );              //先序输出
    
18. 
    
19. #endif

1. #include "searchTree.h"
   
2. #include <stdio.h>
   
3. #include <stdlib.h>
   
4. 
   
5. struct TreeNode
   
6. {
   
7.         ElementType Element;
   
8.         Position Left;
   
9.         Position Right;
   
10. };
    
11. 
    
12. SearchTree MakeEmpty( SearchTree T )
    
13. {
    
14.         if (T != NULL)
    
15.         {
    
16.                 MakeEmpty(T->Left);
    
17.                 MakeEmpty(T->Right);
    
18.                 free(T);
    
19.         }
    
20.         return NULL;
    
21. }
    
22. 
    
23. Position Find( ElementType X, SearchTree T )
    
24. {
    
25.         if (T == NULL)
    
26.                 return NULL;
    
27.         if (T->Element < X)
    
28.                 return Find(X, T->Right);
    
29.         else if(T->Element > X)
    
30.                 return Find(X, T->Left);
    
31.         else 
    
32.                 return T;
    
33.         //非递归实现
    
34.         /*while (T != NULL)
    
35.         {
    
36.                 if (T->Element < X)
    
37.                         T = T->Left;
    
38.                 else if (T->Element > X)
    
39.                         T = T->Right;
    
40.                 else 
    
41.                         return T;
    
42.         }*/
    
43. }
    
44. 
    
45. Position FindMin( SearchTree T )
    
46. {
    
47.         if (T == NULL)
    
48.                 return NULL;
    
49.         else if (T->Left == NULL)
    
50.                 return T;
    
51.         else 
    
52.                 return FindMin(T->Left);
    
53.         //非递归实现
    
54.         /*Position P = T;
    
55.         while (P->Left != NULL)
    
56.         {
    
57.                 P = P->Left;
    
58.         }
    
59.         return P;*/
    
60. }
    
61. 
    
62. Position FindMax( SearchTree T )
    
63. {
    
64.         if (T == NULL)
    
65.                 return NULL;
    
66.         else if (T->Right == NULL)
    
67.                 return T;
    
68.         else 
    
69.                 return FindMax(T->Right);
    
70.         //非递归实现
    
71.         /*Position P = T;
    
72.         while (P->Right != NULL)
    
73.         {
    
74.                 P = P->Right;
    
75.         }
    
76.         return P;*/
    
77. }
    
78. 
    
79. SearchTree Insert( ElementType X, SearchTree T )
    
80. {
    
81.         if (T == NULL)
    
82.         {        //最后该插入X的位置
    
83.                 T = (Position)malloc(sizeof(struct TreeNode));
    
84.                 if (T == NULL)
    
85.                 {
    
86.                         printf("Out of space!\n");
    
87.                         return NULL;
    
88.                 }
    
89.                 T->Left = T->Right = NULL;
    
90.                 T->Element = X;
    
91.         }
    
92.         else if (T->Element < X)
    
93.                 T->Right = Insert(X, T->Right);
    
94.         else if (T->Element > X)
    
95.                 T->Left = Insert(X, T->Left);
    
96.         return T;
    
97. }
    
98. 
    
99. SearchTree Delete( ElementType X, SearchTree T )
    
100. {
     
101.         Position TmpCell;
     
102.         if (T == NULL)
     
103.                 printf("Cannot find element %d\n", X);
     
104.         else
     
105.         {
     
106.                 if (X < T->Element)   //在左子树中查找
     
107.                         T->Left = Delete(X, T->Left);
     
108.                 else if (X > T->Element)
     
109.                         T->Right = Delete(X, T->Left);
     
110.                 else
     
111.                 {
     
112.                         //找到值为X的节点，即此时的T，判断该节点的左右孩子是否都存在
     
113.                         if (T->Left && T->Right)
     
114.                         {
     
115.                                 TmpCell = FindMin(T->Right);    //找到右子树中的最小者
     
116.                                 T->Element = TmpCell->Element;
     
117.                                 T->Right = Delete(T->Element, T->Right);  //改为删除T右子树中最小者
     
118.                         }
     
119.                         else
     
120.                         {
     
121.                                 TmpCell = T;
     
122.                                if ( T->Left == NULL) 
     
123.                                         T = T->Right;  
     
124.                                else if ( T->Right == NULL )  
     
125.                                         T = T->Left; 
     
126. 
     
127.                                 free(TmpCell);
     
128.                         }
     
129.                 }
     
130.                 
     
131.         }
     
132.         return T;
     
133. } 
     
134. 
     
135. void PrintTree( SearchTree T )
     
136. {
     
137.         if (T != NULL)
     
138.         {
     
139.                 printf("%5d\n", T->Element);
     
140.                 PrintTree(T->Left);
     
141.                 PrintTree(T->Right);
     
142.         }
     
143. }
     
144. 
     
145. ElementType Retrieve( Position P )
     
146. {
     
147.         return P->Element;
     
148. }