二叉树的重构

先序遍历：根 -> 左 -> 右

中序遍历：左 -> 根 -> 右

后序遍历：左 -> 右 -> 根

知道任何一棵二叉树的先序和中序遍历的序列或者中序和后序的遍历序列，都能构造出唯一的一棵二叉树

下面先看一道PTA上的题引入思考

因为知道了先序遍历的特点，从第一个开始，都先从根开始。
把先序的根在中序中找到，以此分两分，左边是左子树，右边是右子树。递归分治重新生成一棵二叉树。

已知先序中序求后序

代码如下：

#include <iostream>
#include <string.h>
#include <stdio.h>
#include <algorithm>
using namespace std;
char pre[50],in[50];
typedef struct node{
	char data;
	node *l,*r;
}btnode,*btree;
int n,sum;
btree rebuildtree(int root,int start,int end)
{
	if(start>end)
	return NULL;
	int i;
	for(i=start;i<=end;i++)
	{
		if(in[i]==pre[root])
		break;
	}
	btree t=new btnode;
	t->data=pre[root];
	t->l=rebuildtree(root+1,start,i-1);
	t->r=rebuildtree(root+i-start+1,i+1,end);
	return t;
}
void h(btree root,int ans)
{
	if(root==NULL)
	return;
	sum=max(sum,ans);
	h(root->l,ans+1);
	h(root->r,ans+1);
	return;
}
int main()
{
	int i;
	btree r;
	cin>>n;
	for(i=1;i<=n;i++)
	{
		cin>>pre[i];
	}
	for(i=1;i<=n;i++)
	{
		cin>>in[i];
	}
	r=rebuildtree(1,1,n);
	h(r,1);
	cout<<sum<<endl;
	return 0;
}

已知中序后序求先序（原理相同）

代码如下：

#include <iostream>
using namespace std;
typedef struct node{
	char data;
	node *l,*r;
}btnode,*btree;
char in[10005],post[10005];
int n;
btree rebuildtree(int root,int start,int end)
{
	if(start>end)
	return NULL;
	int i;
	for(i=start;i<=end;i++)
	{
		if(in[i]==post[root])
		break;
	}
	btree t=new btnode;
	t->data=post[root];
	t->r=rebuildtree(root-1,i+1,end);
	t->l=rebuildtree(root-end+i-1,start,i-1);
	return t;
}
void print(btree root)
{
	if(root==NULL)
	return;
	cout<<root->data<<" ";
	print(root->l);
	print(root->r);
	return;
}
int main()
{
	int i;
	cin>>n;
	for(i=0;i<n;i++)
	{
		cin>>in[i];
	}
	for(i=0;i<n;i++)
	{
		cin>>post[i];
	}
	btree t=rebuildtree(n-1,0,n-1);
	print(t);
	return 0;
}

已知先序中序求后序

public class BinaryTree1 {
    private Node root;

    public void postOrder(){
        postOrder(root);
    }

    //二叉树构造完毕之后进行后续遍历
    private void postOrder(Node localroot) {
        if(localroot!=null){
            postOrder(localroot.left);
            postOrder(localroot.right);
            System.out.print(localroot.data+" ");
        }
    }

    public void InitTree(int[] preOrder,int[] inOrder){
        this.root=InitTree(preOrder,0,preOrder.length-1,inOrder,0,inOrder.length-1);
    }

    /**
     *
     * @param preOrder 先序遍历的数组
     * @param start1 递归每次遍历的数据段在先序遍历数组中的起始位置
     * @param end1 递归每次遍历的数据段在先序遍历数组中的终止位置
     * @param inOrder 中序遍历的数组
     * @param start2 递归每次遍历的数据段在中序遍历数组中的起始位置
     * @param end2 递归每次遍历的数据段在中序遍历数组中的终止位置
     * @return 返回本次递归所构造完毕的树的根节点（从子结点向上依次返回）
     */
    private Node InitTree(int[] preOrder, int start1, int end1, int[] inOrder, int start2, int end2) {
        if(start1>end1||start2>end2){
            return null;
        }
        int rootData=preOrder[start1];
        Node head=new Node(rootData);
        int rootindex=findIndexInArray(inOrder,rootData,start2,end2);
        /**
         * offset为以本次递归构造的节点为根节点的左子树的节点个数
         */
        int offset=rootindex-start2-1;
        Node left=InitTree(preOrder,start1+1,start1+offset+1,inOrder,start2,start2+offset);
        Node right=InitTree(preOrder,start1+offset+2,end1,inOrder,rootindex+1,end2);
        head.left=left;
        head.right=right;
        return head;
    }

    //检索出递归方法每次构造的节点在中序遍历数组中的索引
    public int  findIndexInArray(int[] a,int x,int begin,int end){
        for (int i = begin; i <=end; i++) {
            if(a[i]==x){
                return i;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        BinaryTree1 biTree=new BinaryTree1();
        int[] preOrder={2,1,8,7,4,3,6,5,7,9};
        int[] inorder={1,2,3,4,5,6,7,7,8,9};
        biTree.InitTree(preOrder,inorder);
        System.out.println("后序遍历");
        biTree.postOrder();
    }
}

解释：假设先序数组A B D E C F 中序数组D B E A F C

已知中序后序求先序

public class BinaryTree2 {
    private Node root;

    public void preOrder(){
        preOrder(root);
    }

    private void preOrder(Node localroot) {
        if(localroot!=null){
            System.out.print(localroot.data+" ");
            preOrder(localroot.left);
            preOrder(localroot.right);
        }
    }

    public void initTree(int[] inOrder,int[] postOrder){
        this.root=initTree(inOrder,0,inOrder.length-1,postOrder,0,postOrder.length-1);
    }

    private Node initTree(int[] inOrder, int start1, int end1, int[] postOrder, int start2, int end2) {
        if(start1>end1||start2>end2){
            return null;
        }
        int rootdata=postOrder[end2];
        Node head=new Node(rootdata);
        int rootindex=findIndexInArray(inOrder,rootdata,start1,end1);
        int offset=rootindex-1-start1;
        Node left=initTree(inOrder,start1,start1+offset,postOrder,start2,start2+offset);
        Node right=initTree(inOrder,rootindex+1,end1,postOrder,start2+offset+1,end2-1);
        head.left=left;
        head.right=right;
        return head;
    }

    public int  findIndexInArray(int[] a,int x,int begin,int end){
        for (int i = begin; i <=end; i++) {
            if(a[i]==x){
                return i;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        BinaryTree2 biTree=new BinaryTree2();
        int[] inorder={1,2,3,4,5,6,7,7,8,9};
        int[] postOrder={1,3,5,6,4,7,7,9,8,2 };
        biTree.initTree(inorder,postOrder);
        System.out.println("先序遍历");
        biTree.preOrder();
    }
}

解释同上。。。。。。

题目描述

如题所示，已知先序中序序列建树与求后序序列

算法原理

        利用递归和分制的思想，找到当前树先序序列的根节点，然后找到对应中序序列的位置，然后根据根节点在中序序列中的位置来判断左右子树分别的位置，然后继续对左右子树进行递归，最后得出结果

post(0, 0, 序列总长度-1);

void post(int root, int start, int end)

         首先是递归函数进入，其中三个形参分别代表的含义为

                root        先序序列中当前递归层中根节点的下标

                start        中序序列中子树的最左下标（子树开始的下标）

                end        中序序列中子树的最右下标（子树结束的下标）

if(start > end)     return ;

         递归结束的标志，因为子树的元素范围在下标[start,end]之内，当start>end的时候，说明以当前节点为空节点

int i = start;

        这里的i相当于只在中序遍历中有效，这里的i对于查找根节点root的先序序列完全没有意义，仅代表root在中序序列中的下标位置

例子：

 假设一棵二叉树为上面的形式，那么他的先序序列和中序序列为

递归原理：

        重点要解释一下这里的两条递归语句，分别代表递归当前根节点的左子树和当前根节点的右子树

        对于左子树

post(root + 1, start, i - 1);    //递归左子树

       如图可见，当遍历左子树的时候，

       对于先序序列，左子树的根节点为先序序列上一层根节点root的下一个节点，也就是root+1

       对于中序序列，因为是左子树，所以启始start值不变，end应该为在中序序列中找到的根节点i的前一个节点也就是i-1

        对于右子树

post(root + 1 + i - start, i + 1, end);

中序序列中的启始位置和结束位置都比较好确定，启始位置为i+1，结束位置为end

        主要的难点就在于root的确认，我们能知道在先序序列中，是按照根节点——左子树——右子树排列的，左子树的根节点在先序序列中就为本层的根节点+1（root+1），比较好确定，但是右子树的跟节点就没有那么好确认了，但是我们细想就可以知道，原本的根节点加上左子树的节点个数，那不就到了右子树了嘛，但是这个想法也不准确

        首先左子树的节点个数可以根据中序序列来判断，为i-start，但是根节点加上左子树的节点总数（root+（i-start））仅仅代表了左子树的最右侧节点，再加1才能代表右子树的第一个端点

        有这幅图就可以比较清楚的看出

        那么就引出了另一个问题了为什么根节点不能直接是i+1，而是要绕这么大一个圈子回来呢？

        这就需要下一步递归来判断了 

 这样就比较容易能看出来了，正确的根节点应该是6

但是i+1仅仅表示7，明显与答案不符

实际上i仅仅在中序序列中有意义，放在先序序列中并没有什么意义

核心代码实现

参考柳婼已知前序（先序）与中序输出后序_柳婼 の blog-CSDN博客

#include <cstdio>
using namespace std;
int pre[] = {1,2,3,4,5,6,7,8};
int in[] = {4,3,5,2,7,6,8,1};
void post(int root, int start, int end) {
    //root        先序序列中当前递归层中根节点的下标
    //start        中序序列中子树的最左下标（子树开始的下标）
    //end        中序序列中子树的最右下标（子树结束的下标）
    if(start > end)     return ;    /*递归结束的标志，因为子树的元素范围在下标[start,end]之内，当start>end的时候，说明以当前节点为空节点*/
    int i = start;    //这里的i对于查找根节点root的先序序列完全没有意义，仅代表root在中序序列中的下标位置
    while(i < end && in[i] != pre[root]) i++;    //寻找root在中序序列中的位置
    post(root + 1, start, i - 1);                //递归左子树
    post(root + 1 + i - start, i + 1, end);        //递归右子树
    printf("%d ", pre[root]);                    //输出后序序列
}
 
int main() {
    post(0, 0, 7);
    //这里的总长度是pre.size()-1,而不是pre.size()
    return 0;
}

例题