0


【数据结构】建立二叉树、二叉树的推导技巧

💟作者简介:大家好呀!我是路遥叶子,大家可以叫我叶子哦!❣️
📝个人主页:【路遥叶子的博客】
🏆博主信息:四季轮换叶,一路招摇胜!

     **专栏**

   【安利Java零基础】

   【数据结构-Java语言描述】

🐋希望大家多多支持😘一起进步呀!~❤️
🌈若有帮助,还请【关注➕点赞➕收藏】,不行的话我再努力努力呀!💪
————————————————
⚡版权声明:本文由【路遥叶子】原创、在CSDN首发、需要转载请联系博主。
🍁想寻找共同成长的小伙伴,请点击【Java全栈开发社区】

如果文章对您有帮助,就拿起小手赶紧给博主点赞💚评论❤️收藏💙 一下吧!

前言

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

逆向思维

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

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

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

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

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

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

🐋建立二叉树的方式

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

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

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

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

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

🐋二叉树的推导

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

🎃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


本文转载自: https://blog.csdn.net/zsy3757486/article/details/124568503
版权归原作者 路遥叶子 所有, 如有侵权,请联系我们删除。

“【数据结构】建立二叉树、二叉树的推导技巧”的评论:

还没有评论