前言

现在我们已经了解到的二叉树的特性及遍历方式，那么你知道如何根据三种不同的遍历方式将二叉树推导进行出来吗?那你又需要用多长的时间呢？今天看完文章1分钟带来玩转二叉树，高效正确建立二叉树。

逆向思维

逆向思维指的是反向思考问题的能力。

这种人思维活跃，想法别致，遇到问题能用常人想不到的方式解决。

众所周知的“司马光砸缸。”有人落水，常规的思维模式是“救人离水”，而司马光面对紧急险情，运用了逆向思维，果断地用石头把缸砸破，“让水离人”，救了小伙伴性命。

运用好逆向思维去思考和处理问题，实际上就是以“出奇”去达到“制胜”，让问题变得更简单。

而我们的二叉树的建立，推导过程，就是运用了逆向思维。在得到的二叉树前序、中序、后序遍历的结果后，在根据2种不同的遍历结果，反向推导出二叉树集合。

💙 💜 ❤️ 💚💙 💜 ❤️ 💚💙 💜 ❤️ 💚💙 💜 ❤️💙 💜 ❤️ 💚💙 💜 ❤️ 💚💙 💜 💚

🐋建立二叉树的方式

四种方式可以建立二叉树：

由先根和中根遍历序列建二叉树

由后根和中根遍历序列建二叉树

由标明空子树的先根遍历建立二叉树

由完全二叉树的顺序存储结构建立二叉链式存储结构

🐋二叉树的推导

🌲由先根和中根遍历序列建二叉树

🎃1）先根和中根原理

技巧总结：

通过先序遍历获得根结点（第一个结点）。因为先序遍历总是先遍历第一个结点，也就是根结点。

通过已知的根结点在中序遍历可以分别确定左子树和右子树的结点元素。因为中序遍历总是在遍历完左子树中所有结点后，放在中间遍历的，遍历完后又继续遍历右子树所有结点。

🎃2）实例分析步骤：

第一步：由先序遍历得知A结点为根结点，则可拆分中序遍历得A结点的左右子树结点元素

第二步：根据先序遍历，首先遍历根结点，遍历完之后会去遍历左子树的第一个结点，也就是上图先序遍历A后面的B结点。由此在左子树元素DBGE中可以得出B结点为父结点。依次类推。

先序遍历：根结点—左子树—右子树【ABDEGCFH】

左子树：

1）由前序BDEG，中序DBGE得知：B为父结点，在中序遍历中位于B的左边元素D，为B的左结点，右边元素GE为B的右结点。

2）依次由1步骤进行判断。由前序BDEG，中序DBGE得知：D为下一个结点，且D没有左右结点；E为下一个结点，且E没有左子树，有一个右子树G

右子树：

1）由前序遍历顺序中CFH，得知C是父结点，FH为左孩子；F是父结点，H为右孩子。

核心技巧：

根据先序遍历找根结点和父结点

根据中序遍历确定左右子树的元素位置

🎃3）算法实现

/** 例如：new BiTree("ABDEGCFH","DBGEAFHC",0,0,8);
* @param preOrder 先序遍历序列
* @param inOrder  中序遍历序列
* @param preIndex 在preOrder中开始位置
* @param inIndex  在inOrder中开始位置
* @param count 结点数
*/
public BiTree(String preOrder,String inOrder,int preIndex,int inIndex,int count) {
    if(count > 0) {
        //1 通过先序获得根结点
        char r = preOrder.charAt(preIndex);
        //2 中序中，根结点的位置
        int i = 0 ;
        for(; i < count ; i ++) {
            if(r == inOrder.charAt(i + inIndex)) {
                break;
            }
        }
        //3 通过中序，截取左子树和右子树
        root = new BiTreeNode(r);
        root.lchild = new BiTree(preOrder,inOrder,preIndex+1, inIndex, i).root;
        root.rchild = new BiTree(preOrder,inOrder,preIndex+1+i,inIndex + i + 1, count-i-1).root;
    }
}

💙 💜 ❤️ 💚💙 💜 ❤️ 💚💙 💜 ❤️ 💚💙 💜 ❤️💙 💜 ❤️ 💚💙 💜 ❤️ 💚💙 💜 💚

🌲由后根和中根遍历序列建二叉树

🎃 1）后根和中根原理

技巧总结：

通过后序遍历获得根结点（最后一个结点）。

通过根结点在中序遍历确定左子树和右子树。

与先序、中序遍历建立二叉树,异曲同工。不同的是：根据后序遍历获取根结点。由于后序遍历的顺序，每一个左右根组合，每次根都是最后遍历的，所以我们获取根结点，要从后序遍历的后面往前依次确定根结点。

🎃2）实例分析步骤：

已知二叉树，中根遍历序列为：9,3,15,20,7、后根遍历序列为：9,15,7,20,3 重建二叉树？

💙 💜 ❤️ 💚💙 💜 ❤️ 💚💙 💜 ❤️ 💚💙 💜 ❤️💙 💜 ❤️ 💚💙 💜 ❤️ 💚💙 💜 💚

🌲由标明空子树的先根遍历建立二叉树

🎃 1）概述

仅使用先根遍历序列无法唯一确定一颗二叉树，例如：“AB”，B可以是左孩子，也可以是右孩子。

在先根遍历序列中加入==空树==信息，从而确定结点与双亲、孩子与兄弟间的关系，从而唯一确定一颗二叉树。

表名空子树的先序遍历序列：二叉树中每一个结点都必须有孩子或#

空树：以字符“#”表示

根节点A：以字符串“A##”表示

🎃 2）实例演示:

前言：已知以下二叉树 ：

现我们知道字符串“AB#C##D##” ，根据字符串建立二叉树

下图树，以字符串“ABDH#K###E##CFI###G#J##”表示 ：

🎃3）算法

建立二叉链表算法分析：

若读取的字符是“#”，则建立空树；否则

建立根节点

递归建立左子树的二叉链表

递归建立右子树的二叉

算法

采用先序，每一个结点都根左右

private static int index = 0;     //用于记录preStr的索引值
public BiTree(String preStr) {
    char c = preStr.charAt(index++);
    if(c != '#') {
        root = new BiTreeNode(c);         //根
        root.lchild = new BiTree(preStr).root;    //左
        root.rchild = new BiTree(preStr).root;    //右
    } else {
        root = null;
    }
}

由完全二叉树的顺序存储结构建立二叉链式存储结构

🎃 1）由二叉树的特性5可知，结点编号规则：

根节点的编号为0

编号为i的结点

左孩子的编号为2i+1

右孩子的编号为2i+2

完全二叉树及其顺序存储（层次遍历序列）

🎃 2) 算法：

public BiTreeNode createBiTree(String sqBiTree, int index) {
    BiTreeNode root = null;
    if(index < sqBiTree.length()) {
        root = new BiTreeNode(sqBiTree.charAt(index));
        root.lchild = createBiTree(sqBiTree, 2*index+1);
        root.rchild = createBiTree(sqBiTree, 2*index+2);
    }
    return root;
}

小试牛刀

练习1：

已经二叉树，先序序列为abcdefg，中序序列为cbdaegf，重建二叉树？

练习2：

已经二叉树，前序遍历序列为{1,2,4,7,3,5,6,8}，中序遍历序列{4,7,2,1,5,3,8,6}，后序遍历序列是？【先建树在写二叉树】

练习3 ：

已知一棵树二叉树的先根遍历和中根遍历的序列分别为：A B D G H C E F I和G D H B A E C I F，请画出此二叉树，并写出它的后根遍的序列？

练习4：

已知二叉树，中根遍历序列为：6,3,4,1,5,8,2,7 后根遍历序列为：3,6,1,8,5,7,2,4 前根遍历序列？

练习5：

已知一棵树二叉树的后根遍历和中根遍历的序列分别为：A C D B G I H F E 和A B C D E F G H I 请画出该二叉树，并写出它的先根遍历的序列。