1 #include <cstdio>  2 #include <cstdlib>  3 #include <ctime>  4   5 #define MIN (1 << 31)  6   7 typedef int itemType;  8 struct TreeNode;  9 typedef struct TreeNode *position; 10 typedef struct TreeNode *tree; 11  12 struct TreeNode { 13     itemType item; 14     tree left; 15     tree right; 16 }; 17 // 由于树在定义上的递归性。我们选择用递归的方法去实现，也是最简洁直观的。  18 tree 19 MakeEmpty(tree t) 20 { 21     if (t != NULL) { 22         MakeEmpty(t->left); 23         MakeEmpty(t->right); 24         free(t); 25     } 26     return NULL; 27 } 28  29 position 30 Find( itemType x, tree t) 31 { 32     if (t != NULL) { 33         if (x < t->item) { 34             return Find(x, t->left); 35         } 36         else if (x > t->item) { 37             return Find(x, t->right); 38         } 39         else { 40             return t; 41         } 42     } 43     else { 44         return t; 45     } 46 } 47  48 position 49 FindMin(tree t) 50 { 51     if (t != NULL) { 52         if (t->left == NULL) { 53             return t; 54         } 55         else { 56             return FindMin(t->left); 57         } 58     }  59     else { 60         return t; 61     } 62 } 63  64 position 65 FindMax(tree t) 66 { 67     if (t != NULL) { 68         if (t->right == NULL) { 69             return t; 70         } 71         else { 72             return FindMax(t->right); 73         } 74     } 75     else { 76         return t; 77     } 78 } 79  80 tree 81 Insert(itemType x, tree t) 82 { 83     // 如果t为NULL，则说明到达了应该插入的位置，则我们插入。  84     if (t == NULL) { 85         t = (tree)malloc(sizeof(struct TreeNode)); 86         if (t == NULL) { 87             printf("Out of space!\n"); 88             return NULL; 89         } 90         t->item = x; 91         t->left = NULL; 92         t->right = NULL; 93     } 94     else { 95         if (x < t->item) { 96             t->left = Insert(x, t->left); 97         }  98         else if (x > t->item) { 99             t->right = Insert(x, t->right);100         }101     }102     // 返回插入工作完成之后的树根。 103     return t;104 }105 // 如果待删除的节点有零个或一个叶子节点的，我们可以编写一组代码来处理。106 // 对待待删除的节点有两个叶子节点的，我们编写一组代码来处理。    107 tree108 Delete(itemType x, tree t)109 {110     position tmp;111     112     if (t == NULL) {113         //printf("Item not found!\n");114     } 115     else if (x < t->item) {116         t->left = Delete(x, t->left);117     }118     else if (x > t->item) {119         t->right = Delete(x, t->right);120     }121     else if (t->left != NULL && t->right != NULL) {122         tmp = FindMin(t->right);123         t->item = tmp->item;124         t->right = Delete(t->item, t->right);125     }126     else {127         tmp = t;128         /* 这种写法不能正确处理零个叶子节点的情况 129         if (t->left != NULL) { // 处理左叶子节点存在的情况 130             t = t->left;131         }132         else if (t->right != NULL) { // 处理右叶子节点存在的情况 133             t = t->right;134         }135         */136         if (t->left == NULL) { // 处理右叶子节点存在或者无叶子节点的情况 137             t = t->right;138         } else if (t->right == NULL) { // 处理左叶子节点存在的情况 139             t = t->left;140         }141         free(tmp);142     }143     return t;144 }145 146 itemType147 Retrieve(position p)148 {149     if (p == NULL) {150         printf("Position invalid!\n");151         return MIN;152     }153     else {154         return p->item;155     }156 }157 158 void159 PrintItem(position p)160 {161     if (p != NULL) {162         printf("%d\t", p->item);163     } else {164         printf("Position invalid!\n");165     }166 }167 168 void169 InorderTraverse(tree t)170 {171     if (t != NULL) {172         InorderTraverse(t->left);173         PrintItem(t);174         InorderTraverse(t->right);175     }176 }177 178 int179 main(int argc, char** argv)180 {181     tree t;182     t = NULL;183 184     srand((unsigned int)time(NULL));185     // insert186     for (int i = 0; i < 100; i++) {187         t = Insert(rand()%100, t);188     }189     // find min190     position p;191     p = FindMin(t);192     if (p != NULL) {193         printf("min: %d\n", p->item);194     }195     // find max196     p = FindMax(t);197     if (p != NULL) {198         printf("max: %d\n", p->item);199     }200     // traverse201     printf("traverse: \n");202     InorderTraverse(t);203     printf("\n");204     // delete205     printf("deleting...\n");206     for (int i = 0; i < 100; i++) {207         t = Delete(rand()%100, t);208     }209     // find min210     p = FindMin(t);211     if (p != NULL) {212         printf("min: %d\n", p->item);213     }214     // find max215     p = FindMax(t);216     if (p != NULL) {217         printf("max: %d\n", p->item);218     }219     // traverse220     printf("traverse: \n");221     InorderTraverse(t);222     printf("\n");223     224     system("pause");225     return 0;226 }