问题A:二叉排序树
题目描述
输入一系列整数，建立二叉排序数，并进行前序，中序，后序遍历。
输入
输入第一行包括一个整数n(1<=n<=100)。接下来的一行包括n个整数。
输出
可能有多组测试数据，对于每组数据，将题目所给数据建立一个二叉排序树，并对二叉排序树进行前序、中序和后序遍历。每种遍历结果输出一行。每行最后一个数据之后有一个空格。
样例输入
1 2 2 8 15 4 21 10 5 39
样例输出
2 2 2 8 15 8 15 15 8 21 10 5 39 5 10 21 39 5 10 39 21
//问题A:二叉排序树
#include <iostream>
#include <cstdio>
using namespace std;
#define maxn 105
int data[maxn]={0};
struct node{
int data;
node* lchild;
node* rchild;
};
node* newNode(int v);
void insert1(node* &root,int x);
node* Create(int data[],int n);
void preOrder(node* root);
void inOrder(node* root);
void postOrder(node* root);
int main()
{
int n;
while(cin>>n)
{
node* root=new node;
data[maxn]={0};
for(int i=0;i<n;i++) cin>>data[i];
root=Create(data,n);
preOrder(root);
cout<<endl;
inOrder(root);
cout<<endl;
postOrder(root);
cout<<endl;
}
return 0;
}
node* Create(int data[],int n)
{
node* root=NULL; //根结点地址设为空
for(int i=0;i<n;i++)
{
insert1(root,data[i]);
}
return root;
}
void insert1(node* &root,int x)
{
if(root==NULL){ //空树，说明查找失败，也即插入位置
root=newNode(x);
return;
}
if(x==root->data){
return;
}else if(x<root->data)
{
insert1(root->lchild,x);
}else{
insert1(root->rchild,x);
}
}
node* newNode(int v)
{
node* Node=new node; //申请node型变量地址空间
Node->data=v;
Node->lchild=Node->rchild=NULL;
return Node; //返回新建结点的地址
}
void preOrder(node* root)
{
if(root==NULL) return;
printf("%d ",root->data);
preOrder(root->lchild);
preOrder(root->rchild);
}
void inOrder(node* root)
{
if(root==NULL) return;
inOrder(root->lchild);
printf("%d ",root->data);
inOrder(root->rchild);
}
void postOrder(node* root)
{
if(root==NULL) return;
postOrder(root->lchild);
postOrder(root->rchild);
printf("%d ",root->data);
}
问题B:二叉查找树
题目描述
判断两序列是否为同一二叉搜索树序列
输入
开始一个数n，(1<=n<=20) 表示有n个需要判断，n= 0 的时候输入结束。
接下去一行是一个序列，序列长度小于10，包含(0~9)的数字，没有重复数字，根据这个序列可以构造出一颗二叉搜索树。
接下去的n行有n个序列，每个序列格式跟第一个序列一样，请判断这两个序列是否能组成同一颗二叉搜索树。
输出
如果序列相同则输出YES，否则输出NO
样例输入
6 45021 12045 54120 45021 45012 21054 50412 0
样例输出
NO NO YES NO NO NO
#include <cstdio>
#include <iostream>
#include <sstream>
#include <vector>
using namespace std;
#define maxn 105
int data[maxn]={0};
int data1[maxn]={0};
vector<int> originpre,nowpre,originin,nowin;
struct node{
int data;
node* lchild;
node* rchild;
};
//新建一个结点
node* newNode(int v);
//插入一个结点
void insert1(node* &root,int x);
//创建二叉排序树
node* Create(int data[],int n);
///因为vector数组要传值回来，故一定要带引用
void preOrder(node* root,vector<int> &vec);
void inOrder(node* root,vector<int> &vec);
int main()
{
int n;
while(cin>>n)
{
if(n==0) break;
string line;
cin>>line;
int len=line.length();
for(int i=0;i<len;i++) data[i]=line[i]-'0';
node* root=new node;
root=Create(data,len);
preOrder(root,originpre);
inOrder(root,originin);
for(int i=0;i<n;i++)
{
cin>>line;
for(int i=0;i<len;i++) data1[i]=line[i]-'0';
node* root1=new node;
root1=Create(data1,len);
preOrder(root1,nowpre);
inOrder(root1,nowin);
//可以使用“==“直接判断两个vector数组是否相等
if(originpre==nowpre&&originin==nowin) printf("YES\n");
else printf("NO\n");
//清除vector数组内元素
nowpre.clear();
nowin.clear();
}
originpre.clear();
originin.clear();
}
return 0;
}
node* newNode(int v)
{
node* Node=new node;
Node->data=v;
Node->lchild=Node->rchild=NULL;
return Node;
}
void insert1(node* &root,int x)
{
if(root==NULL){
root=newNode(x);
return;
}
if(root->data==x) return;
else if(x<root->data)
{
insert1(root->lchild,x);
}else{
insert1(root->rchild,x);
}
}
node* Create(int data[],int n)
{
node* root=NULL; //根结点地址首先要设为空!!!
for(int i=0;i<n;i++)
{
insert1(root,data[i]);
}
return root;
}
//记得vector数组带引用
void preOrder(node* root,vector<int> &vec)
{
int i;
if(root==NULL) return;
// printf("%d ",root->data);
vec.push_back(root->data);
preOrder(root->lchild,vec);
preOrder(root->rchild,vec);
}
void inOrder(node* root,vector<int> &vec)
{
if(root==NULL) return;
inOrder(root->lchild,vec);
vec.push_back(root->data);
inOrder(root->rchild,vec);
}