美文网首页
程序猿必修课之数据结构(十)树1

程序猿必修课之数据结构(十)树1

作者: Xiao_Mai | 来源:发表于2018-07-10 18:22 被阅读0次

    上一章:程序猿必修课之数据结构(九)串

    你还在为开发中频繁切换环境打包而烦恼吗?快来试试 Environment Switcher 吧!使用它可以在app运行时一键切换环境,而且还支持其他贴心小功能,有了它妈妈再也不用担心频繁环境切换了。https://github.com/CodeXiaoMai/EnvironmentSwitcher

    树是一对多的数据结构

    树的定义

    树(Tree)是 n (n ≥ 0)个结点的有限集。

    n = 0 时,称为空树。

    在任意一棵非空树中:

    • 有且仅有一个特定的根(root)结点。
    • 当 n > 1 时,其余结点可分为 m (m > 0) 个互不相交的有限集,其中每一个集合本身又是一棵树,并且称之为根的子树(SubTree)。

    其实树的定义用到了递归的方法。

    常用名词概念

    树的每一个结点包含一个数据元素和若干个指向其子树的分支。

    结点的度:结点拥有的子树的个数称为结点的度(Degree)。

    度为 0 的结点称为叶结点(Leaf)终端结点

    度不为 0 的结点称为非终端结点分支结点

    除根结点之外,分支结点也称为内部结点

    树的度:树内各结点的度的最大值。

    下图中,结点度的最大值是结点 D 的度为 3,所以树的度也为 3。

    image

    结点的层次(Level) 从根开始,根为第一层。

    树中结点的最大层次称为树的深度高度,上图中树的深度为 4。

    如果把树中各子树看成从左到右是有序的,不能互换的,则称该树为有序树,否则称为无序树

    森林:m (m ≥ 0)棵互不相交的树的集合。

    线性结构与树结构的对比

    线性结构 树结构
    第一个数据元素:无前驱
    最后一个数据元素:无后继
    中间元素:一个前驱一个后继
    根结点:无双亲,唯一
    叶结点:无孩子,可以多个
    中间结点:一个双亲,多个孩子

    树的存储结构

    树的存储结构的3种表示方法:双亲表示法、孩子表示法、孩子兄弟表示法。

    双亲表示法

    用一组连续空间存储树的结点,同时每个结点包含数据域和一个指向其双亲的指针域。

    结点 :

    data parent

    其中 data 是数据域,存储结点的数据信息。而 parent 是指针域,存储该结点的双亲在数组中的下标。由于根结点没有双亲,所以我们约定根结点的位置域设置为 - 1,这样所有的结点就都保存了它的双亲的位置了。

    二叉树

    二叉树( Binary Tree) 是 n(n ≥ 0) 个结点的有限集合,该集合或者为空集(称为空二叉树),或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成 。

    二叉树的特点:

    1. 每个结点最多有两棵子树,所以二叉树中不存在度大于2的结点。注意:不是只有两棵子树,而是最多。没有子树或者有一棵子树都是可以的。
    2. 左子树和右子树是有顺序的,次序不能任意颠倒。
    3. 即使树中某结点只有一棵子树,也要区分是左子树还是右子树。如下图:树 1 和 树 2 是同一棵树,但它们却是不同的二叉树。
    不同的二叉树

    二叉树的五种形态

    1. 空二叉树。
    2. 只有一个根结点。
    3. 根结点只有左子树。
    4. 根结点只有右子树。
    5. 根结点既有左子树又有右子树。

    特殊二叉树

    1. 斜树
      所有的结点都只有左子树的二叉树叫左斜树;所有结点都只有右子树的二叉树叫右斜树。左斜树和右斜树统称为斜树。斜树有很明显的特点:就是每一层都只有一个结点,结点的个数与二叉树的深度相同。
    2. 满二叉树
      在一棵二叉树中,如果所有分支结点都存在左子树和右子树,并且所有叶子都在同一层上,这样的二叉树称为满二叉树。
      满二叉树的特点:
      1) 叶子只能出现在最下一层。
      2) 非叶子结点的度一定是 2。
      3) 在同样深度的二叉树中,满二叉树的结点个数最多,叶子数最多。
    3. 完全二叉树
      对一棵具有 n 个结点的二叉树按层次编号,如果编号为 i (1≤ i ≤ n) 的结点与同样深度的满二叉树中编号为 i 的结点在二叉树中位置完全相同,则这棵二叉树称为完全二叉树。
      完全二叉树的特点:
      1)叶子结点只能出现在最下两层。
      2)最下层的叶子一定集中在左边连续位置。
      3)倒数第二层,若有叶子结点,一定都在右边连续位置。
      4)如果结点度为 1,则该结点只有左孩子,不存在只有右孩子的情况。
      5)同样结点数的二叉树,完全二叉树的深度最小。

    二叉树的性质

    1. 在二叉树的第 i 层上至多有 2 i-1 个结点(i ≥ 1)。
    2. 深度为 k 的二叉树至多有 2 k - 1个结点(k ≥ 1)。
    3. 具有 n 个结点的完全二叉树的深度为 ⌊ log2n ⌋ + 1 (⌊x⌋ 表示不大于 x 的最大整数)。

    二叉树的存储结构

    顺序存储结构

    二叉树的顺序存储结构就是用一维数组存储二叉树中的结点,并且结点的存储位置,也就是数组的下标要能体现结点之间的逻辑关系。

    将一棵完全二叉树用顺序存储结构存储。

    完全二叉树.png

    将这棵二叉树存入到数组中,相应的下标对应其同样的位置

    对于一般的二叉树,可以将其按完全二叉树编号,把不存在的结点设置为“^” 就可以了。

    但是当一棵深度为 K 的右斜树,它只有 k 个结点,却要分配 2k -1 个存储单元,这样对存储空间造成浪费。所以,顺序存储结构一般只用于完全二叉树

    二叉链表

    二叉树每个结点最多有两个孩子,所以每个结点包含一个数据域和两个指针域,这样的链表叫做二叉链表。

    其中 data 是数据域,lchild 和 rchild 都是指针域,分别存放左孩子和右孩子的指针。

    相关文章

      网友评论

          本文标题:程序猿必修课之数据结构(十)树1

          本文链接:https://www.haomeiwen.com/subject/ovxiixtx.html