04-树7 二叉搜索树的操作集

  本题要求实现给定二叉搜索树的5种常用操作。


函数接口定义：
BinTree Insert( BinTree BST, ElementType X );
BinTree Delete( BinTree BST, ElementType X );
Position Find( BinTree BST, ElementType X );
Position FindMin( BinTree BST );
Position FindMax( BinTree BST );
其中BinTree结构定义如下：
typedef struct TNode *Position;
typedef Position BinTree;
struct TNode{
    ElementType Data;
    BinTree Left;
    BinTree Right;
};
函数Insert将X插入二叉搜索树BST并返回结果树的根结点指针；
函数Delete将X从二叉搜索树BST中删除，并返回结果树的根结点指针；如果X不在树中，则打印一行Not Found并返回原树的根结点指针；
函数Find在二叉搜索树BST中找到X，返回该结点的指针；如果找不到则返回空指针；
函数FindMin返回二叉搜索树BST中最小元结点的指针；

函数FindMax返回二叉搜索树BST中最大元结点的指针。

输入样例：
10
5 8 6 2 4 1 0 10 9 7
5
6 3 10 0 5
5
5 7 0 10 3
输出样例：
Preorder: 5 2 1 0 4 8 6 7 10 9
6 is found
3 is not found
10 is found
10 is the largest key
0 is found
0 is the smallest key
5 is found
Not Found
Inorder: 1 2 4 6 8 9

[cpp] view plain copy

print?

1. #include <stdio.h>  
2. #include <stdlib.h>  
3.   
4. typedef int ElementType;  
5. typedef struct TNode *Position;  
6. typedef Position BinTree;  
7. struct TNode {  
8.     ElementType Data;  
9.     BinTree Left;  
10.     BinTree Right;  
11. };  
12.   
13. void PreorderTraversal(BinTree BT);   
14. void InorderTraversal(BinTree BT);    
15. void PostorderTraversal(BinTree BT);  
16. BinTree Insert(BinTree BST, ElementType X);  
17. BinTree Delete(BinTree BST, ElementType X);  
18. Position Find(BinTree BST, ElementType X);  
19. Position FindMin(BinTree BST);  
20. Position FindMax(BinTree BST);  
21.   
22. int main()  
23. {  
24.     BinTree BST, MinP, MaxP, Tmp;  
25.     ElementType X;  
26.     int N, i;  
27.   
28.     BST = NULL;  
29.     scanf("%d", &N);  
30.     for (i = 0; i<N; i++) {  
31.         scanf("%d", &X);  
32.         BST = Insert(BST, X);  
33.     }  
34.     printf("Postorder:");  
35.     PostorderTraversal(BST);  
36.     printf("\n");  
37.     printf("Preorder:");  
38.     PreorderTraversal(BST);  
39.     printf("\n");  
40.     MinP = FindMin(BST);  
41.     MaxP = FindMax(BST);  
42.     scanf("%d", &N);  
43.     for (i = 0; i<N; i++) {  
44.         scanf("%d", &X);  
45.         Tmp = Find(BST, X);  
46.         if (Tmp == NULL) printf("%d is not found\n", X);  
47.         else {  
48.             printf("%d is found\n", Tmp->Data);  
49.             if (Tmp == MinP) printf("%d is the smallest key\n", Tmp->Data);  
50.             if (Tmp == MaxP) printf("%d is the largest key\n", Tmp->Data);  
51.         }  
52.     }  
53.     scanf("%d", &N);  
54.     for (i = 0; i<N; i++) {  
55.         scanf("%d", &X);  
56.         BST = Delete(BST, X);  
57.     }  
58.     printf("Inorder:");   
59.     InorderTraversal(BST);  
60.     printf("\n");  
61.   
62.     return 0;  
63. }  
64.   
65. void PreorderTraversal(BinTree BT) {  
66.     if (!BT) return;  
67.     printf(" %d", BT->Data);  
68.     PreorderTraversal(BT->Left);  
69.     PreorderTraversal(BT->Right);  
70. }  
71.   
72. void InorderTraversal(BinTree BT) {  
73.     if (!BT) return;      
74.     PreorderTraversal(BT->Left);  
75.     printf(" %d", BT->Data);  
76.     PreorderTraversal(BT->Right);  
77. }  
78.   
79. void PostorderTraversal(BinTree BT) {  
80.     if (BT) {  
81.         PostorderTraversal(BT->Left);  
82.         PostorderTraversal(BT->Right);  
83.         printf(" %d", BT->Data);  
84.     }  
85. }  
86.   
87. BinTree Insert(BinTree BST, ElementType X) {  
88.     if (!BST) {  
89.         BST = (BinTree)malloc(sizeof(struct TNode));  
90.         BST->Data = X;  
91.         BST->Left = NULL;  
92.         BST->Right = NULL;  
93.     }  
94.     else if (X < BST->Data)  
95.         BST->Left = Insert(BST->Left, X);  
96.     else if (X > BST->Data)  
97.         BST->Right = Insert(BST->Right, X);  
98.     return BST;  
99. }  
100.   
101. BinTree Delete(BinTree BST, ElementType X) {  
102.     Position Tmp;  
103.     if (!BST) {  
104.         printf("Not Found\n");  
105.     }  
106.     else if (X < BST->Data)  
107.         BST->Left = Delete(BST->Left, X);  
108.     else if (X > BST->Data)  
109.         BST->Right = Delete(BST->Right, X);  
110.     else {  
111.         if (BST->Left && BST->Right) {  
112.             Tmp = FindMax(BST->Left);  
113.             BST->Data = Tmp->Data;  
114.             BST->Left= Delete(BST->Left, Tmp->Data);  
115.         }  
116.         else {  
117.             Tmp = BST;  
118.             if (!BST->Left)  
119.                 BST = BST->Right;  
120.             else  
121.                 BST = BST->Left;  
122.             free(Tmp);  
123.         }  
124.     }  
125.     return BST;  
126. }  
127.   
128. Position Find(BinTree BST, ElementType X) {  
129.     while (BST && (X != BST->Data)) {  
130.         if (X < BST->Data)  
131.             BST = BST->Left;  
132.         else  
133.             BST = BST->Right;  
134.     }  
135.     return BST;  
136. }  
137.   
138. Position FindMin(BinTree BST) {  
139.     if (BST) {  
140.         while (BST->Left)  
141.             BST = BST->Left;  
142.     }  
143.     return BST;  
144. }  
145.   
146. Position FindMax(BinTree BST) {  
147.     if (BST) {  
148.         while (BST->Right)  
149.             BST = BST->Right;  
150.     }  
151.     return BST;  
152. }