当前位置:   article > 正文

数据结构—树(自学笔记)(郝斌)_树的每个结点有且仅有一个父节

树的每个结点有且仅有一个父节

树的定义

专业定义

  • 有且只有一个称为根的节点
  • 有若干个互不相交的子树,这些子树本身也是一颗树

通俗的定义

  • 树是由节点和边组成
  • 每个节点只有一个父节点但可以有多个子节点
  • 但有一个节点例外,该节点没有父节点,此节点称为根节点

相关术语

  • 节点
  • 双亲节点
  • 子节点
  • 子孙
  • 兄弟(同一个双亲节点)
  • 堂兄弟(它们的双亲节点在同一层)
  • 层次
    • 从根节点到最底层节点的层数称为深度或者高度
    • 根节点是第一层
  • 叶子节点
    • 没有子节点的节点
  • 非终端节点
    • 实际非叶子节点
    • 子节点的个数
  • 树的度
    • 树中节点最大的度
      在这里插入图片描述

树的分类

一般树

  • 任意一个节点的子节点的个数都不受限制

二叉树

  • 任意一个节点的子节点个数最多两个,且子节点的位置不可更改
二叉树的分类
  • 一般二叉树
  • 满二叉树
    • 在不增加树层数的前提下,无法再添加一个节点的二叉树就是满二叉树
    • 高度为h,且有 2 h − 1 2^h-1 2h1 个节点的二叉树
  • 完全二叉树
    • 如果只是删除了满二叉树最底层最右边的连续若干个节点,这样形成的二叉树就是完全二叉树
  • 扩充二叉树(2-树)
    • 仅存在度为2和0的节点
    • 不存在度为1的节点
二叉树的性质

在这里插入图片描述

  1. 在二叉树的第i层上至多有 2 i − 1 2^{i-1} 2i1个节点
  2. 深度为k的二叉树至多有 2 k − 1 2^k-1 2k1个节点
  3. 对如何一棵二叉树T,如果其终端节点数为 n 0 n_0 n0,度为2的节点数为 n 2 n_2 n2,则 n 0 n_0 n0 = n 2 n_2 n2 + 1;
  4. 具有n个节点的完全二叉树的深度为 ⌊ l o g 2 n ⌋ \lfloor log_2n \rfloor log2n+1( ⌊ x ⌋ \lfloor x \rfloor x表示不大于x的最大整数)
  5. 如果对一棵有n个节点的完全二叉树,(其深度为 ⌊ l o g 2 n ⌋ \lfloor log_2n \rfloor log2n+1)的节点按层序编号(从第1层到第 ⌊ l o g 2 n ⌋ \lfloor log_2n \rfloor log2n+1层,每层从左到右),对任一节点i(1 ≤ \leq i ≤ \leq n)有:
    1. 如果i = 1,则节点i是二叉树的根,无双亲;如果i >1,则其双亲是节点 ⌊ i / 2 ⌋ \lfloor i/2 \rfloor i/2.
    2. 如果2i > n,则节点i无左孩子,(节点i为叶子节点);否则其左孩子是节点2i。
    3. 如果 2i+1 > n,则节点i无右孩子,否则其右孩子节点是2i+1.
      在这里插入图片描述
对于第一条来说是显然的,i = 1时就是根节点。 i > 1时,比如节点7,它的双亲就是 ⌊ 7 / 2 ⌋ \lfloor 7/2 \rfloor 7/2=3,节点9,它的双亲就是 ⌊ 9 / 2 ⌋ \lfloor 9/2 \rfloor 9/2=4。
第二条,比如节点6,因为2 × \times × 6 =12超过了节点总数10,所以节点6无左孩子,它是叶子节点。同样,而节点5,因为2 × \times × 5=10正好是节点总数10,所以它的左孩子是节点10.
第三条,比如节点5,因为2 × \times × 5+1 =11,大于节点总数10,所以它无右孩子。而节点3,因为2 × \times × 3+1 = 7小于10,所以它的右孩子是节点7.

森林

  • n个互不相交的树的集合

树的存储

在这里插入图片描述

  • 二叉树的存储
    • 连续存储【完全二叉树】
      • 优点
        • 查找某个节点的父节点和子节点(包括判断有没有子节点)速度很快
      • 缺点:
        • 耗用内存空间过大
    • 链式存储

  • 一般树的存储
    • 双亲表示法
      • 求父节点方便
    • 孩子表示法
      • 求子节点方便
    • 双亲孩子表示法
      • 求父节点和子节点都很方便
    • 二叉树表示法
      • 把一个普通树转化成二叉树存储
        • —>大概思路
          • 设法保证任意一个节点的
            • 左指针域指向他的第一个孩子
            • 右指针域指向它的第一个兄弟
          • 只要能满足此条件,就可以把一个普通树转化为二叉树
          • 一个普通树转化成的二叉树一定没有右子树
            在这里插入图片描述
        • 具体方法:
        1. 加线。在所有兄弟节点之间加一条连线。
        2. 去线。对树中每个节点,只保留它与第一个孩子节点的连线,删除它与其他孩子节点之间的连线。
        3. 层次调整。以树的根节点为轴心,将整棵树顺时针旋转一定的角度,使其看起来像个二叉树。注意⚠️第一个孩子是二叉树节点的有孩子,兄弟转换过来的孩子是节点的右孩子。
          在这里插入图片描述
        • 把森林转化为二叉树
          • 大概思路:
          • 森林是由若干棵树组成的,所以完全可以理解为,森林中的每一棵树都是兄弟,可以安装兄弟的处理办法来操作。
  • 森林的存储
    • 先把森林转化为二叉树,再存储二叉树

二叉树的操作

  • 遍历
    • 先序遍历【先访问根节点
      • 先访问根节点
      • 再先序访问左子树
      • 再先序访问右子树
      • 例子:在这里插入图片描述
    • 中序遍历【中间访问根节点
      • 中序遍历左子树
      • 再访问根节点
      • 再中序遍历右子树
      • 例子:在这里插入图片描述
    • 后序遍历【最后访问根节点
      • 后序遍历左子树
      • 后序遍历右子树
      • 再访问根节点
      • 例子:在这里插入图片描述
  • 已知两种遍历序列求原始序列
    • 通过先序和中序 或者 中序和后序我们可以还原出原始的二叉树
    • 但是通过先序和后序是无法还原出原始的二叉树的
      • ​ 换种说法:
        • 只有通过先序和中序,或通过中序和后序才可以唯一确定一个二叉树
    • 例子(1):在这里插入图片描述
    • 例子(2):在这里插入图片描述

应用

  • 树是数据库中数据组织一种重要形式
  • 操作系统子父进程的关系本身就是一棵树
  • 面向对象语言中类的继承关系本身就是一棵树
  • 赫夫曼数
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/Li_阴宅/article/detail/747780
推荐阅读
相关标签
  

闽ICP备14008679号