二叉排序树

题目描述

二叉排序树的定义是：或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。 今天我们要判断两序列是否为同一二叉排序树

输入

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

输出

 

示例输入

2 123456789 987654321 432156789 0

示例输出

NO NO

提示

#include <iostream> #include <cstring> #include <cstdio> using namespace std; // BST的结点 typedef struct node { int data; struct node *lChild, *rChild; }Node, *BST; // 在给定的BST中插入结点，其数据域为element, 使之称为新的BST bool BSTInsert(Node * &p, int key) { if(NULL == p) // 空树 { p = new Node; p->data = key; p->lChild = p->rChild = NULL; return true; } if(key == p->data) // BST中不能有相等的值 return false; if(key < p->data) // 递归 return BSTInsert(p->lChild, key); return BSTInsert(p->rChild, key); // 递归 } // 建立BST void createBST(Node * &T, char str[], int n) { T = NULL; int i,x; for(i = 0; i < n; i++) { x=str[i]-'0'; BSTInsert(T, x); } } //比较T1,T2，是否相等； int bijiao (Node * &T,Node * &T1) { if(!T&&!T1) return 1; if(T->data==T1->data) { if(bijiao(T->lChild,T1->lChild)&&bijiao(T->rChild,T1->rChild)) return 1; else return 0; } else return 0; } int main() { int n,L1,L2,x; BST T,T1; char str[100],str1[100]; while(~scanf("%d",&n)&&n!=0) { scanf("%s",str); L1=strlen(str); createBST(T, str, L1); while(n--) { scanf("%s",str1); L2=strlen(str1); createBST(T1, str1, L2); x=bijiao(T,T1); if(x==1) cout<<"YES"<<endl; else cout<<"NO"<<endl; } } return 0; }