💟作者简介：大家好呀！我是路遥叶子，大家可以叫我叶子哦！❣️
📝个人主页：【路遥叶子的博客】
🏆博主信息：四季轮换叶，一路招摇胜！**专栏** 【安利Java零基础】 【数据结构-Java语言描述】🐋希望大家多多支持😘一起进步呀！~❤️
🌈若有帮助，还请【关注➕点赞➕收藏】，不行的话我再努力努力呀！💪
————————————————
⚡版权声明：本文由【路遥叶子】原创、在CSDN首发、需要转载请联系博主。
🍁想寻找共同成长的小伙伴，请点击【Java全栈开发社区】
如果文章对您有帮助，就拿起小手赶紧给博主点赞💚评论❤️收藏💙 一下吧！
前言
现在我们已经了解到的二叉树的特性及遍历方式，那么你知道如何根据三种不同的遍历方式将二叉树推导进行出来吗?那你又需要用多长的时间呢？今天看完文章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）算法
- 建立二叉链表算法分析：- 若读取的字符是“#”，则建立空树；否则1. 建立根节点2. 递归建立左子树的二叉链表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 请画出该二叉树，并写出它的先根遍历的序列。
如果文章对您有帮助，就拿起小手赶紧给博主点赞💚评论❤️收藏💙 一下吧！
想要了解更多吗？没时间解释了，快来点一点！
路遥叶子的博客_CSDN博客-数据结构,安利Java零基础,spring领域博主路遥叶子擅长数据结构,安利Java零基础,spring,等方面的知识https://blog.csdn.net/zsy3757486?type=blog
版权归原作者 路遥叶子 所有， 如有侵权，请联系我们删除。