数据结构与算法-树的应用(三)-二叉排序树
二叉排序树是一棵特殊的二叉树，它是一棵二叉树但同时满足如下条件：对于树上任意一个结点，其上的数值必大于等于其左子树上任意结点数值，必小于等于其右子树上任意结点的数值。
二叉树的存储方式与二叉树保持一致，我们更多是关注它独有的操作。
我们从二叉树的插入开始了解其建树方式，对二叉排序树插入数字x:
- 若当前数为空，则x为其根节点
- 若当前结点大于x,则x插入其左子树；若当前结点小于x,则x插入其右子树；若当前结点等于x,则根据具体情况选择插入左右子树或者直接忽略。以插入4,2,6,1,3为例，其二叉排序树变化情况如下图
- 由于各个数字插入的顺序不同，所得到的二叉排序树的形态也很可能不同，所以不同的插入顺序对二叉排序树的形态有重要的影响。但是，所有的二叉排序树都有一个共同的特点：若对二叉排序树进行中序遍历，那么其遍历结果必然是一个递增序列，这也是二叉排序树的来由，通过建立二叉排序树就能对原无序序列进行排序，并实现动态维护。
题目描述：
输入一系列整数，建立二叉排序树，并进行前序，中序，后序遍历。
输入：
输入第一行包括一个整数n(1<=n<=100)。接下来的一行包括n个整数。
输出：
可能有多组测试数据，对于每组数据，将题目所给数据建立一个二叉排序树，并对二叉排序树进行前序，中序，和后序遍历。每种遍历结果输出一行。每行最后一个数据之后有一个空格。
样例输入：
5
1 6 5 9 8
样例输出：
1 6 5 9 8
1 5 6 8 9
5 8 9 6 1
代码如下：
#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
样例输入：
2
567432
543267
576342
0
样例输出：
YES
NO
代码如下：
#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;
}