二叉搜索树(遍历,查找,插入,删除)

二叉搜索树就类似于二分查找,根节点的左边都比根结点小,右边都比根结点大。

  1 #include<stdio.h>
  2 #include<stdlib.h>
  3 
  4 typedef int TElemType;
  5 typedef int ElemType;
  6 #define OK 1
  7 #define ERROR -1
  8 
  9 typedef struct BiTNode
 10 {
 11     TElemType data;
 12     struct BiTNode* lchild;
 13     struct BiTNode* rchild;
 14 }BiTNode,*BiTree;
 15 //前序遍历创建二叉树
 16 void PreOrderCreatBiTree(BiTree *T)
 17 {
 18     int ch;
 19     scanf("%d", &ch);
 20     if (ch == 0)
 21     {
 22         *T = NULL;
 23     }
 24     else
 25     {
 26         *T = (BiTNode *)malloc(sizeof(BiTNode));
 27         (*T)->data = ch;
 28         PreOrderCreatBiTree(&(*T)->lchild);
 29         PreOrderCreatBiTree(&(*T)->rchild);
 30     }
 31 }
 32 //前序遍历
 33 void PreOrderTarverse(BiTree T)
 34 {
 35     if (T)
 36     {
 37         printf("%d", T->data);
 38         PreOrderTarverse(T->lchild);
 39         PreOrderTarverse(T->rchild);
 40     }
 41 }
 42 //查找元素
 43 int Find(ElemType x, BiTree T)
 44 {
 45     if (!T)  //如果树为空
 46         return ERROR;
 47     if (x > T->data)
 48     {
 49         return Find(x, T->rchild);
 50     }
 51     else if (x < T->data)
 52     {
 53         return Find(x, T->lchild);
 54     }
 55     else if(x == T->data)
 56     {
 57         return OK;
 58     }
 59     return ERROR;
 60 }
 61 //查找最小值并返回值
 62 int FindMin(BiTree T)
 63 {
 64     if (!T)  //如果树为空
 65     {
 66         return ERROR;
 67     }
 68     else if (!T->lchild)
 69     {
 70         return T->data;
 71     }
 72     else
 73     {
 74         return FindMin(T->lchild);
 75     }
 76 }
 77 //查找最小值并返回地址
 78 BiTree FindMinAddress(BiTree T)//删除使用到
 79 {
 80     if (!T)  //如果树为空
 81     {
 82         return NULL;
 83     }
 84     else if (!T->lchild)
 85     {
 86         return T;
 87     }
 88     else
 89     {
 90         return FindMin(T->lchild);
 91     }
 92 }
 93 //查找最大值并返回值
 94 int FindMax(BiTree T)
 95 {
 96     if (T)
 97     {
 98         while (T->rchild)
 99         {
100             T = T->rchild;
101         }
102     }
103     return T->data;
104 }
105 //插入
106 BiTree Insert(BiTree *T, ElemType x)
107 {
108     if (!(*T))  //数为空,则生成并返回一个结点的搜索二叉树
109     {
110         *T = (BiTNode *)malloc(sizeof(BiTNode));
111         (*T)->data = x;
112         (*T)->lchild = (*T)->rchild = NULL;
113     }
114     else  //开始找要插入元素的位置
115     {
116         if (x < (*T)->data)
117         {
118             (*T)->lchild = Insert(&(*T)->lchild, x);  //递归插入左子树
119         }
120         else if (x > (*T)->data)
121         {
122             (*T)->rchild = Insert(&(*T)->rchild, x);  //递归插入右子树    
123         }
124         //else x已经存在,什么都不做
125     }
126     return *T;
127 }
128 //删除
129 BiTree Delete(BiTree* T, ElemType x)
130 {
131     BiTree Tmp;
132 
133     if (!(*T))
134     {
135         printf("要删除的元素未找到");
136     }
137     else
138     {
139         if (x < (*T)->data) //递归左子树
140         {
141             (*T)->lchild = Delete(&(*T)->lchild, x);
142         }
143         else if (x > (*T)->data) //递归右子树
144         {
145             (*T)->rchild = Delete(&(*T)->rchild, x);
146         }
147         else  //递归到要删除的结点
148         {
149             if ((*T)->lchild && (*T)->rchild)  //被删除结点有两个子树
150             {
151                 Tmp = FindMinAddress((*T)->rchild);
152                 (*T)->data = Tmp->data;
153                 (*T)->rchild = Delete(&(*T)->rchild, (*T)->data);
154             }
155             else
156             {
157                 Tmp = *T;
158                 if (!(*T)->lchild) //只有右孩子或者没有子结点
159                 {
160                     *T = (*T)->rchild;
161                 }
162                 else
163                 {
164                     *T = (*T)->lchild;
165                 }
166                 free(Tmp);
167             }
168 
169         }
170     }
171     return *T;
172 }
173 
174 int main()
175 {
176     BiTree T = NULL;
177     int FindNum;
178     int temp;
179     int min,max;
180     int InsertNum;
181     int DeleteNum;
182 
183     printf("请输入数据,0表示空\n");
184     PreOrderCreatBiTree(&T);
185     printf("前序遍历二叉树并打印:\n");
186     PreOrderTarverse(T);
187 
188     printf("\n请输入你想要查找的元素:");
189     scanf("%d", &FindNum);
190     temp = Find(FindNum,T);
191     if (temp == 1)
192     {
193         printf("查找成功!你所要查找的数据在树中\n");
194     }
195     else if(temp == -1)
196     {
197         printf("查找失败!你所要查找的数据不在树中\n");
198     }
199 
200     min = FindMin(T);
201     printf("树中的最小值是:%d\n", min);
202     max = FindMax(T);
203     printf("树中的最大值是:%d\n", max);
204 
205     printf("请输入你想要插入的数据:");
206     scanf("%d", &InsertNum);
207     Insert(&T, InsertNum);
208     printf("插入后遍历树并打印:\n");
209     PreOrderTarverse(T);
210 
211     printf("\n请输入你想要删除的数据:");
212     scanf("%d", &DeleteNum);
213     Delete(&T, DeleteNum);
214     printf("删除后遍历树并打印:\n");
215     PreOrderTarverse(T);
216 
217     return 0;
218 }

 

上一篇:二叉树中的最大路径和(python实现)


下一篇:二叉树 概念+代码