二叉树的遍历及重建
二叉树的遍历
我们知道二叉树是一种常用的数据结构，包括内部节点和叶节点，每个节点有0-2个子女。对于一棵二叉树来说，我们一般从根节点开始遍历每个节点。二叉树的遍历一般有三种方法：前序遍历、中序遍历和后序遍历。
D
/ \
/ \
B E
/ \ \
/ \ \
A C G
/
/
F
对于如上所示的二叉树，三种遍历访问的顺序分别是：
前序遍历：DBACEGF 中序遍历：ABCDEFG 后序遍历：ACBFGED
从中可以发现，前序遍历一定从根节点开始，后序遍历一定以根节点结束。再结合中序遍历的顺序，可以发现这样的规律对于一棵二叉树的子树来说也是成立的。如左子树前中后遍历顺序分别为：BAC、ABC和ACB。
二叉树的重建
如果我们给出三种遍历结果中的一个或两个，能不能把整棵树的结构重建出来呢？很明显，根据单个遍历结果是不能重建一棵二叉树的，而由于前序遍历和后序遍历没有保存根节点的位置信息，所以也不能根据前序遍历和后序遍历重建一棵二叉树。也就说由中序遍历结果和前序遍历或后序遍历中的一种，我们就能重建一棵二叉树。
相关例题
这里有两道重建二叉树的题目，可以供大家练习。
1. 前序和中序重建二叉树转后序遍历（POJ 2255 二叉树重建）
题目链接：http://poj.org/problem?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 由中根序列和后根序列重建二叉树）
题目链接：http://dsalgo.openjudge.cn/huawen05/1/ AC代码：
#include<bits/stdc++.h>using namespace std;#define eps 1e-8#define INF 0x3f3f3f3fconst 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);}
int main(){ int k=0; cnt=0; while(~scanf("%d",&n[k++])){} for(int i=0;i<k/2;i++){ a[i]=n[i]; b[i]=n[i+k/2]; } node* tree=buildtree(0,k/2-1,0,k/2-1); pre_order(tree); for(int i=0;i<cnt-1;i++){ printf("%d ",ans[i]); } printf("%d\n",ans[cnt-1]); return 0;}