1 #include "stdafx.h"
  2 #include<stdlib.h>
  3 #include<iostream>
  4 using namespace std;
  5 typedef int ElementType;
  6 
  7 
  8 struct TreeNode;
  9 typedef struct TreeNode *Position;
 10 typedef struct TreeNode *SearchTree;
 11 SearchTree MakeEmpty(SearchTree T);
 12 Position Find(ElementType x, SearchTree T);
 13 Position FindMin(ElementType x, SearchTree T);
 14 Position FindMax(ElementType x, SearchTree T);
 15 SearchTree Insert(ElementType x, SearchTree T);
 16 SearchTree Delete(ElementType x, SearchTree T);
 17 ElementType Retrieve(Position P);
 18 
 19 struct TreeNode
 20 {
 21     ElementType Element;
 22     SearchTree left;
 23     SearchTree right;
 24 };
 25 
 26 SearchTree MakeEmpty(SearchTree T)
 27 {
 28     if (T != NULL)
 29     {
 30         MakeEmpty(T->left);
 31         MakeEmpty(T->right);
 32         free(T);
 33     }
 34 }
 35 
 36 Position Find(ElementType x,SearchTree T)
 37 {
 38     if (T == NULL)
 39         return NULL;
 40     if (x < T->Element)
 41         return Find(x, T->left);
 42     else
 43         if (x > T->Element)
 44             return Find(x, T->right);
 45         else
 46         {
 47             return T;
 48         }
 49 }
 50 
 51 Position FindMin(SearchTree T)
 52 {
 53     if (T == NULL)
 54         return NULL;
 55     else if (T->left == NULL)
 56         return T;
 57     else
 58         return FindMin(T->left);
 59 }
 60 
 61 Position FindMax(SearchTree T)
 62 {
 63     if(T!=NULL)
 64         while (T->right!=NULL)
 65         {
 66             T = T->right;
 67         }
 68     return T;
 69 }
 70 
 71 SearchTree Insert(ElementType x,SearchTree T)
 72 {
 73     if (T == NULL) {
 74         T = (SearchTree)malloc(sizeof(struct TreeNode));
 75         if (T == NULL)
 76             EXIT_FAILURE;
 77         else
 78         {
 79             T->Element = x;
 80             T->left = T->right = NULL;
 81         }
 82     }
 83     else
 84     {
 85         if (x < T->Element)
 86             T->left = Insert(x, T->left);
 87         else if (x > T->Element)
 88             T->right = Insert(x, T->right);
 89        //否则在已在树上什么都不做
 90         return T;
 91     }
 92 
 93 }
 94 
 95 SearchTree Delete(ElementType x, SearchTree T)
 96 {
 97     Position TmpCell;
 98     if (T == NULL)
 99         cout << "Element no found";
100     else if (x < T->Element)
101         T->left = Delete(x, T->left);
102     else
103       if (x > T->Element)
104          T->right = Delete(x, T->right);
105       else//找到要删除的元素
106       {
107           if (T->left&&T->right) {
108               TmpCell = FindMin(T->right);
109               T->Element = TmpCell->Element;
110               T->right = Delete(T->Element, T->right);
111           }
112           else //只有一个或者没有儿子
113           {
114               TmpCell = T;
115               if (T->left == NULL)
116                   T = T->right;
117               else if (T->right == NULL)
118                   T = T->left;
119               free(TmpCell);
120           }
121       }
122     return T;
123     
124 
125 }
126 
127 int main()
128 {
129     return 0;
130 }