第六章 树
最后更新于：2022-04-01 23:02:10
### 一、树的定义
定义：树是n个结点的有限集。n=0时称为空树。在任意一棵非空树中：（1）有且仅有一个特定的称为根的结点；（2）当n>1时，其余结点可以分为m个互不相交的有限集T1、T2、...Tm，其中每一个集合本身又是一棵树，并且称为根的子树。
对于树的定义还需要强调两点：
1.n>0时根节点是唯一的；
2.m>0时，子树的个数没有限制，但他们一定是互不相交的。
结点的分类
结点拥有的子树数称为结点的度（Degree）。度为0的结点称为叶子结点（leaf），度不为0的结点称为分支结点。树的度是树内各结点的度的最大值，如图所示树的度为3。
结点的子树的根称为该结点的孩子，相应的该结点称为孩子的双亲（Parent）。同一个双亲的孩子之间互称为兄弟。结点的祖先是从根到该节点所经分支上的所有结点。以某结点为根的子树中任一结点都称为该结点的子孙。
树的层次（Level）的概念：
树中结点的最大层次称为树的深度（Depth）。
最后，对比线性表与树的结构：
### 二、树的抽象数据类型
下面给出树的一些基本和常用操作：
### 三、二叉树的定义
二叉树（Binary Tree）是n（n>=0）个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根节点和两颗互不交互的、分别称为根节点的左子树和右子树的二叉树组成。
特殊二叉树：
1.满二叉树：在一棵二叉树中，如果所有的分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树就称为满二叉树。
2.完全二叉树：对一棵具有n个结点的二叉树按层序编号，如果编号为i（1=1）;
性质2：深度为K的二叉树至多有2^k-1个结点（k>=1）；
性质3：对于任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。
性质4：具有n个结点的完全二叉树的深度为【log2n】+1（【x】表示不大于x的最大整数）
### 四、二叉树的存储结构
1.二叉树的顺序存储结构：
顺序存储一般适用于完全二叉树
2.二叉链表
二叉树每个结点最多有两个孩子，所以为它涉及一个数据域和两个指针域是比较自然的想法，我们称这样的链表叫做二叉链表。如图所示：
二叉链表的结点结构定义代码如下：
结构示意图如下：
### 五、遍历二叉树
二叉树的遍历是指从根节点出发，按照某种次序依次访问二叉树中的所有结点，使得每个结点被访问一次，且仅被访问一次。
二叉树的遍历方法
1.前序遍历：规则是若二叉树为空，则空操作返回，否则先访问根节点，然后前序遍历左子树，再前序遍历右子树。如图所示：（根左右）
2.中序遍历：（左根右）
3.后序遍历（左右根）
4.层序遍历：
下面来看一下前序遍历算法
二叉树的定义是用递归的方式，所以，实现遍历算法也可以采用递归，而且极其简洁明了：
中序遍历算法：
后序遍历算法：
### 六、二叉树的建立
为了能让每个结点确认是否有左右孩子，我们对它进行了扩展，如图：
扩展二叉树就可以做到一个遍历序列确定一个二叉树了，上图的前序遍历序列就是AB#D##C##。有了这样的准备，我们就可以来看看如何生成一棵二叉树了。实现算法如下：
### 七、霍夫曼树及其应用
最基本的压缩编码方法-霍夫曼编码，在介绍霍夫曼编码前，我们必须得介绍霍夫曼树，而介绍霍夫曼树。带权路径长度WPL最小的二叉树称作霍夫曼树。也有不少树中称为最优二叉树。
二叉树a的WPL=315，二叉树b的WPL=220。
下面介绍一下霍夫曼树的构造：
一、对给定的n个权值{W1,W2,W3,...,Wi,...,Wn}构成n棵二叉树的初始集合F= {T1,T2,T3,...,Ti,...,Tn}，其中每棵二叉树Ti中只有一个权值为Wi的根结点，它的左右子树均为空。（为方便在计算机上实现算 法，一般还要求以Ti的权值Wi的升序排列。）
二、在F中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树，新二叉树的根结点的权值为其左右子树的根结点的权值之和。
三、从F中删除这两棵树，并把这棵新的二叉树同样以升序排列加入到集合F中。
四、重复二和三两步，直到集合F中只有一棵二叉树为止。
简易的理解就是，假如我有A,B,C,D,E五个字符，出现的频率（即权值）分别为5,4,3,2,1,那么我们第一步先取两个最小权值作为左右子树构造一个新树，即取1，2构成新树，其结点为1+2=3，如图：
[](http://images.cnblogs.com/cnblogs_com/Jezze/201112/201112231832079219.png)
虚线为新生成的结点，第二步再把新生成的权值为3的结点放到剩下的集合中，所以集合变成{5,4,3,3}，再根据第二步，取最小的两个权值构成新树，如图：
[](http://images.cnblogs.com/cnblogs_com/Jezze/201112/20111223183207124.png)
再依次建立哈夫曼树，如下图：
[](http://images.cnblogs.com/cnblogs_com/Jezze/201112/201112231832082109.jpg)
其中各个权值替换对应的字符即为下图：
[](http://images.cnblogs.com/cnblogs_com/Jezze/201112/201112231832085730.jpg)
所以各字符对应的编码为：A->11,B->10,C->00,D->011,E->010
下面研究一下霍夫曼编码：
一般地，设需要编码的字符集为{d1,d2,......dn},各字符在电文中出现的次数或频率的集合为{w1,w2,......wn}，以d1,d2,......dn作为叶子结点，以w1,w2,......wn作为相应叶子结点的权值来构造一棵霍夫曼树。规定霍夫曼树的左分支代表0，右分支代表1，则从根节点到叶子结点所经过的路径分支组成的0和1的序列便为该结点对应字符编码，这就是霍夫曼编码。
例子：我们在发送电报的时候用到了六个字母，其出现的概率分别为：A 27，B 8，C 15， D 15，E 30，F 5,合起来正好是百分之百。
怎么获得霍夫曼编码呢？
首先按照比率作为权值画霍夫曼树，然后将左分支代表0，右分支代表1，如图：
从根节点到叶子结点所经过的路径分支组成的0和1的序列便为该结点对应字符编码，即：
这样就获得了霍夫曼编码。
';