二叉查找树练习题
1043 Is It a Binary Search Tree (25 分)
https://pintia.cn/problem-sets/994805342720868352/problems/994805440976633856
题意：给出N个正整数来作为一棵二叉排序树的结点插入顺序，问这串序列是否是该二叉排序树的先序序列或是该二叉排序树的镜像树的先序序列。镜像树是指交换二叉树的所有结点的左右子树而形成的树
（也即左子树所有节点数据域大于或等于根结点，右子树数据域小于根结点数据域）若是，则输出YES,并输出对应的树的后序序列；否则输出NO。
思路：通过给定的插入序列，构建出二叉排序树；
解法一是针对一个序列分别构建了两棵树：二叉排序树和其镜像树，然后分别对两棵树进行先序遍历分别得到不同的结果，若二叉排序树先序遍历序列和原序列相同，则输出该树的后序遍历序列；
若镜像树先序遍历序列和原序列相同，则输出镜像树后序遍历序列，否则输出No。
解法二是依据对镜像树的先序遍历只需要在原树的先序遍历时交换左右子树的访问顺序；即先针对一个序列构建一棵二叉排序树，然后对该树分别进行普通先序遍历和镜像树先序遍历，看哪种遍历结果和原序列相同；若有一个相同，就输出对应的后序遍历序列，否则输出No。
注意点：
①使用vector来存放初始序列、先序序列、镜像树先序序列，可以方便相互之间进行比较。若使用数组，则比较操作就需要使用循环才能实现。
②定义根结点时要将其设为空结点，在新建结点时要注意另其左右子结点地址设为NULL。
解法一：
#include <iostream> #include <cstdio> #include <vector> using namespace std; #define maxn 1005 int data[maxn]={0}; vector<int> vec1,vec2,vec3; struct node{ int data; node* lchild; node* rchild; }; node* Create1(int data[],int n); node* Create2(int data[],int n); void insert1(node* &root,int x); void insert2(node* &root,int x); node* newNode(int v); void preOrder(node* root,vector<int> &vec); void postOrder(node* root,vector<int> &vec); int main() { node* root1=new node; node* root2=new node; int n,i=0,j=0; cin>>n; for(i=0;i<n;i++) cin>>data[i]; root1=Create1(data,n); root2=Create2(data,n); preOrder(root1,vec1); preOrder(root2,vec2); for(i=0;i<vec1.size();i++) { if(vec1[i]!=data[i]) break; } for(j=0;j<vec2.size();j++) { if(vec2[j]!=data[j]) break; } if(i>=vec1.size()||j>=vec2.size()) { cout<<"YES "; if(i>=vec1.size()){ postOrder(root1,vec3); for(int i=0;i<vec3.size();i++) { if(i==0) cout<<vec3[i]; else cout<<" "<<vec3[i]; } cout<<endl; }else{ postOrder(root2,vec3); for(int i=0;i<vec3.size();i++) { if(i==0) cout<<vec3[i]; else cout<<" "<<vec3[i]; } cout<<endl; } } else cout<<"NO "; return 0; } node* Create1(int data[],int n) { node* root1=NULL; for(int i=0;i<n;i++) { insert1(root1,data[i]); } return root1; } node* Create2(int data[],int n) { node* root2=NULL; for(int i=0;i<n;i++) { insert2(root2,data[i]); } return root2; } void insert1(node* &root,int x) { if(root==NULL) { root=newNode(x); return; } if(x<root->data) { insert1(root->lchild,x); }else{ insert1(root->rchild,x); } } void insert2(node* &root,int x) { if(root==NULL) { root=newNode(x); return; } if(x>=root->data) { insert2(root->lchild,x); }else{ insert2(root->rchild,x); } } node* newNode(int v) { node* Node=new node; Node->data=v; Node->lchild=Node->rchild=NULL; return Node; } void preOrder(node* root,vector<int> &vec) { if(root==NULL) return; vec.push_back(root->data); preOrder(root->lchild,vec); preOrder(root->rchild,vec); } void postOrder(node* root,vector<int> &vec) { if(root==NULL) return; postOrder(root->lchild,vec); postOrder(root->rchild,vec); vec.push_back(root->data); }
解法二：
#include <iostream> #include <cstdio> #include <vector> using namespace std; #define maxn 1005 int data[maxn]={0}; vector<int> origin,pre,post,preM,postM; struct node{ int data; node* lchild; node* rchild; }; void insert1(node* &root,int x); void preOrder(node* root,vector<int> &vec); void preOrderMirror(node* root,vector<int> &vec); void postOrder(node* root,vector<int> &vec); void postOrderMirror(node* root,vector<int> &vec); int main() { node* root=NULL; //定义头结点，初始设为空 int n,i=0,j=0,data; cin>>n; for(i=0;i<n;i++){ cin>>data; origin.push_back(data); insert1(root,data); } preOrder(root,pre); //求先序 preOrderMirror(root,preM); //求镜像树先序 postOrder(root,post); //求后序 postOrderMirror(root,postM); //求镜像树后序 if(origin==pre){ //初始序列等于先序序列 printf("YES "); for(int i=0;i<post.size();i++) { if(i==0) cout<<post[i]; else cout<<" "<<post[i]; } cout<<endl; }else if(origin==preM){ //初始序列等于镜像树先序列 printf("YES "); for(int i=0;i<postM.size();i++) { if(i==0) cout<<postM[i]; else cout<<" "<<postM[i]; } cout<<endl; }else{ cout<<"NO "; } return 0; } void insert1(node* &root,int x) { if(root==NULL) { root=new node; root->data=x; root->lchild=root->rchild=NULL; //这句不可以漏！！！ return; } if(x<root->data) { insert1(root->lchild,x); }else{ insert1(root->rchild,x); } } void preOrder(node* root,vector<int> &vec) { if(root==NULL) return; vec.push_back(root->data); preOrder(root->lchild,vec); preOrder(root->rchild,vec); } void postOrder(node* root,vector<int> &vec) { if(root==NULL) return; postOrder(root->lchild,vec); postOrder(root->rchild,vec); vec.push_back(root->data); } void preOrderMirror(node* root,vector<int> &vec) { if(root==NULL) return; vec.push_back(root->data); preOrderMirror(root->rchild,vec); preOrderMirror(root->lchild,vec); } void postOrderMirror(node* root,vector<int> &vec) { if(root==NULL) return; postOrderMirror(root->rchild,vec); postOrderMirror(root->lchild,vec); vec.push_back(root->data); }
问题A:二叉排序树
题目描述
输入一系列整数，建立二叉排序数，并进行前序，中序，后序遍历。
输入
输入第一行包括一个整数n(1<=n<=100)。接下来的一行包括n个整数。
输出
可能有多组测试数据，对于每组数据，将题目所给数据建立一个二叉排序树，并对二叉排序树进行前序、中序和后序遍历。每种遍历结果输出一行。每行最后一个数据之后有一个空格。
样例输出
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
#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 "); else printf("NO "); //清除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); }