Binary Tree Traversals(二叉树) - HDU 1710

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.

（二叉树是一个有限集合，可以为空，有一个根节点r，根节点下面有两棵不相交的子树。有3种有序的方法可以遍历二叉树，分别是先序遍历、中序遍历、后序遍历，假定二叉树T有T1和T2两个子树，先序遍历会先遍历T，然后中序遍历T1和T2的所有节点，中序遍历是先遍历T1的所有节点，然后是T，然后是中序遍历T2的所有节点。后序遍历是先遍历T1和T2，再访问r。现在给定先序遍历和中序遍历，找出后序遍历的序列。）

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

二叉树遍历

对一棵二叉树进行遍历，我们可以采取3中顺序进行遍历，分别是前序遍历、中序遍历和后序遍历。这三种方式是以访问父节点的顺序来进行命名的。假设父节点是N，左节点是L，右节点是R，那么对应的访问遍历顺序如下：

• 前序遍历 N－>L－>R
• 中序遍历 L－>N－>R
• 后序遍历 L－>R－>N

所以，对于以下这棵树，三种遍历方式的结果是：

• 前序遍历 ABCDEF
• 中序遍历 CBDAEF
• 后序遍历 CDBFEA

解题说明：

二叉树的遍历用递归的方式写起来非常简单，本题用数组实现，先序和中序遍历的特点是，对于每颗（子）树的存储都是块状的，这样理解代码起来就简单很多。

源码：G++

#include <stdio.h>

static int pre[1005];
static int mid[1005];

/**
每次处理数组中的一个小块
特点：先序和后序遍历任意子树都是连续的块
**/
void post(int pre_index, int mid_index, int size, int is_root)
{
    if (!size) {
        return;
    }

    if (size == 1)
    {
        //打印先序
        printf("%d ", pre[pre_index]);
        return;
    }

    //每个（子）树根的位置
    int root;

    //找到根节点
    for (root = 0; root < size && pre[pre_index] != 
        mid[mid_index + root]; root++);

    //处理根的左边
    post(pre_index + 1, mid_index, root, 0);
    //处理根的右边
    post(pre_index + root + 1, mid_index + root + 1, 
        size - root - 1, 0);
    //是否是总根，打印根（相对）
    is_root ? printf("%d\n", pre[pre_index]) : 
        printf("%d ", pre[pre_index]);
}

int main()
{
    int n, i;
    n = 9;
    while (~scanf("%d", &n))
    {
        for (i = 0; i < n; i++)
            scanf("%d", &pre[i]);
        for (i = 0; i < n; i++)
            scanf("%d", &mid[i]);
        post(0, 0, n, 1);
    }
    return 0;
}

参考：

1、https://www.cnblogs.com/liujinghuan/p/5842487.html

2、http://blog.csdn.net/xiaotaoqibao/article/details/5602295