二叉树的遍历及重建
二叉树的遍历
我们知道二叉树是一种常用的数据结构，包括内部节点和叶节点，每个节点有0-2个子女。对于一棵二叉树来说，我们一般从根节点开始遍历每个节点。二叉树的遍历一般有三种方法：前序遍历、中序遍历和后序遍历。
D
/ \
/ \
B E
/ \ \
/ \ \
A C G
/
/
F
对于如上所示的二叉树，三种遍历访问的顺序分别是：
前序遍历：DBACEGF
中序遍历：ABCDEFG
后序遍历：ACBFGED
从中可以发现，前序遍历一定从根节点开始，后序遍历一定以根节点结束。再结合中序遍历的顺序，可以发现这样的规律对于一棵二叉树的子树来说也是成立的。如左子树前中后遍历顺序分别为：BAC、ABC和ACB。
二叉树的重建
如果我们给出三种遍历结果中的一个或两个，能不能把整棵树的结构重建出来呢？很明显，根据单个遍历结果是不能重建一棵二叉树的，而由于前序遍历和后序遍历没有保存根节点的位置信息，所以也不能根据前序遍历和后序遍历重建一棵二叉树。也就说由中序遍历结果和前序遍历或后序遍历中的一种，我们就能重建一棵二叉树。
相关例题
这里有两道重建二叉树的题目，可以供大家练习。
1. 前序和中序重建二叉树转后序遍历（POJ 2255 二叉树重建）
题目链接：?id=2255
AC代码：
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
using namespace std;
struct node
{
char c;
node* left;
node* right;
};
string s1,s2;
node* buildtree(int l1,int r1,int l2,int r2)
{
if(l1>r1) return NULL;
int temp=0;
node* now=new node;
now->c=s1[l1];
if(l1==r1){
now->left=NULL;
now->right=NULL;
return now;
}
for(int i=l2;i<=r2;i++){
if(s2[i]==s1[l1]){
temp=i;
break;
}
}
now->left=buildtree(l1+1,l1+temp-l2,l2,temp-1);
now->right=buildtree(l1+temp-l2+1,r1,temp+1,r2);
return now;
}
void post_order(node* root)
{
if(root==NULL) return;
post_order(root->left);
post_order(root->right);
printf("%c",root->c);
}
int main()
{
while(cin>>s1>>s2){
node* tree=buildtree(0,s1.length()-1,0,s2.length()-1);
post_order(tree);
printf("\n");
}
return 0;
}
2. 中序和后序重建二叉树转前序遍历（POJ 由中根序列和后根序列重建二叉树）
#include<bits/stdc++.h>
using namespace std;
#define eps 1e-8
#define INF 0x3f3f3f3f
const int num=1e6;
int a[num+5],b[num+5],n[num+5],ans[num+5],cnt;
struct node{
int x;
node* left;
node* right;
node(int _x=0){
x=_x;
left=NULL;
right=NULL;
}
};
node* buildtree(int l1,int r1,int l2,int r2)
{
//cout<<l1<<' '<<r1<<' '<<l2<<' '<<r2<<"###"<<endl;
if(l1>r1) return NULL;
if(l1==r1){
node* nd=new node(a[l1]);
return nd;
}
node* nd=new node(b[r2]);
int tmp=b[r2],id=l1;
for(int i=l1;i<=r1;i++){
if(a[i]==tmp){
id=i;
break;
}
}
nd->left=buildtree(l1,id-1,l2,l2+id-l1-1);
nd->right=buildtree(id+1,r1,l2+id-l1,r2-1);
return nd;
}
void pre_order(node* nd){
if(nd==NULL) return;
ans[cnt++]=nd->x;
pre_order(nd->left);
pre_order(nd->right);
}