《数据结构教学课件》第08章.ppt

《《数据结构教学课件》第08章.ppt》由会员分享，可在线阅读，更多相关《《数据结构教学课件》第08章.ppt（118页珍藏版）》请在三一办公上搜索。

1、第8章 树和二叉树,树二叉树二叉树设计二叉树遍历线索二叉树哈夫曼树等价问题树与二叉树的转换树的遍历,主要知识点,8.1 树,1.树的定义,直观上：树是由n(n0)个数据组成的有限集合，其中仅有一个没有直接前驱的数据，称之为根结点,若干没有后继的数据，称之为 叶结点，其他的数据只有一个前驱数据，且至少有一个后继数据。,8.1 树,1.树的定义（严谨）,树是由n(n0)个结点组成的有限集合T。n=0的树称为空树；对n0的树，有:(1)仅有一个特殊的结点称为根结点，根结点没有前驱 结点；(2)当n1时，除根结点外其余的结点分为m(m0)个互 不相交的有限集合T1,T2，Tm，其中每个集合Ti 本身又

2、是一棵结构和树类似的子树。,注：树的定义具有递归性，即“树中还有树”。,若干术语,结点：由数据元素和构造数据元素之 间关系的指针组成,结点的度：结点所拥有的子树的个数,叶结点：度为0的结点，也称作 终端结点,分支结点：度不为0的结点,孩子结点：树中一个结点的子树的根结点,双亲结点：若树中某结点有孩子结点，则这个结点就 称作它的孩子结点的双亲结点,兄弟结点：具有相同的双亲结点的结点,树的度：树中所有结点的度的最大值,结点的层次：从根结点到树中某结点所经路径上的分支数,树的深度：树中所有结点的层次的最大值,0,1,2,3,无序树：树中任意一个结点的各孩子结点之间的次序 构成无关紧要的树,有序树：树

3、中任意一个结点的各孩子结点有严格排列 次序的树,森林：m（m0）棵树的集合,2.树的表示方法,(1)直观表示法,(2)形式化表示法,(3)凹入表示法,(描述树的逻辑结构),T=（D，R）DF=D1D2Dm（1i,jm,DiDj=）R=,i=1,2,n-1,A,B,C,D,E,F,G,H,I,J,K,L,形式化表示,凹进表示,(树的理论讨论),(树的屏幕显示和打印机输出),3.树的抽象数据类型,数据集合:树的结点集合，每个结点由数据元素和构造数 据元素之间关系的指针组成。操作集合:（1）初始化Initiate(T)（2）撤消DestroyTree(T)（3）双亲结点Parent(T,curr)（

4、4）左孩子结点LeftChild(T,curr)（5）右兄弟结点RightSibling(T,curr)（6）遍历树Traverse(T,Visit(),4.树的存储结构,树的结点之间的逻辑关系主要有双亲-孩子关系，兄弟关系。因此，从结点之间的逻辑关系分，树的存储结构主要有：双亲表示法、孩子表示法、双亲孩子表示法和孩子兄弟表示法四种组合。指针有常规指针和仿真指针,指向内存单元地址的指针；,静态链表形式的指针；,结点的数据元素信息,结点之间逻辑关系,(1)双亲表示法,(a)一棵树,（b)仿真指针的双亲表示法存储结构,树及其使用仿真指针的双亲表示法,(2)孩子表示法,A,C,G,B,D,E,F,I

5、,H,root,常规指针的孩子表示法,双亲孩子表示法存储结构,(3)双亲孩子表示法,(4)孩子兄弟表示法,常规指针的孩子兄弟表示法,8.2 二叉树,二叉树：是n(n0)个结点的有限集合。n=0的树称为空二叉树；n0的二叉树由一个根结点以及两棵互不相交的、分别称为左子树和右子树的二叉树组成。逻辑结构：一对二（1:2）基本特征:每个结点最多只有两棵子树（不存在度大于2的结点）；左子树和右子树次序不能颠倒。所以下面是两棵不同的树,1.二叉树的定义,满二叉树：在一棵二叉树中，如果所有分支结点都存在左 子树和右子树，并且所有叶子结点都在同一层上，这样的 二叉树称为满二叉树。完全二叉树：如果一棵深度为k，

6、有n个结点的二叉树结构与深度为k的满二叉树的前n个结点的结构相同，那么该二叉树称为完全二叉树。如下图所示,左子树,右子树,(a)满二叉树,(b)完全二叉树,问题:一个深度为h的完全二叉树最多有多少个结点?最少有多少个结点?,J,(C)不是完全二叉树,数据集合：二叉树的结点集合，每个结点由数据元素和构造数据元素之间关系的指针组成。操作集合：（1）初始化Initiate(T)（2）撤消DestroyTree(T)（3）左插入结点InsertLeftNode(curr,x)（4）右插入结点InsertRightNode(curr,x)（5）左删除子树DeleteLeftTree(curr)（6）右删

7、除子树DeleteRightTree(curr)（7）遍历二叉树Traverse(T,Visit(),2.二叉树抽象数据类型,3.二叉树的性质,性质1 在一棵非空二叉树的第i层上至多有2i个结点（i0）。,性质2 深度为k的二叉树至多有2k+1-1个结点。说明：深度k=-1，表示没有一个结点；深度k=0，表示只有一个根结点。,首项为a0公比为q的等比数列的前n项和为：,性质3 对于一棵非空的二叉树，如果叶结点个数为n0，度为1的结点数为n1，度为2的结点数为n2，结点总数为n,分支总数为M，则有下列结论成立，(1)n=n0+n1+n2;(2)M=n-1;(3)M=n1+2n2;(4)n0=n2

8、+1。,（除根结点外都有惟一的进入分支）,性质4 具有n个结点的完全二叉树的深度k为大于或等于lb(n+1)-1的最小整数。证明：由性质2和完全二叉树的定义可知，对于有n个结点的深度为k的完全二叉树有：2k-1 n 2k+1-1移项有：2k n+1 2k+1对不等式求对数，有：k lb(n+1)k+1 因为lb(n+1)介于k和k+1之间且大于k，而二叉树的深度又只能是整数，所以必有k为大于或等于lb(n+1)-1的最小整数。可简写为k=lb(n+1)-1。例如，2.0=2，2.1=3。,若结点个数n=0，则有深度k=-1，满足k=lb(0+1)-1=-1；若结点个数n=1，则有深度k=0，满

9、足k=lb(1+1)-1=0；若结点个数n=2，则有深度k=1，满足k=lb(2+1)-1=0.xx=1；若结点个数n=3，则有深度k=1，满足k=lb(3+1)-1=1。,性质5 对于一棵有n个结点的完全二叉树，按照从上至下和从左至右的顺序对所有结点从0开始顺序编号,则对于序号为i的结点(0i 0，则其双亲是结点(i-1)/2(“/”表示整除）；如果i=0，则结点i是根结点，无双亲。(2)如果2i+1n，其左孩子是结点2i+1；如果2i+1n，则结点i无左孩子。(3)如果2i2n，其右孩子是结点2i2；如果2i2n，则结点i无右孩子。,结论：如果完全二叉树按照从上到下和从左到右的顺序对所有结

10、点顺序编号，则可以用一维数组存储完全二叉树。,二叉树的顺序存储结构,二叉树的存储结构 二叉树的存储结构主要有三种：顺序存储结构、链式存储结构和仿真指针存储结构。1.二叉树的顺序存储结构 完全二叉树的结点可按从上至下和从左至右的次序存储在一维数组中，其结点之间的关系可由公式计算得到，这就是二叉树的顺序存储结构。下面两棵树在数组中的存储结构分别为：,8.3二叉树的设计和实现,A,B,C,D,E,F,0,1,2,3,4,5,A,B,C,D,E,F,0,1,2,3,4,5,数据,双亲,左孩子,右孩子,0,1,2,3,4,5,A,B,C,D,E,F,和n=6比较,和0比较,-1,1,2,0,3,4,i,

11、0,5,1,1,2,对于一般的非完全二叉树显然不能直接使用二叉树的顺序存储结构。可以首先在非完全二叉树中增添一些并不存在的空结点使之变成完全二叉树的形态，然后再用顺序存储结构存储。,(a)一般二叉树,(b)完全二叉树形态,(c)在数组中的存储形式,2.二叉树的链式存储结构 二叉树的链式存储结构是用指针建立二叉树中结点之间的关系。二叉树最常用的的链式存储结构是二叉链。二叉链存储结构的每个结点包含三个域，分别是数据域data、左孩子指针域leftChild和右孩子指针域rightChild。二叉链存储结构中每个结点的图示结构为：,二叉链存储结构的二叉树也有不带头结点和带头结点两种。带头结点的二叉链

12、存储结构的二叉树见下图(b)，不带头结点的二叉链存储结构的二叉树如下图(a)所示。,图8-10 二叉链存储结构的二叉树,(a)不带头结点的二叉树,(b)带头结点的二叉树,3.二叉树的仿真指针 二叉树的仿真指针存储结构是用数组存储二叉树中的结点，数组中每个结点除数据元素域外，再增加仿真指针域用于仿真常规指针建立二叉树中结点之间的关系。,二叉树的仿真二叉链存储结构,8.3.2 二叉链结构的二叉树设计,带头结点的二叉树,数据域,右孩子指针,结点,于是，一棵二叉树就可以用一个指向根节点上述结构体的指针变量表示。,用一个变量表示,结构体变量结构体指针,整体看待,左孩子指针,首先：定义相应的结点结构体,二

13、叉树结点结构体定义,typedef struct Node DataType data;struct Node*leftChild;struct Node*rightChild;BiTreeNode;,数据域,右孩子指针,左孩子指针,初始化：对于给定的二叉树化为空树。,void Initiate(BiTreeNode*root)*root=(BiTreeNode*)malloc(sizeof(BiTreeNode);(*root)-leftChild=NULL;(*root)-rightChild=NULL;,给定：BiTreeNode*root;,/*左子树插入结点*/功能：在当前结点处插入

14、一个新的结点作为当前结点的左子树；而当前结点的原来左子树变成新插入结点的左子树。,curr,(1)确定当前结点是否存在(2)断其左子树(引入新的指针)(3)创建新的结点s(4)s添加数据x,t,s,x,(5)确定s的左右孩子,(6)确定当前结点curr的左孩子,(7)还回插入结点的指针,/*左子树插入结点*/BiTreeNode*InsertLeftNode(BiTreeNode*curr,DataType x)BiTreeNode*s,*t;if(curr=NULL)return NULL;t=curr-leftChild;s=(BiTreeNode*)malloc(sizeof(BiTre

15、eNode);s-data=x;s-leftChild=t;s-rightChild=NULL;curr-leftChild=s;return curr-leftChild;,/*右子树插入结点*/-思想和左子树插入相同BiTreeNode*InsertRightNode(BiTreeNode*curr,DataType x)BiTreeNode*s,*t;if(curr=NULL)return NULL;t=curr-rightChild;s=(BiTreeNode*)malloc(sizeof(BiTreeNode);s-data=x;s-rightChild=t;s-leftChild=

16、NULL;curr-rightChild=s;return curr-rightChild;,/*删除当前结点的左子树*/BiTreeNode*DeleteLeftTree(BiTreeNode*curr)if(_)return NULL;Destroy(,curr,存在否？,存在否？,curr=NULL|curr-leftChild=NULL,NULL,/*删除当前结点的右子树*/BiTreeNode*DeleteRightTree(BiTreeNode*curr)if(curr=NULL|curr-rightChild=NULL)return _;Destroy(,curr,存在否？,存在

17、否？,NULL,curr,例8-1 编写一个建立如图8-10（b）所示的带头结点的二叉链存储结构二叉树的程序。#include#include typedef char DataType;#include Bitree.h“Void main(void)BiTreeNode*root,*p;Initiate(,InsertLeftNode,p,G,root-leftChild,8.4 二叉树遍历,1.二叉树遍历的基本方法,从二叉树的定义知，一棵二叉树由三部分组成：根结点、左子树和右子树。若规定D,L,R分别代表“访问根结点”、“遍历根结点的左子树”和“遍历根结点的右子树”，根据遍历算法对访问根

18、结点处理的位置，称下面三种遍历算法分别为前序遍历（DLR）、中序遍历（LDR）和后序遍历（LRD）。,8.4.1 二叉树遍历,前序遍历（DLR）递归算法为：若二叉树为空则算法结束；否则：（1）访问根结点；（2）前序遍历根结点的左子树；（3）前序遍历根结点的右子树。对于图8-7（b）所示的二叉树，前序遍历访问结点的次序为：A B D G C E F,中序遍历（LDR）递归算法为：若二叉树为空则算法结束；否则：（1）中序遍历根结点的左子树；（2）访问根结点；（3）中序遍历根结点的右子树。对于图8-7（b）所示的二叉树，中序遍历访问结点的次序为：D G B A E C F,后序遍历（LRD）递归算法

19、为：若二叉树为空则算法结束；否则：（1）后序遍历根结点的左子树；（2）后序遍历根结点的右子树；（3）访问根结点。对于图8-7（b）所示的二叉树，后序遍历访问结点的次序为：G D B E F C A,此外，二叉树还有层序遍历。层序遍历的要求是：按二叉树的层序次序（即从根结点层至叶结点层），同一层中按先左子树再右子树的次序遍历二叉树。它的特点是，在所有未被访问结点的集合中，排列在已访问结点集合中最前面结点的左子树的根结点将最先被访问，然后是该结点的右子树的根结点。这样，如果把已访问的结点放在一个队列中，那么，所有未被访问结点的访问次序就可以由存放在队列中的已访问结点的出队列次序决定。因此可以借助队

20、列实现二叉树的层序遍历。,二叉树的层序遍历算法如下：（1）初始化设置一个队列；（2）把根结点指针入队列；（3）当队列非空时，循环执行步骤（3.a）到步骤（3.c）；（3.a）出队列取得一个结点指针，访问该结点；（3.b）若该结点的左子树非空，则将该结点的左子树指 针入队列；（3.c）若该结点的右子树非空，则将该结点的右子树指 针入队列；（4）结束。,2.二叉树的遍历方法和二叉树的结构 二叉树是非线性结构，每个结点会有零个、一个或两个孩子结点，一个二叉树的遍历序列不能决定一棵二叉树，但某些不同的遍历序列组合可以惟一确定一棵二叉树。可以证明，给定一棵二叉树的前序遍历序列和中序遍历序列可以惟一确定一

21、棵二叉树的结构。,当对一个二叉树用一种特定的遍历方法来遍历时，其遍历序列一定是线性的，且是惟一的。,8.4.2 二叉链存储结构下二叉树遍历的实现(1/4),前序遍历思想：先根，再左子树，最后右子树,前序遍历思想遍历左子树,前序遍历思想遍历右子树,函数实现：函数名PreOrder,函数PreOrder的调用问题,函数PreOrder的调用问题,什么时候停止重复操作？,!=NULL,8.4.2 二叉链存储结构下二叉树遍历的实现(2/4)void PreOrder(BiTreeNode*t,void Visit(DataType item)/*前序遍历二叉树t，访问操作为Visit()函数*/if(

22、t!=NULL)Visit(t-data);_(t-leftChild,Visit);PreOrder(t-rightChild,Visit);为了通用性，把对结点的访问操作设计成前序遍历二叉树函数的一个函数虚参 Visit()。,PreOrder,A,B,D,G,C,E,F,void InOrder(BiTreeNode*t,void Visit(DataType item)/*中序t*/if(t!=NULL)InOrder(t-leftChild,Visit);Visit(t-data);InOrder(t-rightChild,Visit);void PostOrder(BiTreeNo

23、de*t,void Visit(DataType item)/*后序*/if(t!=NULL)PostOrder(t-leftChild,Visit);PostOrder(t-rightChild,Visit);Visit(t-data);,二叉树撤消操作函数,二叉树的撤消操作实际上是二叉树遍历操作的一个具体应用。由于二叉树中每个结点允许有左孩子结点和右孩子结点，所以在释放某个结点的存储空间前必须先释放该结点左孩子结点的存储空间和右孩子结点的存储空间，因此，二叉树撤消操作必须是后序遍历的具体应用。撤消操作算法实现如下：,void Destroy(BiTreeNode*root)if(*root

24、)!=NULL,root,root存在否？,左子树存在否？,右子树存在否？,撤销,撤销,释放根结点,撤销,8.4.3 二叉树遍历的应用,1 打印二叉树 把二叉树逆时针旋转900C，按照二叉树的凹入表示法打印二叉树。可把此函数设计成递归函数。由于把二叉树逆时针旋转900C后，在屏幕上方的首先是右子树，然后是根结点，最后是左子树，所以打印二叉树算法是一种特殊的中序遍历算法。,void PrintBiTree(BiTreeNode*bt,int n)int i;if(bt=NULL)return;PrintBiTree(bt-rightChild,n+1);PrintBiTree(bt-leftCh

25、ild,n+1);,for(i=0;i=0)printf(-);printf(%cn,bt-data);,A,C,F,0,1,2,3,3,E,2,在二叉树中查找数据元素操作的要求是：在bt为根结点指针的二叉树中查找数据元素x，若查找到数据元素x时返回该结点的指针；若查找不到数据元素x时返回空指针。在二叉树bt中查找数据元素x算法可设计成先序遍历算法，此时查找结点的次序是：首先在根结点查找，然后在左子树查找，最后在右子树查找。但是，和常规递归算法不同的是，此算法当一个分支上的结点比较完仍未查找到数据元素x时，要返回到该结点的双亲结点处继续查找。因此，此算法是一个回溯算法。,2 查找数据元素,Bi

26、TreeNode*Search(BiTreeNode*bt,DataType x)BiTreeNode*p;if(bt=NULL)return NULL;if(_)return bt;if(bt-leftChild!=NULL)p=_(bt-leftChild,x);if(_)return p;if(_!=NULL)p=Search(bt-rightChild,x);if(p!=NULL)return p;return NULL;,先序遍历查找,bt-data=x,Search,p!=NULL,bt-rightChild,例8-2 编写一个程序，首先建立如图8-10（b）所示的带头结点的二叉链

27、存储结构二叉树，然后打印该二叉树，最后输出分别按照前序遍历二叉树次序、中序遍历二叉树次序和后序遍历二叉树次序访问各结点的序列信息。设计：输出显示函数设计：按照某种遍历方法输出显示二叉树各结点的信息，其实就是把上述各遍历二叉树函数中的Visit()函数设计成输出显示结点信息的函数。Visit()函数设计如下：void Visit(DataType item)printf(%c,item);,3.应用举例,8.6 哈夫曼树,1.哈夫曼树的基本概念,从A结点到B结点所经过的分支序列叫做从A结点到B结点的路径；从A结点到B结点所经过的分支个数叫做从A结点到B结点的路径长度；从二叉树的根结点到二叉树中所

28、有叶结点的路径长度之和称作该二叉树的路径长度。设二叉树有n个带权值的叶结点，定义从二叉树的根结点到二叉树中所有叶结点的路径长度与相应叶结点权值的乘积之和称作该二叉树的带权路径长度（WPL），即：,WPL=,其中，wi为第i个叶结点的权值，li为从根结点到第i个叶结点的路径长度。,下图所示二叉树带权路径长度分别为:,二叉树的带权路径长度？,二叉树的叶结点数和权值？,（a）WPL=12+32+52+72=32（b）WPL=12+33+53+71=33（c）WPL=73+53+32+11=43（d）WPL=13+33+52+71=29,具有最小带权路径长度的二叉树称作哈夫曼（Huffman）树（或称

29、最优二叉树）。图（d）的二叉树是一棵哈夫曼树。,定义：由给定的n个叶结点权值可以构造很多棵形态不同的二叉树，WPL值最小的二叉树称为哈夫曼树。要使一棵二叉树的带权路径长度WPL值最小，必须使权值越大的叶结点越靠近根结点。哈夫曼树构造算法为：,（1）由给定的n个权值w1,w2,wn构造n棵只有根结点的二叉树，从而得到一个二叉树森林F=T1,T2,Tn。（2）在二叉树森林F中选取根结点的权值最小和次小的两棵二叉树作为新的二叉树的左右子树构造新的二叉树，新的二叉树的根结点权值为左右子树根结点权值之和。（3）在二叉树森林F中删除作为新二叉树左右子树的两棵二叉树，将新二叉树加入到二叉树森林F中。（4）重

30、复步骤（2）和（3），当二叉树森林F中只剩下一棵二叉树时，这棵二叉树就是所构造的哈夫曼树。,2.哈夫曼编码问题,将传送的文字转换为二进制字符0和1组成的二进制串的过程为编码。,例：假设要传送的电文为ABACCDA，电文中只有A,B,C,D四种字符，若这四个字符采用表(a)所示的编码方案，则电文的代码为00 01 00 10 10 11 00，代码总长度为14。若这四个字符采用表(b)所示的编码方案，则电文的代码为0 110 0 10 10 111 0，代码总长度为13。,（a）,（b）,哈夫曼树可用于构造代码总长度最短的编码方案。具体构造方法如下：设需要编码的字符集合为d1,d2,dn，各个字

31、符在电文中出现的次数集合为w1,w2,wn，以d1,d2,dn作为叶结点，以w1,w2,wn作为各叶结点的权值构造一棵二叉树，规定哈夫曼树中的左分支为0，右分支为1，则从根结点到每个叶结点所经过的分支对应的0和1组成的序列便为该结点对应字符的编码。代码总长度最短的不等长编码称之为哈夫曼编码。不等长编码不允许存在前缀码。前缀码的一个例子如：A为01，B为010。如编码存在前缀码，则译码会出现二义性。问题：为什么哈夫曼编码一定不会出现前缀码？,3.哈夫曼编码的软件设计,构造哈夫曼树:方便的实现从双亲结点到左右孩子结点的操作;哈夫曼编码:方便的实现从孩子结点到双亲结点的操作。设计哈夫曼树的结点存储结

32、构为双亲孩子存储结构。采用仿真指针实现，每个结点的数据结构设计为：,一、哈夫曼编码的数据结构设计,n个叶结点的Haffman树总共有2n-1个结点，因此这样的树可以用一个长度为2n-1的一维数组来管理,结构数组,从哈夫曼树求叶结点的哈夫曼编码实际上是从叶结点到根结点路径分支的逐个遍历，每经过一个分支就得到一位哈夫曼编码值。存放哈夫曼编码的数据元素结构为：,weight,编码的起始位置,例如start=1.,编码区,该weight对应字符的对应码字为：Bit1,Bit2,BitMaxBit-1,结构变量,结构数组,二、哈夫曼编码的算法实现,typedef struct/哈夫曼树的结点结构 int

33、 weight;/权值 int flag;/标记 int parent;/双亲结点下标 int leftChild;/左孩子下标 int rightChild;/右孩子下标 HaffNode;typedef struct/存放哈夫曼编码的数据元素结构 int bitMaxN;/数组 int start;/编码的起始下标 int weight;/字符的权值 Code;,HaffNode类型的结构数组;长度为2n-1,Code类型的结构数组;长度为n,初始化,w0,w2,w1,w3,Wn-1,2*n-1,0,1,2,3,n-1,n,n+1,n+2,n+3,选择最小值m1和次小值m2,记录最小值m1

34、的位置x1和次小值m2的位置x2,计算m1+m2这为第n个结点，也就是第1个非叶结点,Wn,第1个非叶结点,第2个非叶结点,从w0,w1,wn-1-wx1,wx2+wn里面选择最小和次小；,为了方便，对每个结点引入一个标志flag，flag=0表示余下的，flag=1表示去除的。,flag,0,0,0,0,0,0,0,0,0,0,重复前面的操作,1,1,对于给定的n个权值,结构数组haffTree2*n-1;,第一步：初始化具有2*n-1个结点的哈夫曼树haffTree2*n-1;第二步：对n-1个非叶结点进行循环生成每个非叶结点都是从haffTree的第0个元素开始到最近加入的非叶结点注意寻

35、找最小值和次最小值(条件是标记为0)根据找到的最小值和次最小值生成非叶结点修改相应的权值、父母、孩子、标记的值,哈夫曼树构造算法如下：void Haffman(int weight,int n,HaffNode haffTree)/建立叶结点个数为n权值为weight的哈夫曼树haffTree int i,j,m1,m2,x1,x2;/哈夫曼树haffTree初始化。n个叶结点的哈夫曼树共有2n-1个结点 for(int i=0;i 2*n-1;i+)if(i n)haffTreei.weight=weighti;else haffTreei.weight=0;haffTreei.parent

36、=-1;haffTreei.flag=0;haffTreei.leftChild=-1;haffTreei.rightChild=-1;,/构造哈夫曼树haffTree的n-1个非叶结点 for(i=0;i n-1;i+)m1=m2=MaxValue;x1=x2=0;for(j=0;j n+i;j+)if(haffTreej.weight m1,在0-n+i-1中寻找最小和次小,/将找出的两棵权值最小的子树合并为一棵子树 haffTreex1.parent=n+i;haffTreex2.parent=n+i;haffTreex1.flag=1;haffTreex2.flag=1;haffTre

37、en+i.weight=haffTreex1.weight+haffTreex2.weight;haffTreen+i.leftChild=x1;haffTreen+i.rightChild=x2;,1,A,3,B,5,C,7,D,4,9,16,输入huffTree和叶节点数n,0,0,1,临时记录编码,实际编码,0,0,1,第0个叶节点,当作孩子结点,找该孩子结点的父母结点,确定该孩子是父母结点的左还是右,确定编码,找到的父母结点当作新的孩子,父母结点存在否？,找该孩子结点的父母结点,临时编码起始位,临时编码起始位减少1,1,A,3,B,5,C,7,D,4,9,16,输入huffTree和叶

38、节点数n,第1个叶节点,当作孩子结点,找该孩子结点的父母结点,确定该孩子是父母结点的左还是右,确定编码,找到的父母结点当作新的孩子,1,0,1,临时记录编码,实际编码,1,0,1,父母结点存在否？,找该孩子结点的父母结点,临时编码起始位,临时编码起始位减少1,哈夫曼编码算法如下：void HaffmanCode(HaffNode haffTree,int n,Code haffCode)Code*cd=(Code*)malloc(sizeof(Code);int i,j,child,parent;/*求n个叶结点的哈夫曼编码*/for(i=0;i start=n-1;cd-weight=haf

39、fTreei.weight;child=i;parent=haffTreechild.parent;,/*由叶结点向上直到根结点*/while(parent!=-1)if(haffTreeparent.leftChild=child)cd-bitcd-start=0;else cd-bitcd-start=1;cd-start-;child=parent;parent=haffTreechild.parent;for(j=cd-start+1;j bitj;haffCodei.start=cd-start+1;haffCodei.weight=cd-weight;,例：设有字符集A,B,C,D

40、，各字符在电文中出现的次数集为1,3,5,7，则哈夫曼树构造过程如下图所示：,（a）,（b）第一步的结果,（c）第二步的结果,（d）哈夫曼树构造结果,0 1 2 3 bit start weight（e）哈夫曼编码结果,例8-5 设有字符集A,B,C,D，各字符在电文中出现的次数集为1,3,5,7，设计各字符的哈夫曼编码。#include#include#define MaxValue 10000#define MaxBit 4#define MaxN 100#include Haffman.h,void main(void)int i,j,n=4;int weight=1,3,5,7;Haf

41、fNode*myHaffTree=(HaffNode*)malloc(sizeof(HaffNode)*(2*n-1);Code*myHaffCode=(Code*)malloc(sizeof(Code)*n);if(n MaxN)printf(给出的n越界，修改MaxN值!n);exit(0);Haffman(weight,n,myHaffTree);HaffmanCode(myHaffTree,n,myHaffCode);/*输出每个叶结点的哈夫曼编码*/for(i=0;i n;i+)printf(Weight=%d Code=,myHaffCodei.weight);for(j=myHa

42、ffCodei.start;j n;j+)printf(%d,myHaffCodei.bitj);printf(n);,程序运行输出结果如下：Weight=1 Code=100Weight=3 Code=101Weight=5 Code=11Weight=7 Code=0 该结果和图8-15所示的该问题的人工设计的哈夫曼编码方案完全吻合。,8.4.4.非递归的二叉树遍历算法,所有递归算法都可以借助堆栈转换成循环结构的非递归算法，通常有两种方法：一种方法是形式化模拟转换，另一种方法是根据要求解问题的特点设计借助堆栈的循环结构算法。,非递归的二叉树前序遍历算法如下：（1）初始化设置一个堆栈；（2）

43、把根结点指针入栈；（3）当堆栈非空时，循环执行步骤（3.a）到步骤（3.c）；（3.a）出栈取得一个结点指针，访问该结点；（3.b）若该结点的右子树非空，则将该结点的右子树指针入栈；（3.c）若该结点的左子树非空，则将该结点的左子树指针入栈；（4）结束。,问题：（1）这个算法和哪个算法相似？（2）为什么相似？（3）非递归的二叉树前序遍历算法有什么用途？,8.5 线索二叉树,线索二叉树是另一种分步遍历二叉树的方法。它既可以从前向后分步遍历二叉树，又可以从后向前分步遍历二叉树。,当按某种规则遍历二叉树时，保存遍历时得到的结点的后继结点信息和前驱结点信息的最常用的方法是建立线索二叉树。对二叉链存储结

44、构的二叉树分析可知，在有n个结点的二叉树中必定存在n+1个空链域。,规定：当某结点的左指针为空时，令该指针指向按某种方法遍历二叉树时得到的该结点的前驱结点；当某结点的右指针为空时，令该指针指向按某种方法遍历二叉树时得到的该结点的后继结点。仅仅这样做会使我们不能区分左指针指向的结点到底是左孩子结点还是前驱结点，右指针指向的结点到底是右孩子结点还是后继结点。因此我们再在结点中增加两个线索标志位来区分这两种情况。,每个结点的结构就如下所示：,结点中指向前驱结点和后继结点的指针称为线索。在二叉树的结点上加上线索的二叉树称作线索二叉树。对二叉树以某种方法（如前序、中序或后序方法）遍历使其变为线索二叉树的

45、过程称作按该方法对二叉树进行的线索化。,线索标志位定义如下：,线索二叉树,一旦建立了某种方式的线索二叉树后，用户程序就可以像操作双向链表一样操作该线索二叉树。例如，一旦建立了中序线索二叉树后，用户程序就可以设计一个正向循环结构遍历该二叉树的所有结点，循环初始定位在中序线索二叉树的第一个结点位置，每次循环使指针指向当前结点的中序遍历的后继结点位置，当指针指向中序线索二叉树的最后一个结点位置后循环过程结束；或者用户程序可以设计一个反向循环结构遍历该二叉树的所有结点，循环初始定位在中序线索二叉树的最后一个结点位置，每次循环使指针指向当前结点的中序遍历的前驱结点位置，当指针指向中序线索二叉树的第一个结

46、点位置前循环过程结束。,这种算法设计要求分别设计三个函数：First()：定位在第一个结点位置；Next()：移动到下一个结点位置；End()：是否已经到最后下一个结点位置；当然，还需要一个根据二叉树构造线索二叉树的函数。,typedef struct ThreadBiNode*root;ThreadBiNode*current;int nextComplete;ThreadBiTree;void ThreadInitiate(ThreadBiTree*tree,ThreadBiNode*root)tree-root=root;tree-current=root;if(root=NULL)tr

47、ee-nextComplete=1;else tree-nextComplete=0;,void First(ThreadBiTree*tree)tree-current=tree-root;while(tree-current-leftThread=0 tree-current=tree-current-leftChild;if(tree-current=tree-root)tree-nextComplete=1;else tree-nextComplete=0;,void Next(ThreadBiTree*tree)ThreadBiNode*p=tree-current-rightChi

48、ld;if(tree-nextComplete=1)return;if(tree-current-rightThread=0)while(p-leftThread=0)p=p-leftChild;tree-current=p;if(tree-current=tree-root)tree-nextComplete=1;int EndOfNext(ThreadBiTree*tree)return tree-nextComplete;,例8-3 编写一个程序，首先建立如图8-10（a）所示的不带头结点的二叉树，然后中序线索化该二叉树，最后用循环结构输出该中序线索化二叉树各结点的序列信息。,void

49、main(void)ThreadBiNode*root;ThreadBiTree tree;MakeCharTree(,8.7 等价问题,1等价关系和等价类 若集合X上的关系R是自反的、对称的和传递的，则称关系R是集合X上的等价关系。设关系R为定义在集合X上的二元关系，若对于每一个xX，都有(x,x)R，则称R是自反的。例如，相等关系就是自反关系。设关系R为定义在集合X上的二元关系，若对于任意的x,yX，若当(x,y)R时，有(y,x)R，则称R是对称的。例如，相等关系就是对称关系。,等价关系的实质是将集合中的元素分类。若关系R是集合X上的一个等价关系，则可以按R将集合X划分成若干互不相交的子

50、集X1,X2,X3,，这些子集的并X1X2X3为集合X，则这些子集便称为集合X的关于R的等价类。,设关系R为定义在集合X上的二元关系，如果对于任意的x,y,zX，若当(x,y)R且(y,z)R时，有(x,z)R，则称关系R是传递的。例如，设集合X=1,2,3，关系R=(1,2),(2,3),(1,3)，则关系R是传递的。另外，相等关系也是传递关系。,2等价类的应用 许多应用问题可以归结为按给定的等价关系划分某集合为等价类，通常称这类问题为等价问题。例如，要测试一个软件是否存在问题，这个软件所有允许的输入数据构成了集合，这个集合中的元素通常很多。我们把软件所有允许的输入数据域划分成若干子集合，然