L2-004. 这是二叉搜索树吗？
陈越
一棵二叉搜索树可被递归地定义为具有下列性质的二叉树：对于任一结点，
其左子树中所有结点的键值小于该结点的键值；
其右子树中所有结点的键值大于等于该结点的键值；
其左右子树都是二叉搜索树。
所谓二叉搜索树的“镜像”，即将所有结点的左右子树对换位置后所得到的树。
给定一个整数键值序列，现请你编写程序，判断这是否是对一棵二叉搜索树或其镜像进行前序遍历的结果。
输入格式：
输入的第一行给出正整数N（<=1000）。随后一行给出N个整数键值，其间以空格分隔。
输出格式：
如果输入序列是对一棵二叉搜索树或其镜像进行前序遍历的结果，则首先在一行中输出“YES”，然后在下一行输出该树后序遍历的结果。数字间有1个空格，一行的首尾不得有多余空格。若答案是否，则输出“NO”。
输入样例1：
7
8 6 5 7 10 8 11
输出样例1：
YES
5 7 6 8 11 10 8
输入样例2：
7
8 10 11 8 6 7 5
输出样例2：
YES
11 8 10 7 5 6 8
输入样例3：
7
8 6 8 5 10 9 11
输出样例3：
NO
思路：根据题意 首先根据最原始的搜索二叉树的方法建树，然后再根据镜像二叉树的方法建树，最后再对这两棵树进行先序遍历，如果其中有一个和题中给出序列一样就输出它的后续遍历结果否则输出NO
#include <stdio.h>
#include <malloc.h>
#include <iostream>
using namespace std;
typedef char InfoType[10];
typedef struct node /*记录类型*/
{
int key; /*关键字项*//*其他数据域*/
struct node *lchild,*rchild; /*左右孩子指针*/
} BSTNode;
int b[1005],c[1005],t=0,s=0;
int b1[1005],c1[1005],t1=0,s1=0;
int InsertBST(BSTNode *&p,int k)
{
if (p==NULL) /*原树为空, 新插入的记录为根结点*/
{
p=(BSTNode *)malloc(sizeof(BSTNode));
p->key=k;
p->lchild=p->rchild=NULL;
return 1;
}
else if (k<p->key)
return InsertBST(p->lchild,k); /*插入到*p的左子树中*/
else
return InsertBST(p->rchild,k); /*插入到*p的右子树中*/
}
BSTNode *CreateBST(int A[],int n) /*返回BST树根结点指针*/
{
BSTNode *bt=NULL; /*初始时bt为空树*/
int i=0;
while (i<n)
{
InsertBST(bt,A[i]); /*将关键字A[i]插入二叉排序树T中*/
i++;
}
return bt; /*返回建立的二叉排序树的根指针*/
}
int InsertBST1(BSTNode *&p,int k)
{
if (p==NULL) /*原树为空, 新插入的记录为根结点*/
{
p=(BSTNode *)malloc(sizeof(BSTNode));
p->key=k;
p->lchild=p->rchild=NULL;
return 1;
}
else if (k<p->key)
return InsertBST1(p->rchild,k); /*插入到*p的左子树中*/
else
return InsertBST1(p->lchild,k); /*插入到*p的右子树中*/
}
BSTNode *CreateBST1(int A[],int n) /*返回BST树根结点指针*/
{
BSTNode *bt1=NULL; /*初始时bt为空树*/
int i=0;
while (i<n)
{
InsertBST1(bt1,A[i]); /*将关键字A[i]插入二叉排序树T中*/
i++;
}
return bt1; /*返回建立的二叉排序树的根指针*/
}
void PreOrder(BSTNode * bt)//先序遍历二叉树
{
if(bt!=NULL)
{
//printf("%d ",bt->key);
b[t++]=bt->key;
PreOrder(bt->lchild);
PreOrder(bt->rchild);
}
}
void PostOrder(BSTNode * bt)//后续遍历二叉树
{
if(bt!=NULL)
{
PostOrder(bt->lchild);
PostOrder(bt->rchild);
c[s++]=bt->key;
}
}
int main()
{
BSTNode *bt,*bt1;
int n,a[1005],ans=0,ans1=0;
int flag=0;
cin>>n;
for(int i=0; i<n; i++)
cin>>a[i];
bt=CreateBST(a,n);
PreOrder(bt);
for(int i=0; i<n; i++)
if(a[i]==b[i])
ans++;
if(ans==n)
{
flag=1;
cout<<"YES"<<endl;
PostOrder(bt);
for(int i=0; i<n; i++)
{
if(i==0)
cout<<c[i];
else
cout<<" "<<c[i];
}
cout<<endl;
}
if(flag==0)
{
t=0;
bt1=CreateBST1(a,n);
PreOrder(bt1);
for(int i=0; i<n; i++)
if(a[i]==b[i])
ans1++;
if(ans1==n)
{flag=1;
cout<<"YES"<<endl;s=0;
PostOrder(bt1);
for(int i=0; i<n; i++)
{
if(i==0)
cout<<c[i];
else
cout<<" "<<c[i];
}cout<<endl;
}
}
if(flag==0)
cout<<"NO"<<endl;
return 0;
}L2-006. 树的遍历
给定一棵二叉树的后序遍历和中序遍历，请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。
输入格式：
输入第一行给出一个正整数N（<=30），是二叉树中结点的个数。第二行给出其后序遍历序列。第三行给出其中序遍历序列。数字间以空格分隔。
输出格式：
在一行中输出该树的层序遍历的序列。数字间以1个空格分隔，行首尾不得有多余空格。
输入样例：
7
2 3 1 5 7 6 4
1 2 3 4 5 6 7
输出样例：
4 1 6 3 5 7 2
解题思路；学过数据结构的人都知道知道中序遍历和先序或后序遍历可以唯一确定一颗二叉树，所以我们只需要构建出书然后进行层次遍历就OK了。
#include <iostream>
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
struct BTNode
{
int key;
BTNode *lchild,*rchild;
};
BTNode *CreateBTNode(int a[],int b[],int n)//a表示后序遍历，b表示中序遍历，每次取后序的最后一个节点，以它为分界点将中序分成两部分，然后在对每部分进行相同的操作。
{
BTNode *bt;
bt=(BTNode*)malloc(sizeof(BTNode));
int t,temp1[35],temp2[35],i,k;
if(n<=0)
return NULL;
t=a[n-1];
bt->key=t;
for(i=0;i<n;i++)
if(b[i]==t)
break;
k=0;
for(int j=i+1;j<n;j++)
temp2[k++]=b[j];
k=0;
for(int j=i;j<n-1;j++)
temp1[k++]=a[j];
bt->lchild=CreateBTNode(a,b,i);
bt->rchild=CreateBTNode(temp1,temp2,n-i-1);
return bt;
}
int c[35],tt;
void LevelOrder(BTNode *bt)//借助队列对树进行中序遍历
{
queue<BTNode*> Q;
BTNode *p;
Q.push(bt);
while(!Q.empty())
{
p=Q.front();
c[tt++]=p->key;
Q.pop();
if(p->lchild)
Q.push(p->lchild);
if(p->rchild)
Q.push(p->rchild);
}
}
int main()
{
int n,a[35],b[35];
BTNode *bt;
tt=0;
cin>>n;
for(int i=0;i<n;i++)
cin>>a[i];
for(int i=0;i<n;i++)
cin>>b[i];
bt=CreateBTNode(a,b,n);
LevelOrder(bt);
cout<<c[0];
for(int i=1;i<n;i++)
cout<<" "<<c[i];
cout<<endl;
return 0;
}
L2-011. 玩转二叉树
给定一棵二叉树的中序遍历和前序遍历，请你先将树做个镜面反转，再输出反转后的层序遍历的序列。所谓镜面反转，是指将所有非叶结点的左右孩子对换。这里假设键值都是互不相等的正整数。
输入格式：
输入第一行给出一个正整数N（<=30），是二叉树中结点的个数。第二行给出其中序遍历序列。第三行给出其前序遍历序列。数字间以空格分隔。
输出格式：
在一行中输出该树反转后的层序遍历的序列。数字间以1个空格分隔，行首尾不得有多余空格。
输入样例：
7
1 2 3 4 5 6 7
4 1 3 2 6 5 7
输出样例：
4 6 1 7 5 3 2
#include <iostream>
#include <queue>
#include <cstdio>
#include <cstring>
#include <string>
#include <malloc.h>
using namespace std;
struct BTNode
{
int key;
BTNode *lchild,*rchild;
};
BTNode *CreatBTNode(int b[],int a[],int n)//a表示中序，b表示先序，构树方法和中序与后序的类似
{
int p,k,i,temp1[35],temp2[35],temp3[35];
BTNode *bt;
if(n<=0) return NULL;
bt=(BTNode*)malloc(sizeof(BTNode));
bt->key=b[0];
for(i=0;i<n;i++)
if(b[0]==a[i])
break;
k=0;
for(int j=1;j<i+1;j++)
temp1[k++]=b[j];
bt->lchild=CreatBTNode(temp1,a,i);
k=0;
for(int j=i+1;j<n;j++)
temp2[k++]=b[j];
k=0;
for(int j=i+1;j<n;j++)
temp3[k++]=a[j];
bt->rchild=CreatBTNode(temp2,temp3,n-i-1);
return bt;
}
void Change(BTNode *&bt)//递归的将左右子树进行交换
{
BTNode *p;
if(bt)
{
p=bt->lchild;
bt->lchild=bt->rchild;
bt->rchild=p;
Change(bt->lchild);
Change(bt->rchild);
}
}
int c[35],tt;
void LevelOrder(BTNode *bt)//层次遍历交换后的树
{
queue<BTNode*> Q;
BTNode *p;
Q.push(bt);
while(!Q.empty())
{
p=Q.front();
c[tt++]=p->key;
Q.pop();
if(p->lchild)
Q.push(p->lchild);
if(p->rchild)
Q.push(p->rchild);
}
}
int main()
{
int n,a[35],b[35];
BTNode *bt,*b1;
tt=0;
cin>>n;
for(int i=0;i<n;i++)
cin>>a[i];
for(int i=0;i<n;i++)
cin>>b[i];
bt=CreatBTNode(b,a,n);
Change(bt);
LevelOrder(bt);
cout<<c[0];
for(int i=1;i<n;i++)
cout<<" "<<c[i];
cout<<endl;
return 0;
}L3-010. 是否完全二叉搜索树
将一系列给定数字顺序插入一个初始为空的二叉搜索树（定义为左子树键值大，右子树键值小），你需要判断最后的树是否一棵完全二叉树，并且给出其层序遍历的结果。
输入格式：
输入第一行给出一个不超过20的正整数N；第二行给出N个互不相同的正整数，其间以空格分隔。
输出格式：
将输入的N个正整数顺序插入一个初始为空的二叉搜索树。在第一行中输出结果树的层序遍历结果，数字间以1个空格分隔，行的首尾不得有多余空格。第二行输出“YES”，如果该树是完全二叉树；否则输出“NO”。
输入样例1：
9
38 45 42 24 58 30 67 12 51
输出样例1：
38 45 24 58 42 30 12 67 51
YES
输入样例2：
8
38 24 12 45 58 67 42 51
输出样例2：
38 45 24 58 42 12 67 51
NO
#include <iostream>
#include <queue>
#include <cstdio>
#include <malloc.h>
using namespace std;
typedef struct node
{
int key;
struct node *lchild,*rchild;
} BSTNode;
int InsertBST(BSTNode *&p,int k)
{
if(p==NULL)
{
p=(BSTNode*)malloc(sizeof(BSTNode));
p->key=k;
p->lchild=p->rchild=NULL;
return 1;
}
else if(k==p->key)
return 0;
else if(k<p->key)
return InsertBST(p->rchild,k);
else
return InsertBST(p->lchild,k);
}
BSTNode *CreateBSTNode(int a[],int n)
{
BSTNode *bt=NULL;
int i=0;
while(i<n)
{
InsertBST(bt,a[i]);
i++;
}
return bt;
}
int IsCompleteBiTree(BSTNode *bt)//利用树的层次遍历判断是否为完全二叉树，因为完全二叉树在左孩子为空的情况下右孩子一定为空，所以只要在p非空的情况下判断p的左孩子是否为空而右孩子非空，如果是这样直接返回Fals，否则的话就将它的左右孩子全部入队，在遇到第一个空节点的时候如果它后边的所有节点都为空则为完全二叉树，否则就不是
{
queue<BSTNode*> Q;
BSTNode *p;
Q.push(bt);
while(!Q.empty())
{
p=Q.front();
Q.pop();
if(p)
{
if(!p->lchild&&p->rchild)
return 0;
Q.push(p->lchild);
Q.push(p->rchild);
}
else
{
Q.pop();
break;
}
}
while(!Q.empty())
{
p=Q.front();
Q.pop();
if(p)
return 0;
}
return 1;
}
int t,b[25];
void LevelOrder(BSTNode *bt)//层次遍历这棵树
{
BSTNode *p;
queue<BSTNode*> Q;
Q.push(bt);
while(!Q.empty())
{
p=Q.front();
//printf("%d ",p->key);
b[t++]=p->key;
Q.pop();
if(p->lchild!=NULL)
Q.push(p->lchild);
if(p->rchild!=NULL)
Q.push(p->rchild);
}
}
int main()
{
int n,a[25],flag;
BSTNode *bt;
t=0;
cin>>n;
for(int i=0; i<n; i++)
cin>>a[i];
bt=CreateBSTNode(a,n);
LevelOrder(bt);
cout<<b[0];
for(int i=1; i<n; i++)
cout<<" "<<b[i];
cout<<endl;
flag=IsCompleteBiTree(bt);
if(flag==0)
cout<<"NO"<<endl;
else
cout<<"YES"<<endl;
return 0;
}最后一个是河南省第九届 ACM程序设计竞赛的一个题，题意大概是首先给你T组测试数据，每组测试数据的第一行是两个数n，k表示有n棵树，每棵树有k个节点，让你判断这n棵树有多少种类型
解题思路：首先构树，然后用一个指针数组将这n棵树存着 ，然后再挨个比较，此时应注意比较时需要标记，如果不标记会造成反复比较相同类型的树数值会变大
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
struct Tree
{
struct Tree *lchild,*rchild;
int key;
};
int Insert(Tree *&p,int k)
{
if(p==NULL)
{
p = (Tree*)malloc(sizeof(Tree));
p->key=k;
p->lchild=p->rchild=NULL;
return 1;
}
else if(k<p->key)
return Insert(p->lchild,k);
else if(k>p->key)
return Insert(p->rchild,k);
}
Tree *CreatT(int A[],int n)
{
Tree *tr = NULL;
int i=0;
while(i<n)
{
Insert(tr,A[i]);
i++;
}
return tr;
}
bool Like(Tree *b1,Tree *b2)//递归比较两棵树是否相似
{
bool like1,like2;
if(b1==NULL&&b2==NULL)
return true;
else if(b1==NULL||b2==NULL)
return false;
else
{
like1=Like(b1->lchild,b2->lchild);
like2=Like(b1->rchild,b2->rchild);
return (like1&&like2);
}
}
int main()
{
int T;scanf("%d",&T);
while(T--)
{
int n,k;
int a[25];
Tree *tr[55];
scanf("%d %d",&n,&k);
for(int i=0;i<n;i++)
{
for(int j=0;j<k;j++)
{
scanf("%d",&a[j]);
}
tr[i]=CreatT(a,k);
}
int sum=0,s=-1;//sum用来表示相似的树有多少棵，s用来同一类型的树有多少棵，因为同一类型的树只算一种，所以初始值为-1
int vis[55];
memset(vis,0,sizeof(vis));
for(int i=0;i<n;i++)
{
if(vis[i])continue;
s=0;
vis[i]=1;
for(int j=0;j<n;j++)
{
if(i!=j&&Like(tr[i],tr[j])&&!vis[j])
{
vis[j]=1;
s++;
}
}sum=sum+s;
}
cout<<n-sum<<endl;
}
return 0;
}