树(Tree)是 n(n >= 0)个结点的有限集。n = 0 时称为空树。

在任意一颗非空树中:

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

相关定义

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

结点拥有的子树个数称为结点的度(Degree),树内各结点度的最大值为树的度。

度为 0 的结点称为叶结点终端结点,度不为 0 的结点称为非终端结点分支结点。除根结点外,分支结点也称为内部结点

结点的子树的根,称为该结点的孩子(Child),该结点称为孩子的双亲(Parent),同一个双亲的孩子之间互称兄弟(Sibling)

根到某一结点所经分支上所有结点称为这一结点的祖先;反之,以某结点为根的子树中的任一结点称为该结点的子孙

结点的层次(Level)从根开始定义,根为第一层,跟的孩子为第二层。双亲在同一层的结点互为堂兄弟

树中结点的最大层次称为树的深度(Depth)高度

如果树中结点的各子树看成从左至右是有次序的、不能互换的,则称该树为有序树,否则称为无序树

森林(Forest)是 m(m >= 0)棵互不相交的树的集合。

抽象数据类型

ADT : 树(Tree)

Data :树由一个根结点和若干棵子树构成。树中结点具有层次关系及相同数据类型。

Operation :

  • init(创建一个空树)
  • clear(将树清为空树)
  • isEmpty(判断是否为空树)
  • depth(返回树的深度)
  • getRoot(返回根结点)
  • getParent(返回双亲结点)
  • getLeftChild(返回最左孩子结点)
  • getRightSibling(返回最右兄弟结点)
  • insertChild(插入子树)
  • deleteChild(删除子树)

endADT

树的存储结构

树中各元素间的逻辑关系较线性表更为复杂,树中结点的孩子可能有多个,要表示结点间的逻辑关系,需要充分利用顺序存储和链式存储结构的特点,以下为 3 种常见的表示方法。

双亲表示法

以一组连续空间存储树的结点,每个结点除数据域外,附设一个指示其双亲结点在数组中位置的指针域, data|parent 。这样的存储结构可以很容易地通过指针域找到双亲结点。

如遇到的场景需要不但关注结点的双亲,又需要关注的孩子、兄弟,可以将其扩展为包含双亲域、长子域和右兄弟域的结构,data|parent|firstchild|rightsib

孩子表示法

由于每个结点可能有多棵子树,所以可以用多重链表,即每个结点有多个指针域,每个指针指向一棵子树的根结点,这种方法称作多重链表表示法

由于每个结点的度可能不同,所以多重链表表示法有两种方案:一是使每个结点的指针域个数等于树的度;二是每个结点指针域的个数等于该结点的度数,同时额外取一个位置存放结点的指针域个数。

前一种方案浪费空间,后一种方案需要维护结点的度,且各结点的链表结构不同,运算上会有损耗。

孩子表示法:把每个结点放到顺序存储的数组中,再对每个结点的孩子建立单链表以体现它们的关系,同时把这些链表的头指针存储在对应的数组元素中。

孩子表示法中包含两种结构,一是包含数据域和链表头指针的结构 data|firstchild ,另一个是孩子结点单链表的结构 child|next

如需要知道结点的双亲,可以综合双亲表示法和孩子表示法,增加双亲域 data|parent|firstchild ,即双亲孩子表示法

孩子兄弟表示法

任意一棵树,结点的第一个孩子如果存在就是唯一的,结点的右兄弟如果存在也是唯一。

孩子兄弟表示法,即设置两个指针,分别指向该结点的第一个孩子和该结点的右兄弟,data|firstchild|rightsib

孩子兄弟法最大的好处,就是将一棵复杂的树变成一棵二叉树,从而可以利用二叉树的特性和算法处理这棵树。

二叉树

二叉树的定义及特点

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

二叉树有以下特点:

  • 每个结点最多有两棵子树
  • 左子树和右子树有顺序
  • 即使树中某个结点只有一颗子树,也要区分左右

特殊二叉树

所有结点都只有左子树的二叉树叫左斜树,所有结点都只有右子树的二叉树叫右斜树,统称为斜树

如果二叉树的所有分支结点都存在左子树和右子树,且所有叶子结点都在同一层,这样的二叉树称为满二叉树

对一棵具有 n 个结点的二叉树按层序编号,如果编号为 i(1 <= i <= n)的结点与同样深度的满二叉树中编号为 i 的结点在二叉树中的位置完全相同,则这棵二叉树称为完全二叉树

二叉树性质

  • 二叉树的第 i 层之多有 $2^{i-1}$ 个结点(i >= 1)。
  • 深度为 k 的二叉树至多有 $2^{k} - 1$ 个结点(k >= 1)。
  • 对任何一棵二叉树 T ,如果其终端结点数为 n0,度为 2 的结点数为 n2,则 n0 = n2 + 1 。

对于二叉树,全部结点数 n = n0 + n1 + n2 。

结点间连线数 = n - 1 = n1 + 2*n2 。

综上得到 n0 + n1 + n2 - 1 = n1 + 2n2 ,进而得到 n0 = n2 + 1 。

  • 具有 n 个结点的完全二叉树深度为 $\lfloor log_2{n} \rfloor + 1$ ($\lfloor x \rfloor$ 表示不大于 x 的最大整数)。
  • 对一棵有 n 个结点的完全二叉树按层序编号,对任意结点 i(1 <= i <= n):
    • 如果 i = 1,则 i 是二叉树的根,无双亲;如果 i > 1 ,则其双亲是结点 $\lfloor i/2 \rfloor$ 。
    • 如果 2i > n,则结点 i 无左孩子;否则其左孩子为结点 2i 。
    • 如果 2i + 1 > n,则结点 i 无右孩子;否则其右孩子为结点 2i + 1 。

二叉树的存储结构

二叉树的顺序存储结构,就是用一维数组,按完全二叉树中的层序依次存储二叉树中的结点,不存在的结点用空占位表示。右斜树等情况会浪费存储空间,所有顺序存储结构一般用于完全二叉树。

二叉树的链式存储结构成为二叉链表,即每个结点包含一个数据域和两个孩子指针域,lchild|data|rchild 。如果有需要,可以增加双亲指针域,称为三叉链表。

二叉树的遍历

二叉树的遍历,是指按照某种次序依次访问二叉树中所有结点,使得每个结点被访问一次且仅被访问一次。

如果限定了从左到右的遍历方式,可分为以下 4 种:

  • 前序遍历:先访问根结点,然后前序遍历左子树,再前序遍历右子树。
  • 中序遍历:从根结点开始(不是先访问根结点),中序遍历根结点左子树,然后访问根结点,再中序遍历右子树。
  • 后续遍历:按从左到右、先叶子后结点的方式遍历访问左右子树,最后访问根结点。
  • 层序遍历:从树的第一层开始,从上而下逐层访问。

二叉树的定义是用递归的方式,实现遍历算法也可以采用递归。

已知前序(或后续)遍历序列,和中序遍历序列,可以唯一确定一棵二叉树。

线索二叉树

包含 n 个结点的二叉链表,有 2n 个指针域,分支线数为 n - 1 ,也是是存在 2n - (n - 1) = n + 1 个空指针域。

这些空指针域可以用来存放结点在某种遍历次序下的前驱和后继结点的地址。这种指向前驱和后继的指针称为线索,加上线索的二叉链表称为线索链表,相应的二叉树称为线索二叉树。对二叉树以某种次数遍历使其变为线索二叉树的过程称为线索化

树、森林与二叉树的转换

对树的处理非常复杂,很难去研究树的性质和算法,转为二叉树就容易得多。

以下为几种转换的具体步骤。

树转为二叉树
  1. 所有兄弟结点间加线。
  2. 对树的每个结点,保留它与第一个孩子结点的连线,去掉与其他孩子结点间的连线。
  3. 层次调整。
森林转换为二叉树
  1. 把每棵树转为二叉树。
  2. 从第二棵二叉树开始,依次把后一棵二叉树的根结点作为前一棵二叉树根结点的右孩子,并用线连接。
二叉树转为树
  1. 若某结点的左孩子结点存在,将这个左孩子的右孩子结点、右孩子的…右孩子结点都作为此结点的孩子,将该结点与这些右孩子结点用线连接。
  2. 删除原二叉树中所有结点与其右孩子结点的连线。
  3. 层次调整。
二叉树转为森林
  1. 从根结点开始,若右孩子存在,则删除与右孩子结点的连线,再处理分离后的二叉树,直到所有右孩子连线都被删除。
  2. 将每个分离后的二叉树转为树。

树与森林的遍历

树的遍历分为两种方式:

  • 先根遍历:先访问树的根结点,然后依次先根遍历根的每棵子树。
  • 后根遍历:先后跟遍历根结点的每棵子树,然后访问根结点。

森林的遍历也分为两种方式:

  • 前序遍历:每棵树依次先根遍历。
  • 后序遍历:每棵树依次后根遍历。

赫夫曼树

从树中的一个结点到另一个结点之间的分支构成两个结点之间的路径,路径上的分支数目称作路径长度。树的路径长度就是从根结点到每个结点路径长度之和。

结点的带权路径长度为路径长度与权的乘积,树的带权路径长度为树中所有叶子结点的带权路径长度之和。

假设有 n 个权值 {w1, w2, … ,wn} ,构造一棵有 n 个叶子结点的二叉树,每个叶子结点权值为 wk ,每个叶子结点的路径长度为 lk ,其中带权路径长度 WPL 最小的二叉树称为赫夫曼树

赫夫曼树的构造方法:

  1. 将带权叶子结点按权值由小到大排序。
  2. 取前 2 个权值最小的结点作为一个新结点 N1 的左右孩子结点(权值较小的是左孩子),新结点的权值为 2 个结点权值之和。
  3. 用 N1 结点替换其 2 个孩子结点,插入结点序列,并保持序列权值从小到大的顺序。
  4. 重复步骤 2 。

设需要编码的字符集为 {d1, d2, … , dn} ,各个字符在电文中出现的次数或频率集合为 {w1, w2, … , wn} ,以字符集作为叶子结点,以次数或频次为权值构建一棵赫夫曼树。规定左分支代表 0 ,右分支代表 1 ,从根结点到叶子结点所经过的路径分支组成的 0 和 1 的序列即该结点对应字符的编码,称为赫夫曼编码。

打赏
  • 版权声明: 本博客所有文章除特别声明外,著作权归作者所有。转载请注明出处!
  • © 2016-2020 姜越

谢谢老板

支付宝
微信