Fork me on GitHub

数据结构与算法-树的应用(三)-二叉排序树


数据结构与算法-树的应用(三)-二叉排序树

​ 二叉排序树是一棵特殊的二叉树,它是一棵二叉树但同时满足如下条件:对于树上任意一个结点,其上的数值必大于等于其左子树上任意结点数值,必小于等于其右子树上任意结点的数值。

​ 二叉树的存储方式与二叉树保持一致,我们更多是关注它独有的操作。

​ 我们从二叉树的插入开始了解其建树方式,对二叉排序树插入数字x:

  1. 若当前数为空,则x为其根节点
  2. 若当前结点大于x,则x插入其左子树;若当前结点小于x,则x插入其右子树;若当前结点等于x,则根据具体情况选择插入左右子树或者直接忽略。以插入4,2,6,1,,3为例,其二叉排序树变化情况如下图
  3. 由于各个数字插入的顺序不同,所得到的二叉排序树的形态也很可能不同,所以不同的插入顺序对二叉排序树的形态有重要的影响。但是,所有的二叉排序树都有一个共同的特点:若对二叉排序树进行中序遍历,那么其遍历结果必然是一个递增序列,这也是二叉排序树的来由,通过建立二叉排序树就能对原无序序列进行排序,并实现动态维护。

题目描述:

​ 输入一系列整数,建立二叉排序树,并进行前序,中序,后序遍历。

输入:

​ 输入第一行包括一个整数n(1<=n<=100)。接下来的一行包括n个整数。

输出:

​ 可能有多组测试数据,对于每组数据,将题目所给数据建立一个二叉排序树,并对二叉排序树进行前序,中序,和后序遍历。每种遍历结果输出一行。每行最后一个数据之后有一个空格。

样例输入:

1
2
5
1 6 5 9 8

样例输出:

1
2
3
1 6 5 9 8
1 5 6 8 9
5 8 9 6 1

代码如下:

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
#include <iostream>
#include <cstdio>

using namespace std;

struct TNode{// 定义树的结构体
int data;
struct TNode *lchild;
struct TNode *rchild;
}Tree[120];

int loc = 0;
TNode* create(){// 创建新的结点
Tree[loc].lchild = Tree[loc].rchild = NULL;
return &Tree[loc++];
}

TNode* insert(TNode *T,int x){
// 按照二叉排序树的定义进行插入
if(T == NULL){
T = create();
T->data = x;
return T;
}else if(x < T->data){
T->lchild = insert(T->lchild,x);
}else if(x > T->data){
T->rchild = insert(T->rchild,x);
}
return T;
}

void preOrder(TNode *T){// 前序遍历
if(T != NULL){
printf("%d ",T->data);
preOrder(T->lchild);
preOrder(T->rchild);
}
}

void inOrder(TNode *T){// 中序遍历
if(T != NULL){
inOrder(T->lchild);
printf("%d ",T->data);
inOrder(T->rchild);
}
}

void postOrder(TNode *T){// 后序遍历
if(T != NULL){
postOrder(T->lchild);
postOrder(T->rchild);
printf("%d ",T->data);
}
}
int main(void){

int n;
while(scanf("%d",&n)!=EOF){
TNode *root = NULL;
for(int i = 0 ; i < n ; i++){
int x;
scanf("%d",&x);
root = insert(root,x);
}

preOrder(root);
cout<<endl;
inOrder(root);
cout<<endl;
postOrder(root);
cout<<endl;
}
return 0;
}

运行结果:

二叉搜索树

​ 在学习了二叉排序树的建立和三种方式的遍历以后,我们还要接触一种特殊的树操作-判断两颗二叉树是否相同。

​ 判断两颗树是否相同,我们不能简单地用某一种遍历方式去遍历两棵树,我们只需对两棵树进行包括中序遍历在内的两种遍历,若两种遍历的结果都相同,那么就可以判定两棵树是完全相同的。

题目描述:

​ 判断两序列是否为同一二叉搜索树序列

输入:

​ 开始一个数n,(1<=n<=20)表示有n个需要判断,n = 0的时候输入结束。接下来一行是一个序列,序列的长度小于10,包含该(0~9)的数字,没有重复的数字,根据这个序列可以构造出一棵二叉搜索树。
​ 接下去的n行有n个序列,每个序列格式跟第一个序列一样,请判断这两个序列是否能组成同一颗二叉搜索树。

输出:

​ 如果序列相同则输出YES,否则输出NO

样例输入:

1
2
3
4
5
2
567432
543267
576342
0

样例输出:

1
2
YES
NO

代码如下:

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
#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

struct TNode{
int data;
struct TNode *lchild;
struct TNode *rchild;
}Tree[20];

int loc = 0;

TNode *create(){
Tree[loc].lchild = Tree[loc].rchild = NULL;
return &Tree[loc++];
}

TNode *insert(TNode *T,int x){
if(T == NULL){
T = create();
T->data = x;
return T;
}else if(T->data > x){
T->lchild = insert(T->lchild,x);
}else if(T->data < x){
T->rchild = insert(T->rchild,x);
}
return T;
}

char str1[20];
int len1 = 0;
char str2[20];
int len2 = 0;
char *str;
int *len;

void preOrder(TNode *T){
if(T != NULL){
str[(*len)++] = T->data+'0';
preOrder(T->lchild);
preOrder(T->rchild);
}
}

void inOrder(TNode *T){
if(T != NULL){
inOrder(T->lchild);
str[(*len)++] = T->data+'0';
inOrder(T->rchild);
}
}

int main(){
int n;

while(scanf("%d",&n)!=EOF && n){
TNode *T1 = NULL;
char tmp[20];
scanf("%s",tmp);
for(int i = 0 ; tmp[i]!='\0' ; i++){
T1 = insert(T1,tmp[i]-'0');
}
str=str1;
len = &len1;
preOrder(T1);
inOrder(T1);
str1[len1] = '\0';
while(n--){
TNode *T2 = NULL;
char tmp2[20];
scanf("%s",tmp2);
for(int i = 0 ; tmp2[i]!='\0' ; i++){
T2 = insert(T2,tmp2[i]-'0');
}
str=str2;
len = &len2;
preOrder(T2);
inOrder(T2);
str2[len2] = '\0';
if(strcmp(str1,str2) == 0){
cout<<"YES"<<endl;
}else{
cout<<"NO"<<endl;
}
}
}

return 0;
}

运行结果:

坚持原创技术分享,您的支持将鼓励我继续创作
-------------本文结束感谢您的阅读-------------
0%