数据结构与算法复习[ADT树基本操作]

复习记录，高手无视，关于 二叉搜索树的一些基本操作。

1. //Code by Pnig0s1992  
2. //Date:2012,3,28  
3. #include <stdio.h>  
4. #include <stdlib.h>  
5.  
6. typedef int Element_type;  
7. typedef struct TreeNode * ptrTreeNode;  
8. typedef struct TreeNode * ADTTree;  
9. struct TreeNode  
10. {  
11.     Element_type element;  
12.     ptrTreeNode pLeftChild;  
13.     ptrTreeNode pRightChild;  
14. };  
15.  
16. void MakeEmpty(ADTTree myTree);//将ADT树置空  
17. ptrTreeNode Find(Element_type x,ADTTree myTree);//查找指定元素的结点并返回  
18. ptrTreeNode FindMin(ADTTree myTree);//查找ADT树中的最小值  
19. ptrTreeNode FindMax(ADTTree myTree);//查找ADT树中的最大值  
20. ptrTreeNode Insert(Element_type x,ADTTree myTree);//向ADT树中插入结点  
21. ptrTreeNode Delete(Element_type x,ADTTree myTree);//ADT树中删除指定结点  
22. ADTTree CreateTree(Element_type x);//构造一个新ADT树并返回根节点指针  
23.  
24. int main(int argc,char ** argv)  
25. {  
26.     Element_type el = 6;  
27.     ADTTree newTree = CreateTree(el);  
28.     newTree = Insert(2,newTree);  
29.     newTree = Insert(8,newTree);  
30.     newTree = Insert(1,newTree);  
31.     newTree = Insert(4,newTree);  
32.     newTree = Insert(3,newTree);  
33.     newTree = Delete(6,newTree);  
34.     return 0;  
35. }  
36. //构建ADT树  
37. ADTTree CreateTree(Element_type x)  
38. {  
39.     ADTTree newTree = (ptrTreeNode)malloc(sizeof(TreeNode));  
40.     newTree->element = x;  
41.     newTree->pLeftChild = newTree->pRightChild = NULL;  
42.     return newTree;  
43. }  
44. //向ADT树中插入一个结点  
45. ptrTreeNode Insert(Element_type x,ADTTree myTree)  
46. {  
47.     if(myTree == NULL)  
48.     {  
49.         myTree =(ptrTreeNode) malloc(sizeof(TreeNode));  
50.         if(myTree == NULL)  
51.         {  
52.             printf("\nOut of space.");  
53.         }  
54.         else 
55.         {  
56.             myTree->element = x;  
57.             myTree->pLeftChild = myTree->pRightChild = NULL;  
58.         }  
59.     }else if (x < myTree->element)  
60.     {  
61.         myTree->pLeftChild = Insert(x,myTree->pLeftChild);  
62.     }else if (x > myTree->element)  
63.     {  
64.         myTree->pRightChild = Insert(x,myTree->pRightChild);  
65.     }  
66.     return myTree;  
67. }  
68. //找到ADT树最小结点  
69. ptrTreeNode FindMin(ADTTree myTree)  
70. {  
71.     if(myTree == NULL)  
72.     {  
73.         printf("\nThe tree is empty.");  
74.     }else if (myTree->pLeftChild == NULL)  
75.     {  
76.         return myTree;  
77.     }else 
78.     {  
79.         return FindMin(myTree->pLeftChild);  
80.     }  
81. }  
82. //找到ADT树最大结点  
83. ptrTreeNode FindMax(ADTTree myTree)  
84. {  
85.     if(myTree == NULL)  
86.     {  
87.         printf("\nThe tree is empty.");  
88.     }else if (myTree->pRightChild == NULL)  
89.     {  
90.         return myTree;  
91.     }else 
92.     {  
93.         return FindMax(myTree->pRightChild);  
94.     }  
95. }  
96. //删除指定ADT树结点  
97. ptrTreeNode Delete(Element_type x,ADTTree myTree)  
98. {  
99.     ptrTreeNode TempCell;  
100.     if(myTree == NULL)  
101.     {  
102.         printf("\nThe tree is empty.");  
103.     }else if (x < myTree->element)  
104.     {  
105.         myTree->pLeftChild = Delete(x,myTree->pLeftChild);  
106.     }else if (x > myTree->element)  
107.     {  
108.         myTree->pRightChild = Delete(x,myTree->pRightChild);  
109.     }else if (myTree->pLeftChild && myTree->pRightChild)  
110.     {  
111.         TempCell = FindMin(myTree->pRightChild);  
112.         myTree->element = TempCell->element;  
113.         myTree->pRightChild = Delete(myTree->element,myTree->pRightChild);  
114.     }else 
115.     {  
116.         TempCell = myTree;  
117.         if(myTree->pLeftChild == NULL)  
118.         {  
119.             myTree = myTree->pRightChild;  
120.         }else if (myTree->pRightChild == NULL)  
121.         {  
122.             myTree = myTree->pLeftChild;  
123.         }  
124.         free(TempCell);  
125.     }  
126.     return myTree;  
127. }  
128.  
129. ptrTreeNode Find(Element_type x,ADTTree myTree)  
130. {  
131.     if(myTree == NULL)  
132.     {  
133.         printf("\nelement not be found.");  
134.     }else if (x < myTree->element)  
135.     {  
136.         return Find(x,myTree->pLeftChild);  
137.     }else if(x > myTree->element)  
138.     {  
139.         return Find(x,myTree->pRightChild);  
140.     }else 
141.         return myTree;  
142. }  
143.  
144. void MakeEmpty(ADTTree myTree)  
145. {  
146.     if(myTree != NULL)  
147.     {  
148.         MakeEmpty(myTree->pLeftChild);  
149.         MakeEmpty(myTree->pRightChild);  
150.         free(myTree);  
151.     }  
152.     return;  
153. }  
154.  

本文转hackfreer51CTO博客，原文链接：http://blog.51cto.com/pnig0s1992/819473，如需转载请自行联系原作者