二叉排序树 ##
题目
Problem Description
二叉排序树的定义是：或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。 今天我们要判断两序列是否为同一二叉排序树
Input
开始一个数n，(1<=n<=20) 表示有n个需要判断，n= 0 的时候输入结束。
接下去一行是一个序列，序列长度小于10，包含(0~9)的数字，没有重复数字，根据这个序列可以构造出一颗二叉排序树。
接下去的n行有n个序列，每个序列格式跟第一个序列一样，请判断这两个序列是否能组成同一颗二叉排序树。(数据保证不会有空树)
Output
Sample Input
2
123456789
987654321
432156789
0
Sample Output
NO
NO
分析&代码
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
using namespace std;
typedef struct node{
char data;
struct node *left;
struct node *right;
}BNode, *BTree;
bool flag;
string seq; //保存输入的数字序列
void Insert(BTree &bt, char ch){ //判断某一个数字应该插入到树的那一边
if(!bt){ //当第一次插入数字或者已经移动到正确插入的位置时候新建这个节点
bt = (BTree)malloc(sizeof(BNode));
bt->data = ch;
bt->left = NULL;
bt->right = NULL;
}
else if(ch < bt->data){
Insert(bt->left, ch);
}
else if(ch > bt->data){
Insert(bt->right, ch);
}
}
BTree Create(string seq){ //对每个数字都进行插入操作
BTree bt = NULL;
int len = seq.length();
for(int i=0; i<len; i++){
Insert(bt, seq[i]);
}
return bt;
}
void comp(BTree bt1, BTree bt2){ //比较，包括这几种情况
if(!bt1 && !bt2) //如果对应节点上都为空，则直接返回
return;
if(!bt1 || !bt2){ //如果只有一个为空，则将标志改变，这时候两棵树已经不同了，
flag = false; //返回（用else if 更清楚，但是因为两者都为空的时候已经判断过了，并且已经返回，所以不加else也不会有影响）
return;
}
if(bt1->data != bt2->data){
flag = false;
return;
}
comp(bt1->left, bt2->left); //递归左右子树
comp(bt1->right, bt2->right);
}
int main(){
int N;
while(cin>>N && N){
cin>>seq;
BTree bt1 = Create(seq);
while(N--){
cin>>seq;
BTree bt2 = Create(seq);
flag = true;
comp(bt1, bt2);
if(!flag)
cout<<"NO"<<endl;
else
cout<<"YES"<<endl;
}
}
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/116832.html
