博客

因为从刘汝佳老师的书中一题发现有一个知识点需要好好理解，它就是如何通过二叉树的中序和后序遍历（前序和中序）构造出这课二叉树。

中序和后序:

这个过程如下：

1.根据后序序列的最后一个元素建立根结点

2.从中序序列中找到这个根结点的位置，确定此根结点的左右子树的中序序列（左边的序列为左子树，右边的即为右子树）

3.在后序序列中确定左右子树的后序序列

4.由左子树的后序序列和中序序列构造出左子树，同理构造出右子树

我们来举个例子：

中序：3 2 1 4 5 7 6

后序：3 1 2 5 6 7 4

1.后序的最后一个元素为整个二叉树的根结点为4

2.在中序序列中找到4，那么4左边的序列为（3 2 1）即为以4为根结点的左子树中序序列，同理（5 7 6）则为右子树的中序序列

3.左子树中序序列（3 2 1）在后序中的序列是（3 1 2），可知这个左子树的根结点为2，同理右子树为的根结点为7

4……依次继续这样找

最后这个树为：

            4
       2          7
    3    1     5     6

这个过程的确难以理解，而且这是一个递归的过程

实现过程如下：

[L1,R1]为中序范围、[L2,R2]为后序范围

//把in_order[L1..R1]和post_order[L2..R2]建成一颗二叉树 
int build(int L1,int R1,int L2,int R2){
    if(L1>R1) return 0;
    int root = post_order[R2];//取根结点 
    int p = L1;
    while(in_order[p]!=root) p++;
    int cnt = p-L1;//左子树的结点个数
    lch[root] = build(L1,p-1,L2,L2+cnt-1);//根结点的左子结点的权值（其实还是新的根结点） 
    rch[root] = build(p+1,R1,L2+cnt,R2-1);//根结点的右子结点的权值
    return root;
}

我们分析一下这个递归函数 lch[root] = build(L1,p-1,L2,L2+cnt-1);

这里的 [L1,p-1]为左子树的中序序列，而[L2,L2+cnt-1]则为右子树的中序序列。

还是根据刚才举的例子来分析：


位置：0 1 2 3 4 5 6


中序：3 2 1 4 5 7 6

后序：3 1 2 5 6 7 4

4为这棵树的根结点，在中序序列中找到它的位置用p来表示，此时p=3，它的左子树的中序序列为（3 2 1），右子树的中序序列为（5 7 6）。cnt表示的是左子树的结点的个数，此时cnt=3，所以左子树的中序序列范围变成了[0,2]，后序序列范围为[0,2]

同理rch[root] = build(p+1,R1,L2+cnt,R2-1)也是这样分析。

前序和后序:

同理，前序就是序列第一个元素为根结点，构造方式同上

//把pre_order[L1..R1]和in_order[L2..R2]建成一颗二叉树 
int build(int L1,int R1,int L2,int R2)
{
    if(L1>R1) return 0;
    int root = pre_order[L1];
    int p = L2;
    while(in_order[p]!=root) p++;
    int cnt = R2-p;//右子树的结点个数 
    rch[root] = build(R1-cnt+1,R1,p+1,R2);//根结点的右子树的值（其实还是新的根结点） 
    lch[root] = build(L1+1,R1-cnt,L2,p-1);//根结点的左子树的值 
    return root;
}

紫书上那题是通过中序和后序构造的，这个递归我理解了好几天才真正理解，然后按照他这个思路把通过前序和中序来构造这个树的递归给写出来了。还是很不容易理解的。