1 #ifndef _Tree_H  2   3 struct TreeNode;  4 typedef struct TreeNode *Position;  5 typedef struct TreeNode *SearchTree;  6   7 SearchTree MakeEmpty(SearchTree T);  8 Position Find(ElementType X, SearchTree T);  9 Position FindMin(SearchTree T); 10 Position FindMax(SearchTree T); 11 SearchTree Insert(ElementType X, SearchTree T); 12 SearcgTree Delete(ElementType X, SearchTree T); 13 ElementType Retrieve(Position P); 14  15 #endif 16  17 struct TreeNode 18 { 19     ElementType Element; 20     SearchTree Left; 21     SearchTree Right; 22 } 23  24  25 SearchTree MakeEmpty(SearchTree T) 26 { 27     if (T != NULL) 28     { 29         MakeEmpty(T->Left); 30         MakeEmpty(T->Right); 31         free(T); 32     } 33     return NULL; 34 } 35  36  37 Position Find(ElementType X, SearchTree T) 38 { 39     if (T == NULL) 40         return NULL; 41     if (X < T->Element) 42         return Find(X, T->Left); 43     else if (X > T->Element) 44         return Find(X, T->Right); 45     else 46         return T; 47 } 48  49  50 Position FindMin(SearchTree T) 51 { 52     if (T == NULL) 53         return NULL; 54     else if (T->Left == NULL) 55         return T; 56     else 57         return FindMin(T->Left); 58 } 59  60 Position FindMax(SearchTree T) 61 { 62     if (T != NULL) 63         while (T->Right != NULL) 64             T = T->Right; 65     return T; 66 } 67  68  69 SearchTree Insert(ElementType X, SearchTree T) 70 { 71     if (T == NULL) 72     { 73         T = malloc(sizeof(struct TreeNode)); 74         if (T = NULL) 75             perror("Out of Space!"); 76         else 77         { 78             T->Element = X; 79             T->Left = T->Right = NULL; 80         } 81     } 82     else if (X < T->Element) 83         T->Left = Insert(X, T->Left); 84     else 85         T->Right = Insert(X, T->Right); 86  87     return T; 88 } 89  90  91 SearchTree Delete(ElementType X, SearchTree T) 92 { 93     Position TmpCell; 94  95     if (T == NULL) 96         perror("Element not found!"); 97     else if (X < T->Left) 98         T->Left = Delete(X, T->Left); 99     else if(X > T-Right)100         T->Right = Delete(X, T->Right);101 102     else if (T->Left && T->Right)103     {104         TmpCell = FindMin(T->Right);105         T->Element = TmpCell->Element;106         T->Right = Delete(T->Element, T->Right);107     }108     else109     {110         TmpCell = T;111         if (T->Left == NULL)112             T = T->Right;113         else if (T->Right == NULL)114             T = T->Left;115         free(TmpCell);116     }117 118     return T;119 }