C语言排序二叉树BST插入、删除和遍历_9,5,6的排序二叉树

一、什么是排序二叉树？

如果一个二叉树的节点都是一个孩子比自己大或空，另一个比自己小或空，这样的二叉树称为排序二叉树也就是BST。
那么这样就分两种情况了，一个是左孩子小，右孩子大，另一种情况是左孩子大右孩子小。
如图示：
两种情况都可以。
下面以第一种情况进行讨论，给出案例：

可以看出，不仅是一个节点的左孩子比自己小，左孩子的孩子也比自己小，以此类推。

二、怎么创建排序二叉树？

其实二叉树和双向链表差不多，都是保存一个数据和两个地址，不同点是双向链表保存的是自己的左节点和右节点地址，二叉树保存自己的两个子节点地址，因此定义为：

typedef struct Tree{
	int data;
	struct Tree *left;//左孩子
	struct Tree *right;//右孩子
}*Tree;
1
2
3
4
5

创建一个树首先的创建跟节点，开辟内存，将数据保存到data中，因为它现在还只是一个独立的节点，所以先将left和right都指向NULL。

Tree node;
node = GetNode(10);
1
2

Tree GetNode(int data){
	Tree node = (struct Tree *)malloc(sizeof(struct Tree));
	node->data = data;
	node->right = NULL;
	node->left = NULL;
	return node;
}
1
2
3
4
5
6
7

三、怎么按规则插入新节点？

规则是：比自己小，就做我的左孩子，比我大就做我的右孩子，因此在插入之前可以先进行数据比较，再选择插入位置。

Tree newn = GetNode(data[i]);
if(newn->data>node>data)
	node->right = new;
if(newn->data<node>data)
	node->left = new;
1
2
3
4
5

但是这样做出来的二叉树最多也就三个节点，假如将7、14依次插入完之后，如图：

再插入5，判断比10小，插到右边，直接将7断开，和5建立连接，不会将5插到7的后面，因此就要使用递归思想来解决这个问题。

Tree InsertNode(Tree node,Tree new){
	if(node==NULL)
		return NULL;
	if(new->data<node->data){
		if(InsertNode(node->left,new)==NULL)
			node->left = new;
	}
	if(new->data>node->data){
		if(InsertNode(node->right,new)==NULL)
			node->right = new;
	}
	return node;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

插入应该要插到没有节点的地方，因此递归结束的条件为node==NULL

if(node==NULL)
		return NULL;
1
2

如果不是NULL，说明这个节点存在，那就判断数据大小，新节点大于该节点，那就往右孩子那边插，以右孩子为基点继续找，直到发现一个节点为空，就做该节点的右孩子；新节点小于该节点，那就往左孩子那边插，以左孩子为基点继续找，直到发现一个节点为空，就做该节点的左孩子。
例如：在10 7 14节点的基础上插入5
InsertNode第一次调用：判断为空？不为空，5小于10？满足，将10的左孩子作为基点继续找；
InsertNode第二次调用：判断为空？不为空，5小于7？满足，将7的左孩子作为基点继续找；
InsertNode第三次调用：判断为空？为空，返回NULL;
回到第二次调用：返回等于NULL?满足，既然满足左孩子要求自己又没有左孩子那就做自己左孩子，然后返回7结点。
回到第二次调用：返回等于NULL?不满足，返回10节点。

再例如：在10 7 14 5节点的基础上，插入16
InsertNode第一次调用：判断为空？不为空，16小于10？不满足，16大于10？满足，将10的右孩子作为基点继续找；
InsertNode第二次调用：判断为空？不为空，16小于14？不满足，16大于14？满足，将14的右孩子作为基点继续找；
InsertNode第三次调用：判断为空？为空，返回NULL;
回到第二次调用：返回等于NULL?满足，既然满足右孩子要求自己又没有右孩子那就做自己右孩子，然后返回14结点。
回到第二次调用：返回等于NULL?不满足，返回10节点。*

四、怎么遍历排序二叉树？

二叉树的遍历根据根节点的遍历顺序分为三种，先序遍历、中序遍历和后序遍历。但遍历的整体方向都是一致的，就是从左到右。
先序遍历就是：先遍历根节点，再遍历左子数、右子树。
中序遍历就是：先遍历左子数、再遍历根节点、右子树。
后序遍历就是：先遍历左子树，再遍历右子树、根节点。
①先序遍历：

void ShowFirst(Tree node){
	if(node!=NULL){
		printf("%d\t",node->data);
		ShowFirst(node->left);
		ShowFirst(node->right);
	}
}
以遍历10 7 14为例：
1
2
3
4
5
6
7
8

运行过程如下：
ShowFirst第一次调用：
10节点等于NULL?不等于
先遍历根节点输出数据：10
再遍历左子树，传入左子树根节点：7

ShowFirst第二次调用：
7节点等于NULL?不等于
先遍历根节点输出数据：7
再遍历左子树，传入左子树根节点：NULL

ShowFirst第三次调用：
NULL等于NULL?等于
结束第三次调用

回到第二次调用状态：
开始遍历右子树，传入右子树根节点：NULL

ShowFirst第四次调用：
NULL节点等于NULL?等于
结束第四次调用
回到第二次调用状态：
没有语句了，结束第二次调用

回到第一次调用状态：
开始遍历右子树，传入右子树根节点：14

ShowFirst第四次调用：
14节点等于NULL?不等于
先遍历根节点输出数据：14
再遍历左子树，传入左子树根节点：NULL

ShowFirst第五次调用：
NULL节点等于NULL?等于
结束第五次调用

回到第四次调用：
开始遍历右子树，传入右子树根节点：NULL
ShowFirst第六次调用：
NULL节点等于NULL?等于
结束第六次调用

回到第二次调用状态：
没有语句了，结束第二次调用

回到第一次调用状态：
没有语句了，结束。

最后输出：10 7 14

用图表示一下调用次序：

②中序遍历

void ShowCent(Tree node){
	if(node!=NULL){
		ShowCent(node->left);
		printf("%d\t",node->data);
		ShowCent(node->right);
	}
}
1
2
3
4
5
6
7

不再详细叙述执行过程，读者可自行写出运行过程。
结果为：7 10 14

③后序遍历

void ShowLast(Tree node){
	if(node!=NULL){
		ShowLast(node->left);
		ShowLast(node->right);
		printf("%d\t",node->data);
	}
}
1
2
3
4
5
6
7

不再详细叙述执行过程，读者可自行写出运行过程。
结果为：7 14 10
总结一句话就是：递归和改变输出顺序。
以此类推，写出下图遍历顺序：

先序遍历：10 7 5 3 2 4 6 8 14 12 11 13 16 15 17
后序遍历：2 4 3 6 5 8 7 11 13 12 15 17 16 14 10
中序遍历：2 3 4 5 6 7 8 10 11 12 13 14 15 16 17

五、怎么删除节点？

在链表中，删除一个节点就得改变前后节点的指向，不能让后面的节点丢失；在排序二叉树中，删除一个节点，那么就要改变该节点的孩子节点的父节点，不能让孩子丢失。因此假如要删除上图的5节点，就得找个节点替换它。
既然排序二叉树有规则，然后替换的节点也得满足规则，在这个案例中也就是：父节点左孩子比自己小或空，右孩子比自己大或空。
又不能凭空捏造一个节点，只能从已有的节点挑选出一个替换要删除的节点，然后把这个节点free，怎么找到满足条件的节点呢？
分为三种情况
①要删除的节点没有孩子
没有孩子要托人照顾那么删除就直接free，赋值为NULL。

②要删除的节点只有一个孩子
直接让这个孩子继承自己的位置，为什么可以这样呢？
例如：只有左孩子

删除7节点，其节点只有左孩子5，让5代替7节点的位置。
分析：
5节点以下：因为5节点以下本身就是满足要求的，所以改变位置后也满足要求，；
5节点以上：5节点比10节点小吗？必须的！因为如果比10大根本就没有机会插在10左边，直接会在10节点右边找合适位置插入。

再例如：只有一个右孩子

删除14节点，其节点只有右孩子16，让16代替14节点的位置。
分析：
16节点以下：因为16节点以下本身就是满足要求的，所以改变位置后也满足要求，；
16节点以上：16节点比10节点大吗？必须的！因为如果比10小根本就没有机会插在10右边，直接会在10节点左边找合适位置插入。

③要删除的节点有两个孩子
有两种找法，首先我们要知道，一颗排序二叉树，最大的数在右子树的最右边，最小的数在左子树的最左边，如图最大为17，最小为2。

第一种，找到要删除数的右孩子，然后从右孩子找最左边的数，也就是右子树中最小的数，用来替换被删除的数。
如上图，要删除14，14右孩子为16,16节点最左边的数为15，用15代替14，并且free(15)。
为什么15满足要求呢？
因为15是14右子树（16 15 17）中最小的数，但又比14大，而14又比14左子树（12 11 13）都大，所以15也大于14左子树，既然该节点大于要删除的节点的左子树节点又小于要删除节点的右子树节点，那就正好满足条件。
实现代码：

temp = temp->right;
while(temp->left!=NULL){
 	parent = temp;
  temp = temp->left;
 }
 node->data = temp->data;
 free(temp);
 temp = NULL;
1
2
3
4
5
6
7
8

第二种，找到要删除数的左孩子，然后从左孩子找最右边的数，也就是左子树中最大的数，用来替换被删除的数。
如上图，要删除14，14左孩子为12,12节点最右边的数为13，用13代替14，并且free(13)。
为什么13满足要求呢？
因为13是14左子树（11 12 13）中最小的数，但又比14小，而14又比14右子树（16 15 17）都小，所以13也小于14左子树，既然该节点大于要删除的节点的左子树又小于要删除节点的右子树，那也满足条件。
代码类似，稍加改动，不再给出。

还有两个特别重要的问题：

①怎么找到要删除的节点
使用递归，如果该节点的数大于要删除节点的数，传入右孩子继续找，如果该节点的数小于要删除节点的数，传入左孩子继续找，直到等于就开始删除算法。

	if(node==NULL)
		return NULL;
	if(node->data>num)
		node->left = DeleteNode(node->left,num);
	else if(node->data<num){
		node->right = DeleteNode(node->right,num);
	}
1
2
3
4
5
6
7

②删除了不该删除的节点
这个问题很多博主都没有考虑到，如果按照第一种方法找到了替代的数，该替代数还有右孩子怎么办呢？如果按照第二种方法找到了替代的数，该替代数还有左孩子怎么办呢？如果不考虑，直接free掉，那就删掉了不该删除的节点。
解决办法还是递归，找到替代的节点，并且将替代节点的数赋值给要删除节点的数之后，如果替代的数还有右节点，再从要删除节点的右孩子（第二种方法是左孩子）出发，继续删。

  if(temp->right==NULL){
   	free(temp);
   	temp = NULL;
   }else{
   	node->right  = DeleteNode(node->right,node->data);
   }
1
2
3
4
5
6

六、完整代码

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
typedef struct Tree{
	int data;
	struct Tree *left;
	struct Tree *right;
}*Tree;
Tree GetNode(int data){
	Tree node = (struct Tree *)malloc(sizeof(struct Tree));
	node->data = data;
	node->right = NULL;
	node->left = NULL;
	return node;
}
Tree InsertNode(Tree node,Tree new){
	if(node==NULL)
		return NULL;
	if(new->data<node->data){
		if(InsertNode(node->left,new)==NULL)
			node->left = new;
	}
	if(new->data>node->data){
		if(InsertNode(node->right,new)==NULL)
			node->right = new;
	}
	return node;
}
Tree DeleteNode(Tree node,int num){
	Tree temp;
	if(node==NULL)
		return NULL;
	if(node->data>num)
		node->left = DeleteNode(node->left,num);
	else if(node->data<num){
		node->right = DeleteNode(node->right,num);
	}else{
		temp = node;
		if(temp->right==NULL&&temp->left==NULL){
			free(node);
			node = NULL;
		}else
			if(temp->right==NULL&&temp->left!=NULL){
				node = temp->left;
	        }
		    else
			    if(temp->right!=NULL&&temp->left==NULL){
				    node = temp->right;
				}
			    else{
			    	Tree parent = temp;
			    	int i = 0;//0代表下一个节点为右节点
		    		temp = temp->right;
			  	    while(temp->left!=NULL){
			  	    	parent = temp;
			  		    temp = temp->left;
			  		    i = 1;//下一个节点变成了左节点
			  	    }
			  	    node->data = temp->data;
			  	    if(temp->right==NULL){
			  	    	 temp = NULL;
				  	    if(i==0)
				  	        parent->right = NULL;
				  	    else
				  	    	parent->left = NULL;
			  	    }else{
			  	    	node->right  = DeleteNode(node->right,node->data);
			  	    }
			  	   
			  	   
			    }
	}
	return node;
}
void ShowLast(Tree node){
	if(node!=NULL){
		ShowLast(node->left);
		ShowLast(node->right);
		printf("%d\t",node->data);
	}
}
void ShowFirst(Tree node){
	if(node!=NULL){
		printf("%d\t",node->data);
		ShowFirst(node->left);
		ShowFirst(node->right);
	}
}
void ShowCent(Tree node){
	if(node!=NULL){
		ShowCent(node->left);
		printf("%d\t",node->data);
		ShowCent(node->right);
	}
}
int main(void){
	Tree node;
	int num;
	/*scanf("%d",&num);
	getchar();*/
	node = GetNode(10);
	int data[14] = {7,14,5,8,12,16,3,6,11,13,15,17,2,4};
	int i = 0;
	while(i!=14){
		//if(scanf("%d",&num)==1){
			Tree newn = GetNode(data[i]);
			//getchar();
			InsertNode(node,newn);
			printf("先序遍历：");
			ShowFirst(node);
			printf("\n");
			printf("后序遍历：");
			ShowLast(node);
			printf("\n");
			printf("中序遍历：");
			ShowCent(node);
			printf("\n");
		/*}
		else{
			getchar();
		    break;
		}*/
		i++;
	}
	while(1){
		printf("开始删除：\n");
		if(scanf("%d",&num)==1){
			getchar();
			node = DeleteNode(node,num);
			printf("先序遍历：");
			ShowFirst(node);
			printf("\n");
			printf("后序遍历：");
			ShowLast(node);
			printf("\n");
			printf("中序遍历：");
			ShowCent(node);
			printf("\n");
		}
		else
		  break;
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144

本来是手动输入直到输入字符结束输入的，后来改成了自动输入，不需要自动输入的读者可以修改代码。
到此结束！