树与二叉树的关系.ppt

6.4.1 树的存储结构 6.4.2 树、森林与二叉树的相互转换 6.4.3 树与森林的转换,6.4 树、森林和二叉树的关系,6.4.1 树的存储结构,树的主要存储方法有： 一、双亲表示法 二、孩子表示法 三、孩子兄弟表示法,一、 双亲表示法：,用一组连续的空间来存储树中的结点，每个结点附设一个指示器指示其双亲结点在表中的位置，其结点的结构如下：,树的双亲表示法如下图：,双亲表示法的优点： 利用了树中每个结点（根结点除外）只有一个双亲结点的性质，使得查找某个结点的双亲结点非常容易。,双亲表示法的缺点： 求某个结点的孩子时，需要遍历整个表。,#define MAX 100 typedef struct TNode DataType data; int parent; TNode;,一棵树可以定义为：,typedef struct TNode treeMAX; int nodenum; /*结点数*/ ParentTree;,双亲表示法的结点结构定义：,二、 孩子表示法：,通常是把每个结点的孩子结点排列起来，构成一个单链表，称为孩子链表。n个结点共有n个孩子链表（叶结点的孩子链表为空表）。 n个结点的数据和n个孩子链表的头指针又组成一个顺序表。,树的孩子链表表示法见p175的图6.26,孩子表示法示意图:,A,B,C,D,E,F,G,1 A 2 B 3 C 4 D 5 E 6 F 7 G,root=1 num=7,data fch,par,带双亲的孩子表示法:,孩子表示法的结构定义：,typedef struct ChildNode /* 孩子链表结点的定义 */ int Child; struct ChildNode * next; ChildNode;,typedef struct /* 树的定义 */ DataNode nodesMAX; /* 顺序表 */ int root, num; /* 根结点指示及结点个数 */ ChildTree;,typedef struct /* 顺序表结点的结构定义 */ DataType data; ChildNode * FirstChild ; DataNode;,三、 孩子兄弟表示法,孩子兄弟表示法又称二叉链表表示法，表中每个结点设有两个链域，分别指向该结点的第一个孩子结点和下一个兄弟（右兄弟）结点。,孩子兄弟表示法的结点结构定义：,typedef struct CSNode DataType data; Struct CSNode *FCh, *Nsib; CSNode, *CSTree;,孩子兄弟表示法示意图：,优点：便于实现树的各种操作； 可实现树(森林)与二叉树的相互转换。,A,B,C,D,E,F,G,A,B,C,D,E,F,G,对应的关系： 树 二叉树 根 根 第一孩子 左孩子 下一兄弟 右孩子,一、 树转换为二叉树,约定树中每一个结点的孩子结点按从左到右的次序顺序编号，即把树看作为有序树。,6.4.2 树、森林与二叉树的相互转换,将一棵树转换为二叉树的方法：, 树中所有相邻兄弟之间加一条连线。 对树中的每个结点，只保留其与第一个孩子结点之间的连线，删去其与其它孩子结点之间的连线。 以树的根结点为轴心，将整棵树顺时针旋转一定的角度，使之结构层次分明。,树转换为二叉树示意图,森林转换为二叉树的方法为：,（1）将森林中的每棵树转换成相应的二叉树。,（2）第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树根结点的右孩子，当所有二叉树连在一起后，所得到的二叉树就是由森林转换得到的二叉树。,二、森林转换为二叉树,森林转换为二叉树示意图,森林转换为二叉树的实例另见p179的图6.31,递归方法描述森林转换为二叉树:,将森林F看作树的有序集F=T1，T2，,TN，它对应的二叉树为B（F）：,（1）若N0，则B（F）为空。,（2）若N0，则： 二叉树B（F）的根为森林中第一棵树T1的根； B（F）的左子树为B（T11，T1m），其中T11，T1m是T1的子树森林； B（F）的右子树是B（T2，TN）。,二叉树转换为树或森林的方法为：,（1）若某结点是其双亲的左孩子，则把该结点的右孩子、右孩子的右孩子、都与该结点的双亲结点用线连起来。 （2）删掉原二叉树中所有双亲结点与右孩子结点的连线。 （3）整理由（1）、（2）两步所得到的树或森林，使之结构层次分明。,三、二叉树转换为树或森林,二叉树转换为森林的示意图,若B是一棵二叉树，T是B的根结点，L是B的左子树，R为B的右子树，设B对应的森林F（B）中含有的n棵树为T1,T2, ,Tn，则有：,（1）B为空，则：F（B）为空的森林（n0）。,（2）B非空，则： F（B）中第一棵树T1的根为二叉树B的根T； T1中根结点的子树森林由B的左子树L转换而成，即F（L）=T11,T1m； B的右子树R转换为F（B）中其余树组成的森林，即F(R) T2, T3, ,Tn。,用递归的方法描述其转换,6.4.3 树与森林的遍历,一、 树的遍历,树的遍历主要有以下两种： 先根遍历 后根遍历,1、先根遍历,若树非空，则遍历过程为： （1）访问根结点。 （2）从左到右，依次先根遍历根结点的每一棵子树。,如图中树的先根遍历序列为：ABECFHGD。,若树非空，则遍历过程为：,（1）从左到右，依次后根遍历根结点的每一棵子树。 （2）访问根结点。,如图树的后根遍历序列为： EBHFGCDA。,2、后根遍历,树的后根遍历：H I J E B C F G D A,树的先根遍历：A B E H I J C D F G,对应二叉树的先序遍历,对应二叉树的中序遍历,二、树的遍历算法,三、森林的遍历,森林的遍历方法主要有以下三种： 先序遍历 中序遍历 *后序遍历,1、先序遍历,若森林非空，则遍历方法为：,（1）访问森林中第一棵树的根结点。 （2）先序遍历第一棵树的根结点的子树森林。 （3）先序遍历除去第一棵树之后剩余的树构成的森林。,即：依次从左至右对森林中的每一棵树进 行先根遍历。,若森林非空，则遍历方法为：,（1）中序遍历森林中第一棵树的根结点的 子树森林。 （2）访问第一棵树的根结点。 （3）中序遍历除去第一棵树之后剩余的树 构成的森林。,2、中序遍历,即：依次从左至右对森林中的每一棵树进行 后根遍历。,先序遍历森林时顶点的访问次序：,A B C D E F G H I J,中序遍历森林时顶点的访问次序：,B C D A F E I H J G,树和森林的遍历和二叉树遍历的对应关系 ？,先根遍历,后根遍历,树,二叉树,森林,先序遍历,先序遍历,中序遍历,中序遍历,3、森林的后序遍历*,若森林非空，则遍历方法为：,（1）后序遍历森林中第一棵树的根结点的子树森林。 （2）后序遍历除去第一棵树之后剩余的树构成的森林。 （3）访问第一棵树的根结点。,6.5 哈夫曼树及其应用,6.5.1 哈夫曼树,哈夫曼树最典型、最广泛的应用是在编码技术上，利用哈夫曼树，可以得到平均长度最短的编码。这在通讯领域是极其有价值的。 计算机程序操作码的优化也可以利用哈夫曼树实现。,路径：从一个结点到另一个结点之间的分支 序列。,路径长度：从一个结点到另一个结点所经过 的分支条数。,树的路径长度：树中每个结点与根之间的路径 长度之和（PL）。,例：,PL(a)=1+1+2+2+2+2=10,PL(b)=1+1+2+2+3+3=12,一、基本概念：,带权路径长度：在树形结构中，我们把从树根到某一结点的路径长度与该结点权的乘积，称做该结点的带权路径长度。,树的带权路径长度：树中所有叶子结点的带权路径长度之和，称为树的带权路径长度，通常记为WPL：,其中：n为叶子结点的个数；wi为第i个叶子的权值； li为第i个叶子结点的路径长度。,结点的权：给树中每个结点赋予一个具有实际意义的数值，我们称该数值为这个结点的权。,例如下图所示的三棵二叉树,WPL(a)=7252224236,其带权路径长度分别为：,WPL(b)=4273532146,WPL(c)=7152234335,什么样的树的带权路径长度WPL最小？,例如：给定一个权值序列2, 4, 5, 7，可构造多种二叉树的形态:,问题2：,在各种形态的含有 n个叶子结点的 二 叉树中, 必存在一棵(几棵)其带权路径长度值WPL 最小的树，被称为“最优二叉树” 。,特征：在最优二叉树中没有度数为 1 的结点(可用反证法证明); 含 n个叶子结点的最优二叉树的总结点数为 2*n-1 (依据二叉树性质三)。,最优二叉树的构造方法最早由哈夫曼研究，所以又称为“哈夫曼树”。,二、哈夫曼树的构造,(1) 根据给定的 n 个权值 w1, w2, , wn ,构造 n 棵二叉树的集合 F = T1, T2, , Tn， 其中每棵二叉树中均只含一个带权值为 wi 的根结点，其左、右子树为空树；,构造哈夫曼树的方法：,在 F 中选取其根结点的权值为最小的两棵二叉树, 分别作为左、右子树构造一棵新的二叉树, 并置这棵新的二叉树根结点的权值为其左、右子树根结点的权值之和；,(2),从F中删去这两棵树,并加入刚生成的新树；,重复 (2) 和 (3) ,直至 F 中只含一棵树为止。,(3),(4),由此得到二叉树就是“最优二叉树” 即“哈夫曼树” 。,例如:,已知权值 W= 5, 6, 2, 9, 7 ,5,2,7,6,7,13,构造哈夫曼树如下：,9,16,29,三、哈夫曼算法的实现,n个叶子结点的哈夫曼树共有2n-1个结点,因此可用有2n-1个元素的数组来存储哈夫曼树, 结点间的关系用游标表示，即采用静态链表来存储哈夫曼树。,1、存储结构,每个结点需包含其双亲结点信息和孩子结点信息，所以构成一个静态三叉链表。,静态三叉链表结构定义,#define N 20 #define M 2*N-1 typedef struct int weight ; int parent，Lchild，Rchild ; HTNode, HuffmanTreeM+1; /*0号单元不用*/,静态三叉链表数组中前 n 个元素存储叶子结点，后n-1个元素存储分支结点即不断生成的新结点，最后一个元素存储哈夫曼树的根结点。,2、哈夫曼算法,初始化：先将n个元素都视为根结点，即孩子和双亲指针全置0。 建哈夫曼树的过程是：反复在数组中选双亲为0(表示它们当前是树根)且权值最小的两结点, 将它们作为左右孩子挂在新的结点之下, 新结点权值为左右孩子权值之和。,void CrtHuffmanTree(HuffmanTree ht , int w, int n) /* w存放已知的n个权值，构造哈夫曼树ht */ ,m=2*n-1; for(i=1;i=n;i+) hti=wi,0,0,0; for(i=n+1;i=m;i+) hti=0,0,0,0;,for(i=n+1;i=m;i+) select(ht,i-1, ,例给定权值: 9,14 ,10 ,10, 12, 13, 9 ,11 ,i wt par Lch Rch 1 5 0 0 0 2 29 0 0 0 3 7 0 0 0 4 8 0 0 0 5 14 0 0 0 6 23 0 0 0 7 3 0 0 0 8 11 0 0 0 9 0 0 0 0 10 0 0 0 0 11 0 0 0 0 12 0 0 0 0 13 0 0 0 0 14 0 0 0 0 15 0 0 0 0,for(i=1;i=n;i+) hti=wi,0,0,0; for(i=n+1;i=m;i+) hti=0,0,0,0;,for(i=n+1;i=m;i+) select(ht,i-1,哈夫曼树最典型的应用是在编码，利用哈夫曼树，可以得到平均长度最短的编码。,6.5.2 哈夫曼编码,平均长度最短的编码一般为不等长编码，为使各编码间无需加分界符即可识别，其编码应是前缀码。,前缀码：同一字符集中任何一个字符的编码都不是另一个字符编码的前缀（最左子串）。,一、概念,利用哈夫曼树可以构造不等长的二进制编码，并且构造所得的编码是一种最优前缀编码，即可以使所传信息的总长度最短。,二、哈夫曼编码:,对哈夫曼树中每个左分支赋予0，右分支赋予1，则从根到每个叶子的路径上，各分支的值构成该叶子的哈夫曼编码。,例：若要传输如下单词 state, seat, act, tea, cat, set, a, eat 如何使所传送的信息编码长度最短？,为保证信息编码长度最短，先统计各字符出现的次数，然后以此作为权值, 构造哈夫曼树。,0,0,0,0,1,1,1,1,00,10,010,011,编码:左分支:0右分支:1； 根到叶子路径上的 值构成叶子的编码。,11,需传输信息：state, seat, act, tea, cat, set, a, eat,构造哈夫曼树：,结论一：哈夫曼编码是前缀码。,若didj(字符不同)，则对应的树叶不同，因为从根到每个叶子的路径是不同的，所以一条路径不可能是另一条路径的前部（前缀），因此哈夫曼编码是前缀码。,三、哈夫曼编码应用举例,例：设有一台模型机，共有7种不同的指令，各指令的使用频率Pi为：,哈夫曼树最典型、最广泛的应用是在编码技术上，而操作码的优化也是其应用之一。,以指令的使用频率为权值构造哈夫曼树，并求各指令的哈夫曼编码。,若用等长编码，其平均码长为3。,各指令的哈夫曼编码为：,四、哈夫曼编码算法,利用哈夫曼树求编码时，编码是由后向前生成的，需要走一条从叶子到根的路径：,当前结点若是其双亲的左子树时，则置当前编码位为0，否则置为1。,当由叶子走到根结点时，完成一个叶子结点编码的求取。,由哈夫曼树生成编码时, 编码存储在多个字符数组中, 每个数组表示一个叶子结点的编码。,存储定义： typedef char * Huffmancoden+1; char * cd; int start;,CrtHuffmanCode(HuffmanTree ht,HuffmanCode hc,int n) /*从叶子到根，逆向求每个叶子对应的哈夫曼编码*/,for(i=1;i=n;i+) /*求每个叶子的哈夫曼编码*/ start=n-1; c=i ; p=hti.parent;,while ( p!=0) -start; if(ht)p.Lchild = c) cdstart=0; /*左分支标0*/ else cdstart=1; /*右分支标1*/ c=p; p=htp.parent; ,hci=(char *)malloc(n-start)*sizeof(char); strcpy(hci,cd=(char * )malloc(n * sizeof(char ); /*当前编码工作空间*/ cdn-1=0; /*从右向左逐位求编码，首先放编码结束符*/,由哈夫曼编码、译码的算法可知：树中每个结点需要有双亲和孩子的指针, 而前述构造哈夫曼树算法中的静态三叉链表已提供了相应的信息。,利用哈夫曼树译码时，需要走一条从根结点到叶子结点的路径，当前编码位为0时走向左子树，当前编码位为1时走向右子树。当走到叶子结点时，完成一个译码。,6.6 总结与提高,1. 熟练掌握二叉树的结构特性，了解相应的证明方法。,2. 熟悉二叉树的各种存储结构的特点及适用范围。,3. 遍历二叉树是二叉树各种操作的基础。二叉树遍历的具体算法与所采用的存储结构有关。掌握各种遍历策略的递归算法及一种非递归算法，灵活运用遍历算法实现二叉树的其它操作。,4. 了解二叉树线索化的实质是建立结点与其在相应遍历序列中的前驱或后继之间的直接联系。二叉树的线索化过程是基于对二叉树进行遍历，而线索二叉树上的线索又为相应的遍历提供了方便。,5. 熟悉树的各种存储结构及其特点，掌握树和森林与二叉树的转换方法。建立存储结构是进行其它操作的前提，因此应掌握 1 至 2 种建立二叉树和树的存储结构的方法。,6.熟悉哈夫曼树的特性，掌握建立哈夫曼树和哈夫曼编码的方法。,典型例题,int like(BiTree b1, BiTree b2) int like1, like2; if (b1=NULL ,1、二叉树相似性判定,2、层次遍历二叉树,int LayerOrder(BiTree bt) SeqQueue *Q; BiTree p; InitQueue(Q); if(bt = NULL)return ERROR; EnterQueue(Q, bt); while(!IsEmpty(Q) DeleteQueue(Q, ,第六章结束,选择最小子树算法,void select(HuffmanTree ht, int n, int *s1, int *s2) m1=32767; m2=32767; *s1=0; *s2=0; for (i=1;i=n;i+) if (hti.parent=0) ,问题1：,什么样的二叉树的路径长度PL最小？,分析：二叉树中路径长度为0的结点只有1个；,路径长度 0 ，1，1，2，2，2，2，3，3，3，4，4，. 结点数n n=1 n=2,3 n=4, 5 ,6 , 7 n=8. n=15 n=16,可知：结点n对应的路径长度为 log2n ,路径长度为1的结点至多只有2个；,路径长度为2的结点至多只有4个；, 路径长度为K的结点至多只有2k个;,所以n个结点的二叉树其路径长度至少等于如下序列的前n项之和。,因为深度为h的完全二叉树的路径长度为：,所以完全二叉树具有树的路径长度为最小的性质，但不具有唯一性。,例如：下列不同形状的二叉树均具有最小的路径长度,故：深度为h的二叉树若前h-1层为满二叉树， 则具有最小的路径长度。,