【数据结构】建立二叉树、二叉树的推导技巧
💟作者简介：大家好呀！我是路遥叶子，大家可以叫我叶子哦！❣️
📝个人主页：【路遥叶子的博客】
🏆博主信息：四季轮换叶，一路招摇胜！专栏
【安利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）算法
-
建立二叉链表算法分析：
-
若读取的字符是“#”，则建立空树；否则
-
建立根节点
-
递归建立左子树的二叉链表
-
递归建立右子树的二叉
-
算法
-
采用先序，每一个结点都
根左右
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
创作打卡挑战赛 
赢取流量/现金/CSDN周边激励大奖神唱ktv下载