二叉查找树

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 
  4 #define MaxSize 1000
  5 
  6 typedef int ElementType;
  7 
  8 struct BinarySearchTreeNode
  9 {
 10     ElementType Element;
 11     struct BinarySearchTreeNode *Left;
 12     struct BinarySearchTreeNode *Right;
 13 };
 14 
 15 struct BinarySearchTreeNode *BinarySearchTreeInit()
 16 {
 17     struct BinarySearchTreeNode *TreeRoot = NULL;
 18     
 19     return TreeRoot;
 20 }
 21 
 22 int BinarySearchTreeDestroy(struct BinarySearchTreeNode *TreeRoot)
 23 {
 24     if(TreeRoot != NULL)
 25     {
 26         BinarySearchTreeDestroy(TreeRoot -> Left);
 27         BinarySearchTreeDestroy(TreeRoot -> Right);
 28         free(TreeRoot);
 29     }
 30     return 0;
 31 }
 32 
 33 struct BinarySearchTreeNode *BinarySearchTreeNodeFind(ElementType ToBeFind,struct BinarySearchTreeNode *TreeRoot)
 34 {
 35     if(TreeRoot==NULL)
 36     {
 37         return NULL;
 38     }
 39     
 40     if(ToBeFind < TreeRoot -> Element)
 41     {
 42         return BinarySearchTreeNodeFind(ToBeFind,TreeRoot->Left);
 43     }
 44     else if(ToBeFind > TreeRoot -> Element)
 45     {
 46         return BinarySearchTreeNodeFind(ToBeFind,TreeRoot->Right);
 47     }
 48     else
 49     {
 50         return TreeRoot;
 51     }
 52 }
 53 
 54 struct BinarySearchTreeNode *BinarySearchTreeNodeFindMin(struct BinarySearchTreeNode *TreeRoot)
 55 {
 56     if(TreeRoot==NULL)
 57     {
 58         return NULL;
 59     }
 60     else if(TreeRoot->Left==NULL)
 61     {
 62         return TreeRoot;
 63     }
 64     else
 65     {
 66         return BinarySearchTreeNodeFindMin(TreeRoot->Left);
 67     }
 68 }
 69 
 70 struct BinarySearchTreeNode *BinarySearchTreeNodeFindMax(struct BinarySearchTreeNode *TreeRoot)
 71 {
 72     if(TreeRoot==NULL)
 73     {
 74         return NULL;
 75     }
 76     else if(TreeRoot->Right==NULL)
 77     {
 78         return TreeRoot;
 79     }
 80     else
 81     {
 82         return BinarySearchTreeNodeFindMax(TreeRoot->Right);
 83     }
 84 }
 85 
 86 //be careful of return NULL 
 87 struct BinarySearchTreeNode *BinarySearchTreeNodeInsert(ElementType ToBeInsert,struct BinarySearchTreeNode *TreeRoot)
 88 {
 89     if(TreeRoot==NULL)
 90     {
 91         TreeRoot = malloc(sizeof(struct BinarySearchTreeNode));
 92         TreeRoot -> Element = ToBeInsert;
 93         TreeRoot -> Left = TreeRoot -> Right = NULL;
 94     }
 95     else if(ToBeInsert < TreeRoot->Element)
 96     {
 97         TreeRoot -> Left = BinarySearchTreeNodeInsert(ToBeInsert,TreeRoot->Left);
 98     }
 99     else if(ToBeInsert > TreeRoot->Element)
100     {
101         TreeRoot -> Right = BinarySearchTreeNodeInsert(ToBeInsert,TreeRoot->Right);
102     }
103     return TreeRoot;
104 }
105 
106 //if doesn't find,return NULL
107 struct BinarySearchTreeNode *BinarySearchTreeNodeDelete(ElementType ToBeDelete,struct BinarySearchTreeNode *TreeRoot)
108 {
109     if(TreeRoot == NULL)
110         return NULL;
111     
112     struct BinarySearchTreeNode *TmpCell;
113     
114     if(ToBeDelete < TreeRoot -> Element)
115     {
116         TreeRoot -> Left = BinarySearchTreeNodeDelete(ToBeDelete,TreeRoot->Left);
117     }
118     else if(ToBeDelete > TreeRoot -> Element)
119     {
120         TreeRoot -> Right = BinarySearchTreeNodeDelete(ToBeDelete,TreeRoot->Right);
121     }
122     else //if(ToBeDelete == TreeRoot -> Element)
123     {
124         if(TreeRoot->Left && TreeRoot->Right)
125         {
126             TmpCell = BinarySearchTreeNodeFindMin(TreeRoot -> Right);
127             TreeRoot -> Element = TmpCell -> Element;
128             TreeRoot -> Right = BinarySearchTreeNodeDelete(TreeRoot->Element,TreeRoot->Right);
129         }
130         else
131         {
132             TmpCell = TreeRoot;
133             if(TreeRoot->Left==NULL)
134             {
135                 TreeRoot = TreeRoot -> Right;
136             }
137             else if(TreeRoot->Right==NULL)
138             {
139                 TreeRoot = TreeRoot -> Left;
140             }
141             free(TmpCell);
142         }
143     }
144     return TreeRoot;
145 }
146 
147 
148 int main()
149 {
150     struct BinarySearchTreeNode *TreeRoot = BinarySearchTreeInit();
151     TreeRoot = BinarySearchTreeNodeInsert(1,TreeRoot);
152     TreeRoot = BinarySearchTreeNodeInsert(2,TreeRoot);
153     TreeRoot = BinarySearchTreeNodeInsert(39,TreeRoot);
154     TreeRoot = BinarySearchTreeNodeInsert(-1,TreeRoot);
155 //    TreeRoot = BinarySearchTreeNodeDelete(2,TreeRoot);
156 //    TreeRoot = BinarySearchTreeNodeDelete(1,TreeRoot);
157 //    TreeRoot = BinarySearchTreeNodeDelete(39,TreeRoot);
158 //    FindNode = BinarySearchTreeNodeFind(2,TreeRoot);
159 //    FindNode = BinarySearchTreeNodeFindMin(TreeRoot);
160 //    FindNode = BinarySearchTreeNodeFindMax(TreeRoot);
161 //  BinarySearchTreeDestroy(TreeRoot);
162 //    printf("%d
",TreeNodeRoot->Element);
163     return 0;
164 }