### 一、树的定义 定义:树是n个结点的有限集。n=0时称为空树。在任意一棵非空树中:(1)有且仅有一个特定的称为根的结点;(2)当n>1时,其余结点可以分为m个互不相交的有限集T1、T2、...Tm,其中每一个集合本身又是一棵树,并且称为根的子树。 对于树的定义还需要强调两点: 1.n>0时根节点是唯一的; 2.m>0时,子树的个数没有限制,但他们一定是互不相交的。 结点的分类 结点拥有的子树数称为结点的度(Degree)。度为0的结点称为叶子结点(leaf),度不为0的结点称为分支结点。树的度是树内各结点的度的最大值,如图所示树的度为3。 ![](https://box.kancloud.cn/2016-02-15_56c1369130ac2.jpg) 结点的子树的根称为该结点的孩子,相应的该结点称为孩子的双亲(Parent)。同一个双亲的孩子之间互称为兄弟。结点的祖先是从根到该节点所经分支上的所有结点。以某结点为根的子树中任一结点都称为该结点的子孙。 ![](https://box.kancloud.cn/2016-02-15_56c1369147546.jpg) 树的层次(Level)的概念: ![](https://box.kancloud.cn/2016-02-15_56c136915fb3e.jpg) 树中结点的最大层次称为树的深度(Depth)。 最后,对比线性表与树的结构: ![](https://box.kancloud.cn/2016-02-15_56c13691776ea.jpg) ### 二、树的抽象数据类型 下面给出树的一些基本和常用操作: ![](https://box.kancloud.cn/2016-02-15_56c13691927e8.jpg) ### 三、二叉树的定义 二叉树(Binary Tree)是n(n>=0)个结点的有限集合,该集合或者为空集(称为空二叉树),或者由一个根节点和两颗互不交互的、分别称为根节点的左子树和右子树的二叉树组成。 特殊二叉树: 1.满二叉树:在一棵二叉树中,如果所有的分支结点都存在左子树和右子树,并且所有叶子都在同一层上,这样的二叉树就称为满二叉树。 ![](https://box.kancloud.cn/2016-02-15_56c13691c056c.jpg) 2.完全二叉树:对一棵具有n个结点的二叉树按层序编号,如果编号为i(1<i<n)的结点与同样深度的满二叉树中编号为i的结点在二叉树中位置完全相同,则这棵二叉树称为完全二叉树,如图:(除最后一层外,每一层上的结点数均达到最大值;在最后一层上只缺少右边的若干结点) ![](https://box.kancloud.cn/2016-02-15_56c13691da338.jpg) 所以满二叉树是完全二叉树,完全二叉树不一定是满二叉树。 四、二叉树的性质 性质1:在二叉树的第i层上之多有2^i-1个结点(i>=1); 性质2:深度为K的二叉树至多有2^k-1个结点(k>=1); 性质3:对于任何一棵二叉树T,如果其终端结点数为n0,度为2的结点数为n2,则n0=n2+1。 性质4:具有n个结点的完全二叉树的深度为【log2n】+1(【x】表示不大于x的最大整数) ### 四、二叉树的存储结构 1.二叉树的顺序存储结构: ![](https://box.kancloud.cn/2016-02-15_56c13691eb349.jpg) ![](https://box.kancloud.cn/2016-02-15_56c1369205c72.jpg) 顺序存储一般适用于完全二叉树 2.二叉链表 二叉树每个结点最多有两个孩子,所以为它涉及一个数据域和两个指针域是比较自然的想法,我们称这样的链表叫做二叉链表。如图所示: ![](https://box.kancloud.cn/2016-02-15_56c1369219d30.jpg) 二叉链表的结点结构定义代码如下: ![](https://box.kancloud.cn/2016-02-15_56c136922a784.jpg) 结构示意图如下: ![](https://box.kancloud.cn/2016-02-15_56c136923ef70.jpg) ### 五、遍历二叉树 二叉树的遍历是指从根节点出发,按照某种次序依次访问二叉树中的所有结点,使得每个结点被访问一次,且仅被访问一次。 二叉树的遍历方法 1.前序遍历:规则是若二叉树为空,则空操作返回,否则先访问根节点,然后前序遍历左子树,再前序遍历右子树。如图所示:(根左右) ![](https://box.kancloud.cn/2016-02-15_56c1369255242.jpg) 2.中序遍历:(左根右) ![](https://box.kancloud.cn/2016-02-15_56c136926bbad.jpg) 3.后序遍历(左右根) ![](https://box.kancloud.cn/2016-02-15_56c1369287ec4.jpg) 4.层序遍历: ![](https://box.kancloud.cn/2016-02-15_56c136929baae.jpg) 下面来看一下前序遍历算法 二叉树的定义是用递归的方式,所以,实现遍历算法也可以采用递归,而且极其简洁明了: ![](https://box.kancloud.cn/2016-02-15_56c13692b47f4.jpg) 中序遍历算法: ![](https://box.kancloud.cn/2016-02-15_56c13692d3ab7.jpg) 后序遍历算法: ![](https://box.kancloud.cn/2016-02-15_56c13692f2320.jpg) ### 六、二叉树的建立 为了能让每个结点确认是否有左右孩子,我们对它进行了扩展,如图: ![](https://box.kancloud.cn/2016-02-15_56c136931fa08.jpg) 扩展二叉树就可以做到一个遍历序列确定一个二叉树了,上图的前序遍历序列就是AB#D##C##。有了这样的准备,我们就可以来看看如何生成一棵二叉树了。实现算法如下: ![](https://box.kancloud.cn/2016-02-15_56c136933354e.jpg) ![](https://box.kancloud.cn/2016-02-15_56c136935edc0.jpg) ### 七、霍夫曼树及其应用 最基本的压缩编码方法-霍夫曼编码,在介绍霍夫曼编码前,我们必须得介绍霍夫曼树,而介绍霍夫曼树。带权路径长度WPL最小的二叉树称作霍夫曼树。也有不少树中称为最优二叉树。 ![](https://box.kancloud.cn/2016-02-15_56c13693762d7.jpg) 二叉树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,如图: [![12](https://box.kancloud.cn/2016-02-15_56c136938fdb1.png "12")](http://images.cnblogs.com/cnblogs_com/Jezze/201112/201112231832079219.png) 虚线为新生成的结点,第二步再把新生成的权值为3的结点放到剩下的集合中,所以集合变成{5,4,3,3},再根据第二步,取最小的两个权值构成新树,如图: [![13](https://box.kancloud.cn/2016-02-15_56c13693a0d9a.png "13")](http://images.cnblogs.com/cnblogs_com/Jezze/201112/20111223183207124.png) 再依次建立哈夫曼树,如下图: [![14](https://box.kancloud.cn/2016-02-15_56c13693afe5f.jpg "14")](http://images.cnblogs.com/cnblogs_com/Jezze/201112/201112231832082109.jpg) 其中各个权值替换对应的字符即为下图: [![15](https://box.kancloud.cn/2016-02-15_56c13693bf596.jpg "15")](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,如图: ![](https://box.kancloud.cn/2016-02-15_56c13693d0e37.jpg) 从根节点到叶子结点所经过的路径分支组成的0和1的序列便为该结点对应字符编码,即: ![](https://box.kancloud.cn/2016-02-15_56c13693e7b13.jpg) 这样就获得了霍夫曼编码。