Chapter 6 Trees
第 6 章 树
一对一 👉 一对多
树（Tree）是 n（n>=0）个结点的有限集。n=0时称为空树。在任意一棵非空树中：
有且仅有一个特定的称为根（Root）的结点
当
时，其余结点可分为
个互不相交的有限集
其中每一个集合本身又是一棵树，并且称为根的子树（SubTree）
一个子结点只能被一个父结点相连
结点的分类
结点拥有的子树数称为结点的度（Degree）。度为0的结点称为叶结点（Leaf）或终端结点；度不为
的结点称为非终端结点或分支结点。除根结点之外，分支结点也称为内部结点。树的度是树内各结点的度的最大值。
结点间的关系
结点的子树的根称为该结点的孩子（Child），相应的，该结点称为孩子的双亲。
同一个双亲的孩子之间互称兄弟（Sibling）
结点的祖先是从根到该结点所经分支上的所有结点
以某结点为根的子树中的任意结点都成为该结点的子孙
树的其他概念
结点的层次（Level）从根开始定义起，根称为第一层，根的孩子称为第二层
双亲在同一层的结点互为堂兄弟
树中的结点的最大层次称为树的深度（Depth）或高度
如果将树中结点的各子树看成从左至右是有次序的，不能互换的，则称该树为有序树，否则称为无序树
森林（Forest）是m（m>=0）课不相交的树的集合
线性结构（线性表）
树结构
第一个数据元素：无前驱
最后一个数据元素：无后继
中间元素：一个前驱一个后继
根结点：无双亲，唯一
叶结点：无孩子，可以多个
中间结点：一个双亲一个或多个孩子
树的存储结构
无法使用顺序存储结构和链式存储结构（一对一）
引入三种方法：双亲表示法、孩子表示法、孩子兄弟表示法（一对多）
双亲表示法
在每个结点中，附设一个指示器指示其双亲结点在数组中的位置。
data
parent
数据域，存储结点的数据信息
指针域，存储该结点的双亲在数组中的下标
双亲表示法方便查询到双亲位置，但不好查询孩子
可以增加一个长子域，表示一个结点最左边孩子的域
data
parent
first
数据域，存储结点的数据信息
指针域，存储该结点的双亲在数组中的下标
该结点的最左边孩子的下标，没有标为－1
有时我们希望可以了解各兄弟之间的关系，则增加一个右兄弟域，标明这个结点的右兄弟的下标
data
parent
first
rightsib
数据域，存储结点的数据信息
指针域，存储该结点的双亲在数组中的下标
该结点的最左边孩子的下标，没有标为－1
右兄弟域，该结点右兄弟的下标，没有为－1
存储结构的设计是一个非常灵活的过程，一个存储结构设计的是否合理，取决于基于该存储结构的运算是否适合、方便，时间复杂度好不好等。
孩子表示法
由于树中每个结点可能有多棵子树，可以考虑用多重链表：每个结点有多个指针域，其中每个指针指向一棵子树的根结点，我们把这种方法叫做多重链表表示法。
孩子表示法：把每个结点的孩子结点排列起来，以单链表作存储结构，则n个结点有n个孩子链表，如果是叶子结点，则此单链表为空。然后n个头指针又组成一个线性表，采用顺序存储结构，存放进一个一个维数组中。
这样可以方便地查找某个结点的某个孩子，或者某个结点的某个兄弟（查找孩子链表），或者遍历整棵树也是很方便的（头结点数组循环）
双亲孩子表示法
双亲表示法对孩子和孩子的兄弟表示过于复杂，孩子表示法又查不到双亲（除非遍历整棵树）。
考虑改进孩子表示法，在头结点链表的每个结构加上表示双亲的单位：指向双亲的下标
孩子兄弟表示法
从兄弟的角度出发：任意一棵树，它的结点的第一个孩子如果存在就是唯一的，它的右兄弟若存在也是唯一的。因此，我们设置两个指针，分别只想该结点的第一个孩子和此结点的右兄弟。
data
firstchild
rightsib
数据域
指针域：存储该结点的第一个孩子结点的存储地址
指针域：存储该结点的右兄弟结点的存储地址
通过这种表示法：只需要通过firstchild找到此结点的长子，然后再通过长子结点的rightsib找到它的二弟，接着一直下去，直到找到具体的孩子。
当然也可以通过增加一个双亲指针域，方便地找到某个结点的双亲。
二叉树
二叉树（Binary Tree）是n（n>=0）个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根结点和两棵互不相交的，分别称为根结点的左子树和右子树的二叉树组成。
二叉树的特点
每个结点最多有两颗子树，所以二叉树中不存在度大于2的结点
左紫薯和右子树是有顺序的，次序不能任意颠倒
即使树中某结点只有一颗子树，也要区分它是左子树还是右子树
特殊二叉树
斜树：所有结点都只有左子树的叫左斜树，反之右斜树，两者统称斜树
满二叉树：在一颗二叉树中，所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树
完全二叉树：对一棵具有n个结点的二叉树按层序编号，如果编号为i（1<=i<=n）的结点与同样深度的满二叉树中编号为i的结点在二叉树中位置完全相同，则这棵二叉树称为完全二叉树（按编号排，一定都是连续的，不能有断值）（满二叉树一定是完全二叉树）
二叉树的性质
性质1：
在二叉树的第i层最多有
结点
类比满二叉树
性质2：
深度为k的二叉树最多有
个结点
性质3：
对任何一棵二叉树T，如果其终端结点数为
，度为2的结点树为
则
性质4：
具有n个结点的完全二叉树的深度为
（[x]表示不大于x的最大整数）
性质5：
如果对一棵有n个结点的完全二叉树（深度为）的结点按层序编号，从上到下，从左到右，对任一结点i有：
如果i=1，则为根；如果i>=2，则双亲是结点[i/2]
如果2i>n，则结点i无左孩子（i为叶子）；否则其左孩子为结点2i
如果2i+1>n，则结点i无右孩子；否则其有孩子是结点2i+1
二叉树的存储结构
二叉树的顺序存储结构
二叉树是一种特殊的树，可以实现线性存储结构，按照次序依次存入数组，不存在的结点设置为^（NULL/空）（一般适用完全二叉树，避免浪费空间）
二叉链表
二叉树每个结点最多有两个孩子，所以为它设计一个数据域和两个指针域。
lchild
data
rchild
指针域，左孩子的指针
数据域
指针域，右孩子的指针
可以再增加一个指向其双亲的指针，称为：三叉链表
遍历二叉树
二叉树的遍历（traversing binary tree）是指从根节点出发，按照某种次序依次访问二叉树中的所有结点，使得每个结点被访问依次且仅被访问一次
二叉树的遍历方法
1.前序遍历
规则是若二叉树为空，则空操作返回，否则先访问根节点，然后前序遍历左子树，再前序遍历右子树。
算法实现：递归函数。
2.中序遍历
规则是若树为空，则空操作返回，否则从根节点开始（注意并不是先访问根节点），中序遍历根节点的左子树，然后访问根节点，最后中序遍历右子树。
3.后序遍历
规则是若树为空，则空操作返回，否则从左到右先叶子后结点的方式遍历访问左右子树，最后是访问根节点。
4.层序遍历
规则是若树为空，则空操作返回，否则从树的第一层，也就是根节点开始访问，从上而下逐层遍历，在同一层中，按从左到右的顺序对结点逐个访问。
研究这么多种遍历方法是为了给计算机提供线性序列（计算机只能处理循环、判断问题）。
前三种算法的本质在于递归函数：区别在于什么时候打印当前结点。
考题：根据前序遍历和中序遍历结果还原二叉树，并推导后续遍历的结果。（已知前序和中序可以唯一确定唯一一棵二叉树、已知中序和后序也可以确定唯一一棵二叉树）但前序和后序不行……
线索二叉树
为了充分利用二叉链表的空指针（当没有子树时，大量的空指针浪费了内存空间）
指向前驱和后继的指针称为线索，加上线索的二叉链表称为线索链表，相应的二叉树就称为线索二叉树（Threaded Binary Tree），简而言之就是将遍历次序保存下来，作为前驱后继的指向。
对二叉树以某种次序遍历使其变为线索二叉树的过程称作是线索化
数据结构表示为如下，可以区分指向是孩子还是前驱后继
lchild
ltag
data
rtag
rchild
左孩子（前驱）
左标签（布尔值）
结点数据
右标签（布尔值）
右孩子（后继）
ltag为0时指向该结点的左孩子，为1时指向该结点的前驱
rtag为0时指向该结点的右孩子，为1时指向该结点的后继
线索化的过程就是在遍历的过程中修改空指针的过程，线索化后形成双向链表，此时可以从任意结点开始遍历（访问）结点
如果所用的二叉树需经常遍历或查找结点时需要某种遍历序列中的前驱和后继，那么采用线索二叉链表的存储结构就是非常不错的选择
树、森林与二叉树交换
树转化为二叉树
步骤：
在所有兄弟结点之间加一条连线
对树的每一个结点，只保留它与第一个孩子结点的连线，删除它与其它孩子结点之间的连线
层次调整，把线拉直
但双亲与孩子、兄弟关系会改变……
森林转换为二叉树
步骤：
把每棵树都转换为二叉树
第一棵二叉树不动，从第二棵开始，依次把后一棵的根结点作为前一棵的根结点的右孩子，用线连起来。
二叉树转化为树
步骤是“树转化为二叉树”的逆步骤
二叉树转化为森林
判断：一棵二叉树的根结点有没有右孩子，有就是森林，没有就是一棵树
步骤：
从根结点点开始，若右孩子存在，把与右孩子的连线删除
删除后的二叉树继续删除右孩子
再将每课分离后的二叉树转换为树即可
树与森林的遍历
树的遍历：先根遍历树、后根遍历
森林的遍历：前序遍历、后序遍历
可以将树和森林的遍历转化为对二叉树的遍历。
哈夫曼树及其应用
哈夫曼树是特殊的二叉树（利用哈夫曼编码）
定义与原理
带权路径长度（WPL）最小的二叉树称作哈夫曼树（也叫最优二叉树）
树结点间的边相关的树叫做权（Weight）
从树中一个结点到另一个结点之间的分支构成两个结点之间的路径，路径上的分支数目称作路径长度
树的路径长度就是从树根到每一结点的路径长度之和
总的来说：就是构造二叉树时，将权重大的结点放在深度小的地方。
哈夫曼编码
若要设计长短不等的编码，则必须是任意字符的编码都不是另一个字符的编码的前缀，这样的编码称作前缀编码。
根据已知字符集中字符出现的频率计算权，得到WPL最小的二叉树（0表示左子树，1表示右子树）（数据都存储在二叉树叶子上），这样的编码方式就是哈夫曼编码。
Last updated