数据结构 排序二叉树(BST) 插入删除查询 中序遍历 销毁(后序遍历)

结构概念如下：

二叉排序树(binary sort tree):

1、也叫做二叉查找树

2、如果他的左子树不为空，则左子树上所有结点的

值均小于他的根结构的值

3、如果他的右子树不为空，则右子树上所有结点的

值均大于他的根结构的值

4、他的左右子树分别为二叉排序树

5、按照二叉树中序遍历其返回结果树有序的

下面就是一颗典型的二叉树，只是是字母，可以将字母换位字母的顺序进行审视，但是它不是平衡二叉树

排序二叉树(BST)的优点在于进行数据查找比较方便，因为他是按照数据来到的顺序进行如上的规则进行的
建树，只要如上的规则进行查找就能找到需要的数据。但是其缺点也是显而易见，树的深度是不可控制的
而且可能极不均匀，考虑 1 2 3 4 5 6 7，这样的数据建树全部节点都在左子树上，级不均匀。那么给
搜索数据的性能带来的较大的影响，所以引入了AVL树平衡二叉树，这个在后面再说

关于排序二叉树BST的各种操作都使用了递归算法，给出递归算法一张我认为很好的图：

这张图实际体现了递归的真谛 顺序调用反向返回，这个列子和图来自小甲鱼C视频也可能来自大话数据结构
上面的代码实际上是：

void print()
{
    char a;
    scanf("%c",&a);
      if(a!='#') print();
      if(a!='#') printf("%c",a);
}

关于递归的经典 费布那切数列和汉诺塔等都可以了解一下；
下面回归正题，直接给出代码和测试用例。说明代码大部分来自大话数据结构，销毁和中序遍历是我自己写的，但是我自己进行了理解。
主要删除数据比较难，分为3种情况
1、删除节点的左子树为空，更改*p = (*p)->rchild;注意这里的*p代表的是parent->child，所以这样做就是将父节原来指向删除节点的指针，指向删除节点的下一个右孩子
2、删除节点的右子树为空，同理更改*p = (*p)->lchild;注意这里的*p代表的是parent->child，所以这样做就是将父节原来指向删除节点的指针，指向删除节点的下一个左孩子
3、删除节点左右子树都不为空，需要进行找到直接前驱或者直接后继节点进行数据代替。这个就比较复杂直接看代码吧
分别进行讨论。 
其他操作相对简单不用再秒素就是递归,但是需要注意排序返回数据是用中序遍历，销毁树用的是后序遍历。
代码如下：

点击(此处)折叠或打开

1. 头文件
2. bstort.h
3. #include<stdio.h>
4. typedef int bool;
5. #define false 0
6. #define true 1
7. #define xfree(x) free(x); x = NULL;
8. typedef struct BiTnode
9. {
10.         int data;
11.         struct BiTnode *lchild,*rchild;
12. } BiTnode,*BiTree;
13. bool SearchBst(BiTree T,int key,BiTree *f,BiTree *p);
14. bool InsertBst(BiTree *T,int key) ;
15. void Inordervist(const BiTree T);
16. void BTreedestroy(BiTree tree);
17. bool DeleteBst(BiTree *T,int key);
18. bool Delete(BiTree *p);

点击(此处)折叠或打开

1. 实现程序
2.  bstort.c
3. #include<stdio.h>
4. #include<stdlib.h>
5. #include"bstort.h"
6. /*
7.    T = Bst root node
8.    key = search key
9.    f = T's parent node,used if search failed save last search node pointer
10.    if search failed last T is NULL,inital vlaues is NULL,
11.    is sucuess f is pointer to p's parent poniter,
12.    p = if sucess p is pointer to find node pointer,if failed is pointer to last
13.    search node pointer
14. */
15. bool SearchBst(BiTree T,int key,BiTree *f,BiTree *p)
16. {
17.         if(!T)
18.         {
19.                 *p = *f;
20.                 return false;
21.         }
22.         else if(key == T->data)
23.         {
24.                 *p = T;
25.                 return true;
26.         }
27.         else if(key < T->data)
28.         {
29.                 *f = T;
30.                 return SearchBst(T->lchild,key,f,p);
31.         }
32.         else
33.         {
34.                 *f = T;
35.                 return SearchBst(T->rchild,key,f,p);
36.         }
37. }
38. /*
39.    T = Bst root node
40.    key = key to insert
41.    */
42. bool InsertBst(BiTree *T,int key)
43. {
44.         BiTree p = NULL ,s = NULL ,f=NULL;
45.         if(!SearchBst(*T,key,&f,&p)) //init NULL,KEY,NULL,&P=NULL
46.         {
47.                 s = (BiTree)calloc(1,sizeof(BiTnode));
48.                 s->data =key;
49.                 s->lchild = s->rchild = NULL;
50.                 if(!p)
51.                 {
52.                         printf("Create Tree with key:%d\n",key);
53.                         *T = s; //create Bst one node
54.                 }
55.                 else if(key < p->data)
56.                 {
57.                         printf("Insert Key To Tree(left):%d\n",key);
58.                         p->lchild = s;
59.                 }
60.                 else
61.                 {
62.                         printf("Insert Key To Tree(right):%d\n",key);
63.                         p->rchild = s;
64.                 }
65.                 return true;
66.         }
67.         else
68.         {
69.                 return false;
70.         }
71. }
72. /*
73. inorder traversal method
74. */
75. void Inordervist(const BiTree T)
76. {
77.         if(T)
78.         {
79.                 Inordervist(T->lchild);
80.                 printf("%d\n",T->data);
81.                 Inordervist(T->rchild);
82.         }
83. }
84. /*
85. postorder traversal method to destroy tree
86. */
87. void BTreedestroy(BiTree T)
88. {
89.         if(T)
90.         {
91.         BTreedestroy(T->lchild);
92.         BTreedestroy(T->rchild);
93.         printf("Delete node for Key%d\n",T->data);
94.         xfree(T);
95.         }
96. }
97. bool DeleteBst(BiTree *T,int key)//use **p *p is parent->child,here is very import
98. {
99.         if(!*T)//
100.         {
101.                 printf("no delete data %d find\n........\n",key);
102.                 return true;
103.         }
104.         else
105.         {
106.                 if(key == (*T)->data)
107.                 {
108.                         return Delete(T);
109.                 }
110.                 else if(key < (*T)->data)
111.                 {
112.                         return DeleteBst(&(*T)->lchild,key);//here use lchild pointer's address
113.                 }
114.                 else
115.                 {
116.                         return DeleteBst(&(*T)->rchild,key);
117.                 }
118.         }
119. }
120. bool Delete(BiTree *p)//use **p *p is parent->child,here is very import
121. {
122.         BiTree q,s;
123.         printf("delete data :%d\n........\n",(*p)->data);
124.         if((*p)->rchild == NULL)//right node is NULL
125.         {
126.                 q = *p;
127.                 *p = (*p)->lchild;
128.                 xfree(q);
129.         }
130.         else if((*p)->lchild ==NULL)//leaf node is NULL
131.         {
132.                 q = *p;
133.                 *p = (*p)->rchild;
134.                 xfree(q);
135.         }
136.         else //exp:use ...20 30 50 (60 delete)... use 50 replace 60 ,use replace not free find node
137.         {
138.                 q = *p;
139.                 //---------------
140.                 s = (*p)->lchild;
141.                 while(s->rchild) //if s->rchild is NULL q=*p mean (*p)->lchild s have no right node
142.                 {
143.                         q = s;
144.                         s = s->rchild;
145.                 }
146.                 (*p)->data = s->data;
147.                 /*-------------- here find near delete node small data,frist find lchild then find
148.                 all small data root node then find last right node this is require data*/
149.                 if(q!=*p) //if (*p)->lchild s have right node
150.                 {
151.                         q->rchild =s->lchild;
152.                 }
153.                 else // if (*p)->lchild s have no right node
154.                 {
155.                         q->lchild = s ->lchild;
156.                 }
157.                 xfree(s);//free find last right node,beacuse it's data used for find node
158.         }
159. }

点击(此处)折叠或打开

1. 测试用例和主函数
2. main.c
3. #include<stdio.h>
4. #include"bstort.h"
5. int main(void)
6. {
7.         BiTree root = NULL;
8.         InsertBst(&root,10);
9.         InsertBst(&root,20);
10.         InsertBst(&root,40);
11.         InsertBst(&root,5);
12.         InsertBst(&root,1);
13.         InsertBst(&root,-1);
14.         InsertBst(&root,-20);
15.         InsertBst(&root,100);
16.         printf("Use inorder traversal method:\n");
17.         Inordervist(root);
18.         DeleteBst(&root,30);
19.         DeleteBst(&root,10);
20.         printf("Use inorder traversal method:\n");
21.         Inordervist(root);
22.         printf("Use postorder traversal method destroy Bst:\n");
23.         BTreedestroy(root);
24. }

结构如下：
Create Tree with key:10
Insert Key To Tree(right):20
Insert Key To Tree(right):40
Insert Key To Tree(left):5
Insert Key To Tree(left):1
Insert Key To Tree(left):-1
Insert Key To Tree(left):-20
Insert Key To Tree(right):100
Use inorder traversal method:
-20
-1
1
5
10
20
40
100
no delete data 30 find
........
delete data :10
........
Use inorder traversal method:
-20
-1
1
5
20
40
100
Use postorder traversal method destroy Bst:
Delete node for Key-20
Delete node for Key-1
Delete node for Key1
Delete node for Key100
Delete node for Key40
Delete node for Key20
Delete node for Key5

这里首先演示了建树，然后演示了中序遍历返回有序的结果，然后删除一个不包含的数据30，
然后删除一个包含的数据10，然后再次进行中序遍历，最后使用后续遍历删除。
可以看到结果如我们希望的。