二叉排序树（也称二叉查找树）或者是一棵空树，或者是具有下列特性的二叉树：1）若左子树非空，则左子树上所有结点的值均小于根结点的值。2）若右子树非空，则右子树上所有结点的值均大于根结点的值。3）左、右子树也分别是一棵二叉排序树。2022 年考研 408 的数据结构大题就考察了二叉排序树的 C 语言实现。以下为我在学习和实战练习过程中所做的笔记，可供参考。
一、二叉排序树的结构
网站演示
树结点数据结构：
1
2
3
4
5
| typedef int KeyType;
typedef struct BSTNode{
KeyType key;
struct BSTNode *lchild,*rchild;
}BSTNode,*BiTree;
|
二叉排序树的创建，中序遍历，查找，删除：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| int main()
{
BiTree T;
BiTree parent;
BiTree search;
KeyType str[]={54,20,66,40,28,79,58};
Creat_BST(T,str,7);
InOrder(T);
printf("\n");
search=BST_Search(T,40,parent);
if(search)
{
printf("找到对应结点，值=%d\n",search->key);
}else{
printf("未找到对应结点\n");
}
DeleteNode(T,66);
InOrder(T);
printf("\n");
system("pause");
}
|
二、二叉排序树的操作
创建二叉排序树：
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
| int BST_Insert(BiTree &T,KeyType k)
{
if(NULL==T)
{
T=(BiTree)malloc(sizeof(BSTNode));
T->key=k;
T->lchild=T->rchild=NULL;
return 1;
}
else if(k==T->key)
return 0;
else if(k<T->key)
return BST_Insert(T->lchild,k);
else
return BST_Insert(T->rchild,k);
}
void Creat_BST(BiTree &T,KeyType str[],int n)
{
T=NULL;
int i=0;
while(i<n)
{
BST_Insert(T,str[i]);
i++;
}
}
|
查找结点：
1
2
3
4
5
6
7
8
9
10
11
| BSTNode *BST_Search(BiTree T,KeyType key,BiTree &p)
{
p=NULL;
while(T!=NULL&&key!=T->key)
{
p=T;
if(key<T->key) T=T->lchild;
else T=T->rchild;
}
return T;
}
|
删除结点：
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
| void DeleteNode(BiTree &root,KeyType x){
if(root == NULL){
return;
}
if(root->key>x){
DeleteNode(root->lchild,x);
}else if(root->key<x){
DeleteNode(root->rchild,x);
}else{
if(root->lchild == NULL){
BiTree tempNode = root;
root = root->rchild;
free(tempNode);
}else if(root->rchild == NULL){
BiTree tempNode = root;
root = root->lchild;
free(tempNode);
}else{
BiTree tempNode = root->lchild;
if(tempNode->rchild!=NULL){
tempNode = tempNode->rchild;
}
root->key = tempNode->key;
DeleteNode(root->lchild,tempNode->key);
}
}
}
|
中序遍历：
1
2
3
4
5
6
7
8
9
| void InOrder(BiTree T)
{
if(T!=NULL)
{
InOrder(T->lchild);
printf("%3d",T->key);
InOrder(T->rchild);
}
}
|