课后习题-查找

还不到11点,竟然有些困意了,其实自己还没有完全整理好,不过任务大致完成了,今天就提交一次,充个绿点吧,毕竟昨天停了一天电,不得已还是断节了,如果可以的话,还是希望自己能够将其保持下去,加油。

7.22:完善中…

先将问题独立出来大致分析一番思路。

问题1:如何判定一棵树是不是二叉排序树

思路:根据二叉排序树中序遍历结果为增序的特性,可以设置一个flag,在中序遍历过程中将当前遍历结点与其前驱结点进行大小比较,即可得出结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void Judge(BSTree T,int &flag)  {
//采用引用传递,将flag变化后的值传回到主函数中
//int flag=1; //主函数中定义flag变量并初始化为1
static BSTNode *pre=NULL;
//定义前驱结点指针,初始化为NULL(至于为何用static还不太清楚)
if (T&&flag) {
Judge(T->lchild,flag);
if (pre==NULL)
pre=T; //pre为空时是遍历的第一个结点,将其指向当前指针
else if (pre=>data.key<T->data.key) //满足二叉排序树特点,前驱结点值小于当前结点值
pre=T; //将前驱指针指向当前结点
else
flag=0; //flag=0时,不是二叉排序树
Judge(T->rchild,flag);
}
}

问题2:从小到大输出一棵二叉排序树中所有数据值>=x的结点的数据

思路:二叉排序树中序遍历即是增序,所以我们可以简单修改一下输出条件,当满足结点数据值>=x时输出,遍历结束后输出的值即是从小到大排列。

1
2
3
4
5
6
7
8
void InorderTraverse(BSTree &T,char x)  {
if (T) {
InorderTraverse(T->lchild,x);
if (T->data.key>=x)
cout<<T->data.key;
InorderTraverse(T->rchild,x);
}
}

和自己希望得类似,将其代入到实例中具体编译运行了一番,具体代码如下。

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
#include <iostream>
using namespace std;

typedef struct ElemType {
char key;
}ElemType; //数据域类型

typedef struct BSTNode {
ElemType data; //数据域
BSTNode *lchild,*rchild; //指针域
}BSTNode,*BSTree;

//先序遍历方式创建二叉树
void CreateBSTree(BSTree &T) {
ElemType e;
cin>>e.key;
if (e.key=='#') T=NULL;
else {
T=new BSTNode;
T->data.key=e.key;
CreateBSTree(T->lchild);
CreateBSTree(T->rchild);
}
}

//中序遍历二叉树
void InOrderTraverse(BSTree &T) {
if (T) {
InOrderTraverse(T->lchild);
cout<<T->data.key;
InOrderTraverse(T->rchild);
}
}

//判断是否为二叉排序树
void Judge(BSTree T,int &flag) {
static BSTNode *pre=NULL;
if (T&&flag) {
Judge(T->lchild,flag);
if (pre==NULL) pre=T;
else if (pre->data.key<T->data.key) //满足前驱结点值小于当前结点值
pre=T; //将前驱指针指向当前结点
else
flag=0;
Judge(T->rchild,flag);
}
}

//生成二叉排序树
void CreateBST(BSTree &T) {
void InsertBST(BSTree &T,ElemType e); //不知为何还要声明
T=NULL;
ElemType e;
cin>>e.key;
while (e.key!='#') {
InsertBST(T,e);
cin>>e.key;
}
}

//二叉排序树插入
void InsertBST(BSTree &T,ElemType e) {
if (!T) { //找到插入位置
BSTree S=new BSTNode;
S->data=e;
S->lchild=S->rchild=NULL;
T=S;
}
else if (e.key<T->data.key)
InsertBST(T->lchild,e);
else if (e.key>T->data.key)
InsertBST(T->rchild,e);
}

//输出所有数据值>=x的数据
void InorderTraverse(BSTree &T,char x) {
if (T) {
InorderTraverse(T->lchild,x);
if (T->data.key>=x)
cout<<T->data.key;
InorderTraverse(T->rchild,x);
}
}

int main() {
BSTree T;
int flag=1;
//先序遍历方式创建二叉树
CreateBSTree(T);
//判断二叉树是否为二叉排序树
Judge(T,flag);
if (flag)
cout<<"是二叉排序树"<<endl;
else
cout<<"不是二叉排序树"<<endl;

cout<<"请输入若干字符,用回车区分,以#结束输入,来创建二叉排序树"<<endl;
CreateBST(T);
cout<<"从小到大输出二叉排序树中所有数据值>=x的结点数据"<<endl;
char x;
cin>>x;
InorderTraverse(T,x);
}
-------------The End-------------