根据⼆叉树的前序和中序或者后序和中序来确定⼆叉树结构
（附例题）
根据中序和前序后序中的任意⼀种结构就可以确定⼆叉树的结构。
因为中序是按照左中右的顺序来遍历的。⽽前序是按照中左右的顺序来确定的，我们可以通过按照前序顺序来构建⼆叉树，通过中序来确定⼆叉树的左⼦树和右⼦树。后序和中序组合也是这样，只不过后序需要从后⾯开始。
这⾥给出两个例题：
1.前序和中序确定：
数据结构与算法题⽬集（中⽂） 7-23 还原⼆叉树 （25 分）
给定⼀棵⼆叉树的先序遍历序列和中序遍历序列，要求计算该⼆叉树的⾼度。
输⼊格式:
输⼊⾸先给出正整数N（≤50），为树中结点总数。下⾯两⾏先后给出先序和中序遍历序列，均是长度为N
的不包含重复英⽂字母（区别⼤⼩写）的字符串。
输出格式:
输出为⼀个整数，即该⼆叉树的⾼度。
输⼊样例:
9
ABDFGHIEC
FDHGIBEAC
输出样例:
5
先还原⼆叉树，然后求⾼度。
代码如下：
#include <bits/stdc++.h>
using namespace std;
const int maxn=55;
int n;
int loc=0;
char pre[maxn],in[maxn];
struct tree
{
int data;
tree* left,*right;
};
int Find (char x)
{
for (int i=0;i<n;i++)
{
if(in[i]==x)
return i;
}
return -1;
}
tree* create (int l,int r)
{
if(l>r)
{
return NULL;
}
char root=pre[loc++];
int m=Find(root);
tree* t=(tree*)malloc(sizeof(tree));
t->data=root;
if(l==r)
{
t->left=t->right= NULL;
}
else
{
t->left=create(l,m-1);
t->right=create(m+1,r);
}
return t;
}
int Height(tree* root)
{
if(root==NULL)
{
return 0;
}
return max(Height(root->left),Height(root->right))+1;
}
int main()
{
scanf("%d",&n);
scanf("%s",pre);先序中序后序遍历二叉树
scanf("%s",in);
tree* root=create(0,n-1);
printf("%d\n",Height(root));
return 0;
}
2. PAT (Advanced Level) Practice  1020 Tree Traversals （25 分）还原⼆叉树，然后进⾏层次遍历。
代码如下：
#include <bits/stdc++.h>
using namespace std;
const int maxn=35;
struct tree
{
int data;
tree* left,*right;
};
int n;
int post[maxn];
int in[maxn];
int loc;
int Find (int x)
{
for (int i=0;i<n;i++)
{
if(in[i]==x)
return i;
}
return -1;
}
tree* create (int l,int r)
{
if(l>r)
{
return NULL;
}
tree* t=(tree*)malloc(sizeof(tree)); t->data=post[loc];
int m=Find(post[loc--]);
if(l==r)
{
t->left=t->right=NULL;
}
else
{
t->right=create(m+1,r);
t->left=create(l,m-1);
}
return t;
}
void Traverse (tree* root)
{
int num=0;
queue<tree*>q;
if(root)
q.push(root);
while (!q.empty())
{
int Size=q.size();
while (Size--)
{
tree* t=q.front();
q.pop();
printf("%d",t->data);
num++;
if(num==n)
{
printf("\n");
}
else
{
printf(" ");
printf(" ");
}
if(t->left)
{
q.push(t->left);
}
if(t->right)
{
q.push(t->right);
}
}
}
}
int main()
{
scanf("%d",&n);
loc=n-1;
for (int i=0;i<n;i++)
{
scanf("%d",&post[i]); }
for (int i=0;i<n;i++)
{
scanf("%d",&in[i]);
}
tree* root=create (0,n-1); Traverse(root);
return 0;
}

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。