Hdu Binary Tree Traversals

Problem Description
        A binary tree is a finite set of vertices that is either empty or consists of a root r and two disjoint binary trees called the left and right subtrees. There are three most important ways in which the vertices of a binary tree can be systematically traversed or ordered. They are preorder, inorder and postorder. Let T be a binary tree with root r and subtrees T1,T2.

In a preorder traversal of the vertices of T, we visit the root r followed by visiting the vertices of T1 in preorder, then the vertices of T2 in preorder.

In an inorder traversal of the vertices of T, we visit the vertices of T1 in inorder, then the root r, followed by the vertices of T2 in inorder.

In a postorder traversal of the vertices of T, we visit the vertices of T1 in postorder, then the vertices of T2 in postorder and finally we visit r.

Now you are given the preorder sequence and inorder sequence of a certain binary tree. Try to find out its postorder sequence.

Input
The input contains several test cases. The first line of each test case contains a single integer n (1<=n<=1000), the number of vertices of the binary tree. Followed by two lines, respectively indicating the preorder sequence and inorder sequence. You can assume they are always correspond to a exclusive binary tree.

Output
For each test case print a single line specifying the corresponding postorder sequence.

Sample Input
9
1 2 4 7 3 5 8 9 6
4 7 2 1 8 5 9 3 6

Sample Output
7 4 2 8 9 5 6 3 1
 
 
 
注: 已知二叉樹的前序和中序遍歷, 可以唯一確定二叉樹的後序遍歷, 但如果知道前序和後序,求中序遍歷是不可能實現的.

 
算法:

     由前序遍歷的第一個元素可確定左、右子樹的根節點，參照中序遍歷又可進一步確定子樹的左、

右子樹元素。如此遞歸地參照兩個遍歷序列，最終構造出二叉樹。

 由前序和中序結果求後序遍歷結果

     樹的遍歷：給你一棵樹的先序遍歷結果和中序遍歷的結果，讓你求以後序遍歷輸出用遞歸。

每次把兩個數組分成三個部分，父節點，左子樹，右子樹，把父節點放到數組裡邊，重復此步驟直到重建一棵新樹

,  這時，數組裡元素剛好是後序遍歷的順序

關鍵點：

    中序遍歷的特點是先遍歷左子樹，接著根節點，然後遍歷右子樹。這樣根節點就把左右子樹隔開了。而前序遍歷的特點是先訪問根節點，從而實現前序遍歷結果提供根節點信息，中序遍歷提供左右子樹信息，從而實現二叉樹的重建

【注明】

先序的排列裡第一個元素是根，再比較中序的排列裡根所在的位置，則能確定左子樹，右子樹元素個數numleft，numright且在先序排列裡，先是一個根，再是numleft個左子樹的元素排列，最後是numright個右子樹的元素排列。

  該過程就是從inorder數組中找到一個根，然後從preorder數組的位置來確定改點到底是左兒子還是右兒子。如此一直循環下去知道一棵完整的數建立完成。

#include <stdio.h>
#include <stdlib.h>

const int MAX = 1000 + 10;
int n,in[MAX],pre[MAX];
typedef struct BITree
{
    int data,index;
    BITree *Left,*Right;
}BiTree,*Tree;

void DFS(Tree &root,int index)
{
    if(root == NULL){
        root = (Tree)malloc(sizeof(BiTree));
        root->data = in[index];
        root->index = index;
        root->Left = NULL;
        root->Right = NULL;
    }else
    {
        if(index < root->index)
          DFS(root->Left,index);
        else
          DFS(root->Right,index);
    }
}

void CreateTree(Tree &root)
{
    int i,j,index;
    root = (Tree)malloc(sizeof(BiTree));
    for(i = 1;i <= n;i++)
      if(in[i] == pre[1])
      {
          root->data = pre[1];
          root->index = i;
          root->Left = NULL;
          root->Right = NULL;
          break;
      }
    index = i;
    for(i = 2;i <= n;i++)
      for(j = 1;j <= n;j++)
         if(in[j] == pre[i])
         {
             if(j < index)
               DFS(root->Left,j);
             else
               DFS(root->Right,j);
             break;
         }
}

void PostOrder(Tree root,int x)
{
    if(root == NULL) return ;
    PostOrder(root->Left,x+1);
    PostOrder(root->Right,x+1);
    if(x == 0)
      printf("%d",root->data);
    else
      printf("%d ",root->data);
}

int main()
{
    int i;
    while(scanf("%d",&n)!=EOF)
    {
        Tree root;
        for(i = 1;i <= n;i++)
          scanf("%d",&pre[i]);
        for(i = 1;i <= n;i++)
          scanf("%d",&in[i]);
        CreateTree(root);
        PostOrder(root,0);
        printf("\n");
    }
    return 0;
}

#include <iostream>
#include <cstdio>
using namespace std;

const int MAX = 1000 + 10;
typedef struct BITree
{
    int data;
    BITree *Left,*Right;
    BITree()
    {
        Left = NULL;
        Right = NULL;
    }
}*BiTree;
int pre[MAX],in[MAX];

void BuildTree(BiTree &root,int len,int pst,int ped,int inst,int ined)
{
    int i,left_len = 0;
    if(len<=0)return;          //遞歸終止的條件
    root = new BITree;
    root->data = pre[pst];
    for(i = inst;i <= ined;i++)
      if(in[i] == pre[pst])
      {
          left_len = i - inst;
          break;
      }
    BuildTree(root->Left,left_len,pst+1,pst+left_len,inst,i-1);
    BuildTree(root->Right,len-left_len-1,pst+left_len+1,ped,i+1,ined);
}

void PostTravel(BITree *root)
{
    if(root)
    {
        PostTravel(root->Left);
        PostTravel(root->Right);
        printf("%d ",root->data);
    }
}

int main()
{
    int i,n;
    BiTree root;
    while(scanf("%d",&n)!=EOF)
    {
        for(i = 1;i <= n;i++)
          scanf("%d",&pre[i]);
        for(i = 1;i <= n;i++)
          scanf("%d",&in[i]);
        BuildTree(root,n,1,n,1,n);
        PostTravel(root->Left);
        PostTravel(root->Right);
        printf("%d\n",root->data);
    }
    return 0;
}