数据结构第六章树和二叉树ppt课件.ppt
数据结构第六章树和二叉树,本章内容6.1 树的概念与基本术语6.2 二叉树6.3 遍历二叉树6.4 线索二叉树6.5 树与森林6.6 赫夫曼树及其应用,6-3,6.1 树的概念与基本术语,树的定义(Tree)树是有n(n0)个结点的有限集合。如果 n=0，称为空树；如果 n0,称为非空树,对于非空树,有且仅有一个特定的称为根(Root)的节点(无直接前驱)如果 n1，则除根以外的其它结点划分为 m(m0)个互不相交的有限集 T1,T2,Tm，其中每个集合本身又是一棵树，并且称为根的子树(SubTree)。每个结点都有唯一的直接前驱，但可能有多个后继树的举例其中：A是根；其余结点分成三个互不相交的子集，T1=B,E,F,K,L；T2=C,G；T3=D,H,I,J,M,T1,T2,T3都是根A的子树，且本身也是一棵树,6-4,6.1 树的概念与基本术语,树的基本术语结点：包含一个数据元素及若干指向其子树的分支结点的度：结点拥有的子树数,或者说后继结点数叶结点：度为0的结点没有子树的结点分支结点：度不为0的结点包括根结点，也称为非终端结点。内部结点:除根外的结点孩子：结点的子树的根双亲：孩子的直接前驱,6-5,6.1 树的概念与基本术语,兄弟：同一双亲的孩子子孙：以某结点为根的树中的所有结点祖先：从根到该结点所经分支上的所有结点层次：根结点为第一层，其孩子为第二层，依此类推深度：树中结点的最大层次森林：互不相交的树的集合。对树中每个结点而言，其子树的集合即为森林,6-6,6.2 二叉树,二叉树(Binary Tree)每个结点最多有棵子树二叉树的子树有左右之分,6-7,6.2 二叉树,二叉树性质：在二叉树的第i层上至多有2i-1个结点证明：i=1,只有一个根节点，因此2i-1=20=1设第i-1层上，以上性质成立，即第i-1层至多有2(i-1)-1结点。由二叉树的定义可知，任何结点的度小于2，因此，第i层上的结点数最多为第i-1层上的两倍，即2*2i-2=2i-1证毕,6-8,6.2 二叉树,二叉树性质：深度为k的二叉树至多有2k-1个结点证明：由性质，已知第i层上结点数最多为2i-1 k 2i-1=2k-1 i=1证毕,6-9,6.2 二叉树,二叉树性质：如果二叉树终端结点数为n0，度为2的结点数为n2，则n0=n2+1证明：设n1是度为1的结点，则总结点数n=n0+n1+n2设B为二叉树的分支数，除根结点外，每个结点有且只有一个分支，因此n=B+1每个分支皆由度为1或2的结点发出，B=n1+2n2n=B+1=(n1+2n2)+1=n0+n1+n2，因此 n0=n2+1证毕,6-10,6.2 二叉树,满二叉树：一个深度为k且有2k-1个结点的二叉树每层上的结点数都是最大数可以自上而下、自左至右连续编号,6-11,6.2 二叉树,完全二叉树：当且仅当每一个结点都与深度相同的满二叉树中编号从1到n的结点一一对应的二叉树叶子结点只在最大两层上出现左子树深度与右子树深度相等或大,6-12,6.2 二叉树,完全二叉树(性质)：具有n个结点的完全二叉树,其深度为 log2n+1证明：设k为深度，由二叉树性质，已知 2k-1-1 n 2k-1即 2k-1 n 2k即 k=log2n+1,6-13,完全二叉树(性质)：在完全二叉树中，结点i的双亲为 i/2结点i的左孩子LCHILD(i)=2i结点i的右孩子RCHILD(i)=2i+1,6.2 二叉树,6-14,6.2 二叉树,二叉树的存储结构1.顺序存储结构2.链式存储结构顺序存储结构：用一个一维数组来存储二叉树的各个结点C语言表示#define MAX_TREE_SIZE 100/二叉树的最大结点数typedef TElemType SqBiTreeMAX_TREE_SIZE;/0号单元存储根结点SqBiTree bt;显然，二叉树的结点必须按某种次序分别存入数组的各个单元，这种次序应能反映结点间的逻辑关系，否则二叉树上的各种基本运算在顺序存储结构上很难实现。对于完全二叉树来说，可以采用“以编号为地址”的方法，将编号为i的结点存入一维数组的第i个单元(下标为i-1)。,6-15,6.2 二叉树,完全二叉树的顺序表示例:对应的顺序存储结构:将编号为i的结点存入一维数组的第i个单元(下标为i-1),6-16,非完全二叉树的顺序表示例:对应的顺序存储结构:一维数组的21单元中只用上了7个.最坏情况下,一个深度为k且只有k个结点的单支树,却需要长度为2k-1的一维数组总结顺序存储结构适合存储完全二叉树对于非完全二叉树，采用链式存储结构更合适,6.2 二叉树,6-17,6.2 二叉树,二叉链表结点结构:通常每个结点中设置三个域,即值域、左指针域和右指针域，其结点结构如下：其中data表示值域，lchild和rchild分别表示左指针域和右指针域，用以分别存储指向左儿子结点和右儿子结点的指针。TElemType可以是任何相应的数据类型如int、float或char等。,typedef struct BiTNode TElemType data;struct BiTNode*lchild,*rchild;BiTNode,*BITree;,6-18,6.2 二叉树,6-19,6.2 二叉树,三叉链表通常每个结点中设置四个域,即值域、左指针域、右指针域和双亲指针域，其结点结构如下：其中data表示值域，用于存储放入结点的数据，lchild和rchild分别表示左指针域和右指针域，用以分别存储指向左儿子结点和右儿子结点的指针,parent指向双亲结点。,6-20,6.3 遍历二叉树,遍历二叉树定义：二叉树的遍历(Traverse)是指按一定的规律访问二叉树的每个结点，且每个结点只被访问一次的过程。对二叉树的遍历过程实际上是将非线性结构的二叉树中的结点排列成一个线性序列的过程。本节仅讨论二叉链表的遍历过程。设访问根结点用D表示，遍历左、右子树用L、R表示遍历分类：在任一结点上，有三种执行操作：访问结点本身，遍历该结点左子树，遍历该结点右子树。操作次序主要分为三种：左、根、右；也称为中序遍历、LDR；根、左、右；也称为先序遍历、DLR；左、右、根；也称为后序遍历、LRD。,6-21,6.3 遍历二叉树,三种遍历次序以递归的形式定义中序(InOrder)遍历：若树为空，执行空操作；否则依次执行：中序遍历左子树L；访问根结点D；中序遍历右子树R。先序(PreOrder)遍历：若树为空，执行空操作；否则依次执行：访问根结点D；先序遍历左子树L；先序遍历右子树R。后序(PostOrder)遍历：若树为空，执行空操作；否则依次执行：后序遍历左子树L；后序遍历右子树R；访问根结点D。,6-22,6.3 遍历二叉树,二叉树遍历的实现template void PreOrder(BiTreeNode*t,void Visit(T item)/使用Visit(item)函数前序遍历二叉树t if(t!=NULL)Visit(t-data);PreOrder(t-Left(),Visit);PreOrder(t-Right(),Visit);为了通用性，把访问操作设计成前序遍历二叉树函数的一个函数虚参 Visit()。,输出结果：ABDEGCF(第一个输出节点必为根节点),6-23,6.3 遍历二叉树,template void InOrder(BiTreeNode*t,void Visit(T item)/使用Visit(item)函数中序遍历二叉树tif(t!=NULL)InOrder(t-Left(),Visit);Visit(t-data);InOrder(t-Right(),Visit);,输出结果：DBGEAFC（先于根节点A输出的节点为左子树的节点后于根节点A输出的节点为右子树的节点）,6-24,6.3 遍历二叉树,template void PostOrder(BiTreeNode*t,void Visit(T item)/使用Visit(item)函数后序遍历二叉树tif(t!=NULL)PostOrder(t-Left(),Visit);PostOrder(t-Right(),Visit);Visit(t-data);,输出结果：DGEBFCA(最后一个输出节点必为根节点),6-25,6.3 遍历二叉树,遍历二叉树应用利用后序求结点个数或树的高度利用前序实现二叉树复制判断两棵树是否相等Return 1+Size(t-lchild)+Size(t-rchild);temp-data=progmpde-data;temp-lchile=copy(orignode-lchild);temp-rchile=copy(orignode-rchild);If(a!=NULL&b!=NULL&a-data=b-data&equal(a-lchild=b-lchild)&equal(a-rchild=b-rchild),6-26,6.3 遍历二叉树,根据先、中序遍历求序列二叉树：如果已知一棵二叉树的先序遍历和中序遍历序列，则可以惟一确定这棵二叉树算法：1.在先序遍历序列中，第一个节点为根节点D2.在中序遍历序列中，根节点D左边的节点归为左子树，根节点D右边的节点归为右子树3.对每个子树反复使用1,2两步，直到确定二叉树,6-27,6.3 遍历二叉树,示例：已知一棵二叉树的先序遍历序列为：ABDEGCF，中序遍历序列为：DBGEAFC，请画出这棵二叉树解：根据先序遍历序列，可知根节点为A；再根据中序遍历序列可知，左子树由DBGE组成，右子树由FC组成。重复上述步骤，分别求出左子树和右子树的细节。,6-28,6.3 遍历二叉树,根据后、中序遍历求序列二叉树：如果已知一棵二叉树的后序遍历和中序遍历序列，则可以惟一确定这棵二叉树算法：1.在后序遍历序列中，最后一个节点为根节点D2.在中序遍历序列中，根节点D左边的节点归为左子树，根节点D右边的节点归为右子树3.对每个子树反复使用1,2两步，直到确定二叉树,6-29,6.3 遍历二叉树,示例：已知一棵二叉树的后序遍历序列为：DGEBFCA，中序遍历序列为：DBGEAFC，请画出这棵二叉树解：根据后序遍历序列，可知根节点为A；再根据中序遍历序列可知，左子树由DBGE组成，右子树由FC组成。重复上述步骤，分别求出左子树和右子树的细节。,6-30,6.4 线索二叉树,二叉树以二叉链表存储结构不足所有叶子结点与无子结点的结点指针位置，存储结构都是空的；同时只能找到结点的左右孩子的信息,而不能在结点的任一序列的前驱与后继信息,这种信息只有在遍历的动态过程中才能得到。解决办法利用二叉树中得空位置，建立遍历指针，达到在遍历中不再使用堆栈的目的。遍历指针被称为：线索。带有线索的二叉树被称为：线索二叉树,6-31,6.4 线索二叉树,在中序遍历过程中，遇到空指针时，需要决定遍历的后续结点的位置，所以：空的右指针指向遍历后继空的左指针指向遍历前趋,6-32,6.4 线索二叉树,线索二叉树中，只有两个空的指针分析中序的遍历过程从左指针为空的结点开始遍历到右指针为空的结点结束遍历建立二叉树的线索：在遍历过程中建立。遍历时，记录当前结点的前趋和后继，在遇到空指针时，建立相应的连接。,6-33,6.5 树与森林,树的存储结构1.双亲表示法采用一组连续的存储空间由于每个结点只有一个双亲，只需要一个指针,6-34,6.5 树与森林,2.孩子表示法多重链表可以采用多重链表，即每个结点有多个指针最大缺点是空链域太多(d-1)n+1个,6-35,6.5 树与森林,3.孩子表示法单链表将每个结点的孩子排列起来，用单链表表示将每个结点排列成一个线性表,6-36,6.5 树与森林,4.孩子兄弟表示法采用二叉链表左边指针指向第一个孩子，右边指针指向兄弟,6-37,6.5 树与森林,树与二叉树的对应关系树与二叉树都可以采用二叉链表作存储结构任意给定一棵树，可以找到一个唯一的二叉树(没有右子树)树转换为二叉树的方法树中所有相邻兄弟之间加一条连线。对树中的每个结点，只保留它与第一个孩子结点之间的连线，删去它与其它孩子结点之间的连线。以树的根结点为轴心，将整棵树顺时针转动450，使之结构层次分明。,6-38,树转换成二叉树的过程举例,6.5 树与森林,6-39,6.5 树与森林,森林与二叉树的对应关系如果把森林中的第二棵树的根结点看作是第一棵树的根结点的兄弟，则可找到一个唯一的二叉树与之对应。森林转换成二叉树如果F=T1,T2,Tm是森林，按如下规则可转换成一棵二叉树B=(root,LB,RB)。（1）若F为空，则B为空；（2）若F非空，则森林中第一棵树T1的根结点为二叉树B的根结点，B的左子树LB由树T1根结点下的子树森林转换而成。右子树RB是由森林F中除树T1外余下部分转换而成。,6-40,6.5 树与森林,树的遍历对树的遍历主要有两种：先根（次序）遍历、后根（次序）遍历先根（次序）遍历：当树非空时访问根结点依次先根遍历根的各棵子树输出结果：ABEFCDG后根（次序）遍历：当树非空时依次后根遍历根的各棵子树访问根结点输出结果：EFBCGDA,6-41,6.5 树与森林,与二叉树遍历的关系当采用孩子兄弟表示法表示树时：树的先根遍历，与树对应的二叉树的先根遍历完全相同树的后根遍历，与树对应的二叉树的中根遍历完全相同,6-42,6.6 赫夫曼树及其应用,赫夫曼树赫夫曼树（Huffman）树也称最优二叉树，是一类带权路径长度最短的树，在判定、查找及数据压缩技术中有着广泛的应用。基本术语路径：从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径路径长度：路径上的分支数目树的路径长度：从树根到每个结点的路径长度之和带权路径长度：从结点到树根之间的路径长度与结点权的乘积树的带权路径长度(WPL)：树中所有叶结点的带权路径长度之和最优二叉树：假设二叉树有n个叶子，其每个叶子结点权为wi，则带权路径长度WPL最小的二叉树称为最优二叉树。赫夫曼(Huffman)树就是一棵最优二叉树,6-43,6.6 赫夫曼树及其应用,例：下图所示的树路径长度为：2*1+3*2+1*3=11下图所示的树的带权路径长度 WPL=2*5+3*3+2*4=27,6-44,6.6 赫夫曼树及其应用,构造Huffman树在Huffman树中，权值最大的结点离根最近权值最小的结点离根最远Huffman树算法根据给定的n个权值(w1,w2,wn)构成n棵二叉树的集合F=T1,T2,Tn，其中每棵二叉树Ti中只有一个带树为Ti的根结点在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置其根结点的权值为其左右子树权值之和在F中删除这两棵树，同时将新得到的二叉树加入F中重复2,3，直到F只含一棵树为止,6-45,6.6 赫夫曼树及其应用,构造Huffman树示例,6-46,6.6 赫夫曼树及其应用,Huffman编码设给出一段报文：GOOD_GOOD_GOOD_GOOOOOOOO_OFF，字符集合是O,G,_,D,F，各个字符出现的频度(次数)是W=15,4,4,3,2。等长编码：若采用等长办法给每个字符编码：O:000 G:001 _:010 D:011 F:100则总编码长度为(15+4+4+3+2)*3=84.我们考虑按各个字符出现的概率不同而给予不等长编码，可望减少总编码长度。各字符出现概率为 15/28,4/28,4/28,3/28,2/28,取整数为15,4,4,3,2如果规定，Huffman树的左子树小于右子树，则可构成右图所示Huffman树。,6-47,6.6 赫夫曼树及其应用,令左孩子分支为编码0，右孩子分支为编码1将根结点到叶子结点路径上的分支编码，组合起来，作为该字符的Huffman码，则可得到：字母O:1 _:011 G:010 D:001 F:000则总编码长度为 15*1+(2+3+4+4)*3=54 84Huffman是一种前缀编码，解码时不会混淆如GOOD编码为：01011001,6-48,习题,本章习题参见教师网页：http:/,
