二叉排序树的创建，插入及删除 - C语言_编程实现二叉排序树,包括生成,插入、删除;

这里的二叉排序树的创建是根据课本上写的，其中掺杂了递归思想，之前的写的二叉树的创建是为非递归的方法https://blog.csdn.net/qq_43402544/article/details/109228383。
完整代码如下：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct//关键字结构体 
{
	int key;//关键字项 
	int otherinfo;//其他数据域 
}ElemType;//每个节点的数据域的类型 
typedef struct BSTNode//二叉树结构体 
{
	ElemType data;//每个节点的数据域包括关键字项和其他数据项 
	struct BSTNode *lchild,*rchild;//左右孩子指针 
}BSTNode,*BSTree;

void InitTree(BSTree &T)//初始化二叉排序树 
{
	T = (BSTNode*)malloc(sizeof(BSTNode));//创建一个头结点 
	T->data.key = NULL;
	T->lchild = T->rchild = NULL;//头结点指针域和数据域都NULL 
}

void InsertTree(BSTree &T,int e)//二叉排序树的插入 
{
	if(!T)//找到插入位置，递归结束 
	{
		BSTree S;
		S = (BSTNode *)malloc(sizeof(BSTNode));//创建一个结点
		S->data.key = e;//新结点的数据置为e 
		S->lchild = S->rchild = NULL;//新结点设置为叶子结点 
		T = S;//把新结点S接到已找到的插入位置 
	}
	else if(e<T->data.key)
		InsertTree(T->lchild,e);//将S插入左子树 
	else
		InsertTree(T->rchild,e);//将S插入右子树 
} 

void CreateTree(BSTree &T)//创建二叉排序树 
{
	int a;
	printf("请输入：");
	scanf("%d",&a);
	T->data.key = a;//将数据填入二叉排序树的根结点 
	while(1)//利用循环进行插入操作 
	{
		scanf("%d",&a);
		InsertTree(T,a);//将数据导入到二叉排序树T中 
		if(getchar()=='\n')//死循环结束条件 
			break;
	}
}

void InOrderTraverse(BSTree T)//遍历二叉树，中序遍历 
{
	if(T)//递归终止条件是T为NULL  
	{
		InOrderTraverse(T->lchild);//中序遍历左子树 
		printf("%d ",T->data);//输出打印根结点 
		InOrderTraverse(T->rchild);//中序遍历右子树 
	}
}

int SearchTree(BSTree T,int key)//二叉排序树的查找，这里的查找只能知道二叉树中有没有和key相等的值 
{
	if(T == NULL)//查找结束，且没有和key相等的值 
		return 0;
	else if(T->data.key==key)//查找结束，二叉树中有和key相等的值 
		return T->data.key;	
	else if(key<T->data.key)
		return SearchTree(T->lchild,key);//递归左子树 
	else
		return SearchTree(T->rchild,key);//递归右子树 
}

void DeleteTree(BSTree &T,int key)//从二叉排序树T中删除关键字等于key的结点  ,这里分三种情况进行讨论 
{
	BSTree f,p;
	p = T;
	f = NULL;//初始化 
	while(p)//利用循环找到关键字等于key的结点
	{
		if(p->data.key == key)//找到关键字等于key的结点，并跳出循环 
			break;
		f = p;//结点f一直为结点p的双亲结点 
		if(p->data.key>key)
			p = p->lchild;//在p的左子树中继续查找 
		else
			p = p->rchild;//在p的右子树中继续查找 
	}
	if(p == NULL)//找不到被删除的结点则返回 
	{
		printf("没有找到要删除的值！\n");
		return ; 
	}
	/*第一种情况：被删除的结点（包含被删除的结点是根结点）的左右子树都存在，在其左子树上找中序最后一个结点填补*/ 
	BSTree q,s;
	if((p->lchild)&&(p->rchild))//被删结点p左右子树均不空 
	{
		q = p;
		s = p->rchild;
		while(s->rchild)//在结点p的左子树中继续查找其前驱结点,即最右下结点 
		{
			q = s;
			s = s->rchild;//向右到尽头 
		}
		p->data = s->data;//结点s中的数据顶替被删结点p中的 
		if(q != p)//重新连接结点q的右子树 
			q->rchild = s->lchild;
		else//重新连接结点q的左子树 
			q->lchild = s->lchild;
		free(s);//释放s 
		return ;//结束该函数 
	}
	/*第二种情况：被删结点(包含根结点)缺右子树，且包含左右子树都缺（即叶子结点）；缺右子树用左孩子填补*/
	else if(p->rchild == NULL)//被删结点缺右子树 
	{
		if(f)//判断被删结点是否为根结点，若是则f==NULL 
		{
			if(f->lchild == p)//判断被删结点的双亲结点的左孩子是否为p 
			{
				f->lchild = p->lchild;
				p->lchild = NULL;
			}
			else//被删结点的双亲结点的右孩子为p 
			{
				f->rchild = p->lchild;
				p->lchild = NULL;
			}
			free(p);//释放结点p 
			return ;//结束该函数 
		}
		else//被删结点为根结点 
		{
			f = p;
			p = p->lchild;
			f->lchild = NULL;
			free(f);//释放根结点 
			T = p;//根结点移位 
			return ;
		}
	}
	/*第三种情况：被删结点(包含根结点)缺左子树，且包含左右子树都缺（即叶子结点）；缺左子树用右孩子填补*/
	else	//	else if(p->lchild == NULL)//被删结点缺左子树 
	{
		if(f)//判断被删结点是否为根结点，若是则f==NULL 
		{
			if(f->lchild == p)//判断被删结点的双亲结点的左孩子是否为p 
			{
				f->lchild = p->rchild;
				p->rchild = NULL;
			}
			else//被删结点的双亲结点的右孩子为p 
			{
				f->rchild = p->rchild;
				p->rchild = NULL;
			}
			free(p);//释放结点p
			return ;//结束该函数 
		}
		else//被删结点为根结点 
		{
			f = p;
			p = p->rchild;
			f->lchild = NULL;
			free(f);//释放根结点 
			T = p;//根结点移位 
			return ;//结束该函数 
		}
	}
}

int main()
{
	BSTree T;
	InitTree(T);//初始化二叉排序树 
	CreateTree(T);//创建二叉排序树 
	InOrderTraverse(T);//打印 
	printf("\n");
	if(SearchTree(T,16))//判断二叉排序树中是否存在关键字与key相等的结点 ，其中的16是测试值，可换变量 
		printf("存在：%d\n",SearchTree(T,16));
	else
		printf("不存在！\n"); 
	DeleteTree(T,16);//二叉排序树的删除，删除与key相等的结点，其中的数值为测试值 
	printf("删除之后："); 
	InOrderTraverse(T);//再次打印结果，验证删除是否成功 
	free(T);
	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
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189

结果演示：