二叉树的遍历及重建

二叉树的遍历

我们知道二叉树是一种常用的数据结构，包括内部节点和叶节点，每个节点有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);
}