数据结构-树的相关概念

算法与数据结构

树

树(Tree)的定义：n(n~0)个结点的有限集，n=0时称为空树，在任意一棵非空树中:

• 有且仅有一个特定的称为根（Root）的结点
• n>1时，其余结点可分为m(m>O)个互不相交的有限集T1、T2、……Tm，其中每一个集合本身又是一棵树，并且称为根的子树(SubTree)

n=0：空树
n>0：非空树 根结点是唯一的，不可能存在多个根结点
含子树时： 子树的个数没有限制，但它们一定是互不相交的
不是树：

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

结点的度：结点拥有的子树数称为结点的度 (Degree)

• 度为0的结点称为叶结点(Leaf)或终端结点
• 度不为0的结点称为非终端结点或分支结点
• 除根结点之外分支结点也称为内部结点

树的度：是树内各结点的度的最大值

孩子：结点的子树的根称为该结点的孩子(Child)
双亲：该结点称为孩子的双亲(Parent)
兄弟：同一个双亲的孩子之间互称兄弟 (Sibling)
祖先：结点的祖先是从根到该结点所经分支上的所有结点
子孙：以某结点为根的子树中的任一结点都称为该结点的子孙

结点的层次（Level）：从根开始定义起，根为第一层，根的孩子为第二层，若某结点在第n层，则其子树的根就在第n+1层
堂兄弟： 其双亲在同一层的结点互为堂兄弟
树的深度：树中结点的最大层次称为树的深度（Depth)或高度

有序树：如果将树中结点的各子树看成从左至右是有次序的，不能互换的，则称该树为有序树
无序树：否则称为无序树
森林（Forest）： m(m>=0)棵互不相交的树的集合。对树中每个结点而 ，其子树的集合即为森林

树的存储结构：
（顺序存储结构不能满足树的实现要求）

• 双亲表示法
• 孩子表示法
• 孩子兄弟表示法

二叉树

二叉树(Bina Tree)的定义：n(n>=O)个结点的有限集合，该集合或者为空集(称为空二叉树)，或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成

二叉树特点：

• 每个结点最多有两棵子树（没有子树或者有一棵子树都是可以的），所以二叉树中不存在度大于2的结点
• 左子树和右子树是有顺序的，次序不能任意颠倒
• 即使树中某结点只有 一棵子树，也要区分它是左子树还是右子树

五种基本形态：

• 空二叉树
• 只有一个根结点
• 根结点只有左子树
• 根结点只有右子树
• 根结点既有左子树又有右子树

左斜树：所有的结点都只有左子树的二叉树叫左斜树
右斜树：所有结点都是只有右子树的二叉树叫右斜树
斜树：这两者统称为斜树
满二叉树：在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层，这样的二叉树称为满二叉树
满二叉树的特点：

• 叶子只能出现在最下一层，出现在其他层就不可能达成平衡
• 非叶子结点的度一定是2
• 在同样深度的二叉树中，满二叉树的结点个数最多，叶子数最多

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

• 叶子结点只能出现在最下两层
• 最下层的叶子一定集中在左部连续位置
• 倒数二层，若有叶子结点，一定都在右部连续位置
• 如果结点度为1 ，则该结点只有左孩子，即不存在只有右子树的情况
• 同样结点数的二叉树，完全二叉树的深度最小

非完全二叉树：

二叉树的性质：

• 性质1：在二叉树的第i层上至多有$2^{i-1}$ (i>=1)个结点
• 性质2：深度为k的二叉树至多有$2^k-1$ (k>=1)个结点
• 性质3: 对任何一棵二叉树T，如果其终端结点数为$n_0$，度为2的结点数为$n_2$，则$n_0 = n_2 + 1$
• 性质4: 具有n个结点的完全二叉树的深度为[$\log_{2}n$+1] ([x]表示不大于x的最大整数)
• 性质5: 如果对一棵有n个结点的完全二叉树（其深度为[$\log_{2}n$+1]）的结点按层序编号（从第1层到第[$log_{2}n$]+1层，每层从左到右），对任一结点i（1<=i<=n）有:
  1）如果i=1，则结点i是二叉树的根，无双亲; 如果i>1，则其双亲是结点[i/2]
  2）如果2i>=n，则结点i无左孩子(结点i为叶子结点) ;否则其左孩子是结点2i
  3）如果2i+1>=n，则结点i无右孩子；否则其右孩子是结点2i+1

二叉树的遍历：
(trave ing bina tree)是指从根结点出发，按照某种次序依次访问二叉树中所有结点，使得每个结点被访问一次且仅被访问一次

二叉树的遍历方法：
- 前序遍历：若二叉树为空，则空操作返回，否则先访问根结点，然后前序遍历左子再前序遍历右子树

• 中序遍历：若树为空，则空操作返回，否则从根结点开始(注意并不是先访问根结点) ，中序遍历根结点的左子树，然后是访问根结点，最后中序遍历右子树

• 后序遍历：若树为空，则空操作返回，否则从左到右先叶子后结点的方式遍历访问左右子树，最后是访问根结点

• 层序遍历：若树为空则空操作返回，否则从树的第一层，也就是根结点开始访问，从上而下逐层遍历，在同一层中 按从左到右的顺序对结点逐个访问

线索二叉树：利用空地址存放指向结点在某种遍历次序下的前驱和后继结点的地址，这种指向前驱和后继的指针称为线索，加上线索的二叉链表称为线索链表，相应的二叉树就称为线索二叉树（Threaded Binary Tree)
线索化：对二叉树以某种次序遍历使其变为线索二叉树的过程称做是线索化。线索化的实质就是将二叉链表中的空指针改为指向前驱或后继的线索。由于前驱和后继的信息只有在遍历该叉树时才能得到，所以线索化的过程就是在遍历的过程中修改空指针的过程

如果所用的二叉树需经常遍历或查找结点时需要某种遍历序列中的前驱和后继，那么采用线索二叉链表的存储结构就是非常不错的选择

树的转换

树转换为二叉树的步骤：

1. 加线。在所有兄弟结点之间加一条连线
2. 去钱。对树中每个结点，只保留它与第一个孩子结点的连线，删除色与其他孩
   子结点之间的连线
3. 层次调整。以树的根结点为轴心，将整棵树顺时针旋转一定的角度，使之结构
   层次分明。注意第一个孩子是二叉树结点的左孩子，兄弟转换过来的孩子是结点的右孩子
   

森林转换为二叉树的步骤：

（森林是由若干棵树组成的，所以完全可以理解为，森林中的每一棵树都是兄弟，可以按照兄弟的处理办法来操作）

1. 把每个树转换为二叉树。
2. 棵二叉树不动，从第 棵二叉树开始，依次把后一棵 叉树的根结点作为棵二叉树的根结点的右孩子，用线连接起来。当所有的二叉树连接起来后就得到了由森林转换来的二叉树。

二叉树转换为树的步骤：

（二叉树转换为树是树转换为 叉树的逆过程，也就是反过来做而已）

1. 加线。若某结点的左孩子结点存在，则将这个左孩子的右孩子结点、右孩子的
   右孩子结点、右孩子的右孩的右孩子结点……，反正就是左孩子的n个右孩子结点都作为此结点的孩子。将该结点与这些右孩子结点用线连接起来
2. 去钱。删除原二叉树中所有结点与其右孩子结点的连线
3. 层次调整。使之结构层次分明

二叉树转换为森林的步骤:

（判断一棵二叉树能够转换成一棵树还是森林，只要看这棵二叉树的根结点有没有右孩子，有就是森林，没有就是一棵树）

1. 从根结点开始 若右孩子存在，则把与右孩子结点的连线删除，再查看分离后的二叉树，若右孩子存在，则连线删除……，直到所有右孩子连线都删除为止，得到分离的二叉树
2. 再将每棵分离后的二叉树转换为树即可

树的遍历：分为两种方式：

1. 先根遍历，即先访问树的根结点，然后依次先根遍历根的每棵子树
2. 后根遍历，即先依次后根遍历每棵子树，然后再访问根结点

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

1. 前序遍历: 先访问森林中第一棵树的根结点，然后再依次先根遍历根的每棵子树，再依放用同样方式遍历除去第一棵树的剩余树构成的森林
2. 后序遍历: 是先访问森林中第一棵树，后根遍历的方式遍历每棵子树，然后再
   访问根结点，再依次同样方式遍历除去第一棵树的剩余树构成的森林

赫夫曼树

路径长度：从树中一个结点到另一个结点之间的分支构成两个结点之间的路径，路径上的分支数目称做路径长度，树的路径长度就是从树根到每一结点的路径长度之和
带权路径长度：结点的带权的路径长度为从该结点到树根之间的路径长度与结点上权的乘积；树的带权路径长度为树中所有叶子结点的带权路径长度之和
赫夫曼树：假设有n个权值{w1, w2, ...wn}，构造一棵有n个叶子结点的二叉树，每个叶子结点带权wk，每个叶子的路径长度为lk，则其中带权路径长度WPL最小的二叉树称做赫夫曼树树（最优二叉树）

• 二叉树a：WPL=5X1+15X2+40X3+30X4+10X4=315
• 二叉树b：WPL=5X3+15X3+40X2+30X2+10X2=220

构造赫夫曼树的赫夫曼算法:

1. 根据给定的n个权值{w1, w2, ...wn}构成n棵二叉树的集合F={T1, T2, ...Tn}，其中每棵二叉树Ti中只有一个带权为wi根结点，其左右子树均为空
2. 在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左右子树上根结点的权值之和
3. 在F中删除这两棵树，同时将新得到的二叉树加入F中
4. 重复2和3步骤，直到F只含一棵树为止，这棵树便是赫夫曼树

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