问题 B: 进击的二叉查找树

题目描述

给定1~N的两个排列，使用这两个排列分别构建两棵二叉查找树（也就是通过往一棵空树中依次插入序列元素的构建方式）。如果这两棵二叉查找树完全相同，那么输出YES；否则输出NO。之后，输出第一个排列对应的二叉查找树的后序序列、层序序列。

输入

每个输入文件中一组数据。

第一行1个正整数N（1<=N<=30），表示二叉查找树中的结点个数。

接下来两行，代表1~N的两个排列。

输出

如果两个排列代表的二叉查找树完全相同，那么输出一行YES，否则输出一行NO。

接下来两行分别输出第一个排列对应的二叉查找树的后序序列、层序序列，整数之间用空格隔开。

每行末尾不允许有多余的空格。

样例输入

5 4 2 1 3 5 4 5 2 3 1

样例输出

YES 1 3 2 5 4 4 2 5 1 3 #include<iostream> #include<queue> #include<stdlib.h>//molloc需要 using namespace std; typedef struct BiTNode{ int value; struct BiTNode *lchild; struct BiTNode *rchild; }BiTNode,*BiTree; //一个指向该类型的指针 //后文中用BiTree定义的都是指针，才可以判断是不是NULL queue<BiTree> Q; int flag; void postOrder(BiTree t){//传入的是指向BiTNode的指针，即BiTree类型 if(t!=NULL){ postOrder(t->lchild); postOrder(t->rchild); if(flag==false){ cout<<t->value; flag = true; } else{ cout<<" "<<t->value; } } } void levelOrder(BiTree t){ while(!Q.empty()) Q.pop(); Q.push(t); while(!Q.empty()){ BiTree tmpt = Q.front(); Q.pop(); if(flag==false){ cout<<tmpt->value; flag = true; } else{ cout<<" "<<tmpt->value; } if(tmpt->lchild) Q.push(tmpt->lchild); if(tmpt->rchild) Q.push(tmpt->rchild); } } int BST_insert(BiTree &T,int x){ if(T==NULL){ T = (BiTree)malloc(sizeof(BiTNode)); T->value = x; T->lchild = T->rchild = NULL; } else if(x == T->value) return 0; else if(x<T->value){ return BST_insert(T->lchild,x); } else return BST_insert(T->rchild,x); } void creat_BST(BiTree &T,int num[],int n){//若要改变树中的结构或值，则要使用引用 T=NULL; int i=0; while(i<n){ BST_insert(T,num[i]); i++; } } int compTree(BiTree T1,BiTree T2){ if(T1 == NULL && T2 == NULL) //两子树都为空，则暂时相等。 return 1; if(T1 != NULL && T2 != NULL){//或者两者都不为空，可以进行下一步比较 if(T1->value == T2->value){//两者值相等，则进一步递归子树的比较情况 if(compTree(T1->lchild,T2->lchild) && compTree(T1->rchild,T2->rchild)){ return 1; } } } //存在一边为空的情况，则返回不一样 return 0; } int main(){ int n; int num1[32]; int num2[32]; BiTree T1 = (BiTree)malloc(sizeof(BiTNode));//由于BiTree类型本身就已经是指针，故无需再加上* BiTree T2 = (BiTree)malloc(sizeof(BiTNode)); while(scanf("%d",&n)!=EOF){ for(int i=0;i<n;i++){ cin>>num1[i]; } for(int i=0;i<n;i++){ cin>>num2[i]; } creat_BST(T1,num1,n); creat_BST(T2,num2,n); if(compTree(T1,T2)){ cout<<"YES"<<endl; } else{ cout<<"NO"<<endl; } flag =false; postOrder(T1); flag =false; cout<<endl; levelOrder(T1); } return 0; }