Scott's world.

二叉搜索树的操作集

Word count: 1.2kReading time: 6 min
2019/07/26 Share

二叉搜索树的操作集

本题要求实现给定二叉搜索树的5种常用操作。

函数接口定义:

1
2
3
4
5
BinTree Insert( BinTree BST, ElementType X );
BinTree Delete( BinTree BST, ElementType X );
Position Find( BinTree BST, ElementType X );
Position FindMin( BinTree BST );
Position FindMax( BinTree BST );

其中BinTree结构定义如下:

1
2
3
4
5
6
7
typedef struct TNode *Position;
typedef Position BinTree;
struct TNode{
ElementType Data;
BinTree Left;
BinTree Right;
};
  • 函数InsertX插入二叉搜索树BST并返回结果树的根结点指针;
  • 函数DeleteX从二叉搜索树BST中删除,并返回结果树的根结点指针;如果X不在树中,则打印一行Not Found并返回原树的根结点指针;
  • 函数Find在二叉搜索树BST中找到X,返回该结点的指针;如果找不到则返回空指针;
  • 函数FindMin返回二叉搜索树BST中最小元结点的指针;
  • 函数FindMax返回二叉搜索树BST中最大元结点的指针。

裁判测试程序样例:

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
#include <stdio.h>
#include <stdlib.h>

typedef int ElementType;
typedef struct TNode *Position;
typedef Position BinTree;
struct TNode{
ElementType Data;
BinTree Left;
BinTree Right;
};

void PreorderTraversal( BinTree BT ); /* 先序遍历,由裁判实现,细节不表 */
void InorderTraversal( BinTree BT ); /* 中序遍历,由裁判实现,细节不表 */

BinTree Insert( BinTree BST, ElementType X );
BinTree Delete( BinTree BST, ElementType X );
Position Find( BinTree BST, ElementType X );
Position FindMin( BinTree BST );
Position FindMax( BinTree BST );

int main()
{
BinTree BST, MinP, MaxP, Tmp;
ElementType X;
int N, i;

BST = NULL;
scanf("%d", &N);
for ( i=0; i<N; i++ ) {
scanf("%d", &X);
BST = Insert(BST, X);
}
printf("Preorder:"); PreorderTraversal(BST); printf("\n");
MinP = FindMin(BST);
MaxP = FindMax(BST);
scanf("%d", &N);
for( i=0; i<N; i++ ) {
scanf("%d", &X);
Tmp = Find(BST, X);
if (Tmp == NULL) printf("%d is not found\n", X);
else {
printf("%d is found\n", Tmp->Data);
if (Tmp==MinP) printf("%d is the smallest key\n", Tmp->Data);
if (Tmp==MaxP) printf("%d is the largest key\n", Tmp->Data);
}
}
scanf("%d", &N);
for( i=0; i<N; i++ ) {
scanf("%d", &X);
BST = Delete(BST, X);
}
printf("Inorder:"); InorderTraversal(BST); printf("\n");

return 0;
}
/* 你的代码将被嵌在这里 */

输入样例:

1
2
3
4
5
6
10
5 8 6 2 4 1 0 10 9 7
5
6 3 10 0 5
5
5 7 0 10 3

输出样例:

1
2
3
4
5
6
7
8
9
10
Preorder: 5 2 1 0 4 8 6 7 10 9
6 is found
3 is not found
10 is found
10 is the largest key
0 is found
0 is the smallest key
5 is found
Not Found
Inorder: 1 2 4 6 8 9

答案

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
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
using namespace std;
typedef int ElementType;
typedef struct TNode *Position;
typedef Position BinTree;
struct TNode{
ElementType Data;
BinTree Left;
BinTree Right;
};

void PreorderTraversal( BinTree BT ); /* 先序遍历,由裁判实现,细节不表 */
void PreorderTraversal( BinTree BT )
{
if(BT)
{
printf("%d",BT->Data);
PreorderTraversal(BT->Left);
PreorderTraversal(BT->Right);
}
}
void InorderTraversal( BinTree BT ); /* 中序遍历,由裁判实现,细节不表 */
void InorderTraversal( BinTree BT )
{
if(BT)
{
InorderTraversal(BT->Left);
printf("%d",BT->Data);
InorderTraversal(BT->Right);
}
}

BinTree Insert( BinTree BST, ElementType X );
BinTree Delete( BinTree BST, ElementType X );
Position Find( BinTree BST, ElementType X );
Position FindMin( BinTree BST );
Position FindMax( BinTree BST );

int main()
{
BinTree BST, MinP, MaxP, Tmp;
ElementType X;
int N, i;

BST = NULL;
scanf("%d", &N);
for ( i=0; i<N; i++ ) {
scanf("%d", &X);
BST = Insert(BST, X);
}
printf("Preorder:"); PreorderTraversal(BST); printf("\n");
MinP = FindMin(BST);
MaxP = FindMax(BST);
scanf("%d", &N);
for( i=0; i<N; i++ ) {
scanf("%d", &X);
Tmp = Find(BST, X);
if (Tmp == NULL) printf("%d is not found\n", X);
else {
printf("%d is found\n", Tmp->Data);
if (Tmp==MinP) printf("%d is the smallest key\n", Tmp->Data);
if (Tmp==MaxP) printf("%d is the largest key\n", Tmp->Data);
}
}
scanf("%d", &N);
for( i=0; i<N; i++ ) {
scanf("%d", &X);
BST = Delete(BST, X);
}
printf("Inorder:"); InorderTraversal(BST); printf("\n");

return 0;
}
/* 你的代码将被嵌在这里 */
BinTree Insert( BinTree BST, ElementType X )
{
if(!BST)
{
BST=(Position)malloc(sizeof(struct TNode));
BST->Data=X;
BST->Left=BST->Right=NULL;
}
else
{
if(X<BST->Data) BST->Left=Insert(BST->Left,X);
else if(X>BST->Data) BST->Right=Insert(BST->Right,X);
}
return BST;
}

BinTree Delete( BinTree BST, ElementType X )
{
Position Tmp;
if(!BST) cout<<"Not Found"<<endl;
else if(X<BST->Data) BST->Left=Delete(BST->Left,X); //根据大小在左子树递归删除
else if(X>BST->Data) BST->Right=Delete(BST->Right,X); //根据大小在右子树递归删除
else //找到要删除的结点
{
//有左右子树的结点
if(BST->Left && BST->Right)
{
//取该结点右子树最小元素
Tmp=FindMin(BST->Right);
BST->Data=Tmp->Data;
//删除该结点的右子树中最小元素
BST->Right=Delete(BST->Right,BST->Data);
}
else //被删除的结点只有一个或无孩子结点
{
Tmp=BST;
if(!BST->Left) //有右孩子或无孩子
BST=BST->Right;
else if(!BST->Right) //有左孩子或无孩子
BST=BST->Left;
free(Tmp);
}
}
return BST;
}
Position Find( BinTree BST, ElementType X )
{
while(BST)
{
if(X>BST->Data)BST=BST->Right;
else if(X<BST->Data)BST=BST->Left;
else return BST;
}
return NULL;
}
Position FindMin( BinTree BST )
{
if(!BST) return NULL;
else if (!BST->Left) return BST; //找到最左叶结点并返回
else return FindMin(BST->Left); //沿左分支继续查找
}
Position FindMax( BinTree BST )
{
if(BST)
while(BST->Right) BST=BST->Right; //沿右分支继续查找直至最右叶结点
return BST;
}
CATALOG
  1. 1. 二叉搜索树的操作集
    1. 1.0.1. 函数接口定义:
    2. 1.0.2. 裁判测试程序样例:
    3. 1.0.3. 输入样例:
    4. 1.0.4. 输出样例:
  2. 1.1. 答案