• 【408数据结构与算法】—树和二叉树(二十七)


    【408数据结构与算法】—树和二叉树(二十七)

    一、树的定义

    在这里插入图片描述

    树的定义

    • 树是n(n>=0)个结点的有限集。
    • 若n=0;称为空树

    若n>0;则它满足如下两个条件

    1. 有且仅有一个特定的称为根的结点
    2. 其余结点可分为m(m>=0)个互不相交的有限集T1,T2,T3……Tm.其中每一个集合本身又是一棵树,并称为根的子树。

    树是n个结点的有限集,显然,树的定义时一个递归的定义

    在这里插入图片描述 树的其他集合

    在这里插入图片描述

    二、树的基本术语

    • 结点:数据元素以及指向子树的分支
      • 根结点:非空树中无前驱结点的结点
      • 结点的度:结点拥有的子树数
      • 树的度:树内各结点的度的最大值
      • 叶子: 度=0。终端结点
      • 分支结点:度≠0。非终端结点,根结点以外的分支结点称为内部结点
    • 结点的子树称为该结点的孩子,该结点称为孩子的双亲
      • 兄弟结点:如果几个结点有共同的前驱结点,我们把这些结点叫做兄弟结点
      • 堂兄弟结点:若两个结点的双亲结点在同一层,我们把这两个结点叫做堂兄弟结点
      • 结点的祖先:从根结点到该结点所经分支上的所有结点
      • 结点的子孙:以某结点为根的子树中的任一结点
    • 树的深度:树中结点的最大层次
      请添加图片描述
    • 有序树:树中的结点的各子树从左至右有次序(左边的为第一个孩子)
    • 无序树:树中结点的各子树无次序
    • 森林:是m(m>=0)棵互不相交的树的集合把根结点删除树就变成了森林
    • 一棵树可以看成是一个特殊的森林。给森林中的各子树加上一个双亲结点,森林就变成了树。
    • 树一定是森林,但森林不一定是树

    在这里插入图片描述

    三、树结构和线性结构的比较

    在这里插入图片描述

    四、二叉树的定义

    一棵二叉树是结点的一个有限集合,该集合或者为空,或者是由一个根节点加上两棵别称为左子树和右子树的二叉树组成。

    二叉树的特点:

    1、每个节点最多有两棵子树,即不存在超过度为2的节点。

    2、二叉树的子树有左右之分,且左右不能颠倒。
    3、二叉树可以是空集合,根可以有空的左子树或空的右子树。

    注意:二叉树不是树的特殊情况,他们是两个概念

    1. 二叉树结点的子树要区分左子树和右子树,即使只有一棵树也要进行区分,说明他是左子树,还是右子树。
    2. 树当结点只有一个孩子时,就无序区分他是左子树还是右子树,因此二者是不同的,这是二叉树与树的主要区别
      在这里插入图片描述
      在这里插入图片描述
      也就是二叉树每个结点位置或者说次序都是固定的,可以是空,但是不可以说他没有位置,而树的结点位置是相对于别的结点来说的,没有别的结点时,他就为所谓左右了。

    思考:具有3个结点的二叉树可能有几种不同的形态?普通树呢?

    二叉树有五种形态:
    在这里插入图片描述

    树有两种形态:
    在这里插入图片描述

    二叉树的五种形态

    在这里插入图片描述

    五、二叉树的抽象数据类型定义

    在这里插入图片描述
    二叉树常用的基本操作在这里插入图片描述

    六、二叉树的性质

    在这里插入图片描述

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    七、两种特殊的二叉树

    ❤️满二叉树

    满二叉树:一棵深度为 k且有2^k-1个结点的二叉树称为满二叉树

    特点:

    • 每一层上的结点数都是最大结点数(即每层都满)
    • 叶子结点全部在底层
      在这里插入图片描述
      对满二叉树进行编号
      编号规则:从根结点开始,自上而下,自左而右;每一结点位置都有元素

    思考:下图中的二叉树是满二叉树吗?
    在这里插入图片描述

    • 满二叉树在同样深度的二叉树中结点个数最多
    • 满二叉树在同样深度的二叉树中叶子结点个数最多

    ❤️❤️完全二叉树

    深度为k的具有n个结点的二叉树,当且仅当每一个结点都与深度为k的满二叉树中编号为1~n的结点一一对应时,称之为完全二叉树

    完全二叉树是由满二叉树而引出来的。对于深度为K的,有n个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。

    一棵二叉树至多只有最下面的一层上的结点的度数可以小于2,并且最下层上的结点都集中在该层最左边的若干位置上,而在最后一层上,右边的若干结点缺失的二叉树,则此二叉树成为完全二叉树。
    在这里插入图片描述

    判断下列是否是二叉树

    在这里插入图片描述
    注意:在满二叉树中,从最后一个结点开始,连续去掉任意一个结点,即使一棵完全二叉树,注意一定是连续去掉
    在这里插入图片描述
    特点:

    • 叶子只能分布在层次最大的两层上
    • 对任一结点,如果其右子树的最大层次为i,则其左子树的最大层必为i或i+1

    八、二叉树的存储结构

    实现:按满二叉树的结点层次编号,依次存放二叉树中的数据元素
    在这里插入图片描述
    例:二叉树结点数值采用顺序存储结构,如图所示,画出二叉树的表示图
    在这里插入图片描述

    二叉树的顺序存储特点:

    最坏情况:深度为K的且有K个结点的单支树需要长度为2^k-1的一维数组
    特点:结点间关系蕴含在其存储位置中,浪费空间,适于存满二叉树和完全二叉树
    在这里插入图片描述

    在这里插入图片描述

    二叉树的链式存储结构

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在n个结点的二叉链表中,有n+1个空指针域
    空指针数目=2n-(n-1)=n+1
    在这里插入图片描述
    三叉链表
    在这里插入图片描述

  • 相关阅读:
    【图形学】26 透明效果基础
    WMS系统出库管理:优化仓储流程
    获取和设置小程序和h5的页面栈
    论文解读(PPNP)《Predict then Propagate: Graph Neural Networks meet Personalized PageRank》
    python实现调和反距离空间插值法AIDW
    【Golang】DFA算法过滤敏感词Golang实现
    基于PHP+MySQL高校教务选课系统的设计与实现
    H2 数据库的 expected “identifier 错误
    VulnHub Tre
    SQLSERVER 查询阻塞SQL以及锁
  • 原文地址:https://blog.csdn.net/m0_46374969/article/details/127976391