💟作者简介:大家好呀!我是路遥叶子,大家可以叫我叶子哦!❣️
📝个人主页:【路遥叶子的博客】
🏆博主信息:四季轮换叶,一路招摇胜!专栏
【安利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