大学教程(零起点)数据结构--树修改

1、自自然然中中的的树树抽抽象象的的树树旋转后旋转后适当进行调整适当进行调整ABCDEFGHI数据结构中树的形态，具有分层特点数据结构中树的形态，具有分层特点ABCDEFGHI某姓氏族谱某姓氏族谱ABCDEFGHIJKLMNOPQRSTUV WXY Z.对树中的结点给定一个符号名称，具有一对多的特点对树中的结点给定一个符号名称，具有一对多的特点树描述的是一种层次结构，树描述的是一种层次结构， 是一种一对多的逻辑关系是一种一对多的逻辑关系FGIJABCEDHFGIJABCEDHABCDEFHGMABCDEFHGMABCDEFHGMABCDEFHGMABCDEFHGMABCDEFHGMABCDEFHG

2、MABCDEFHGMABCDEFHGMABCDEFHMABCACB项目实现的进一步分析：项目实现的进一步分析：项目核心问题：项目核心问题： 如何将电报文字转换成如何将电报文字转换成0101编码编码 扩展问题：扩展问题： 电文传送时的高效性电文传送时的高效性扩展问题：扩展问题： 电文传送时的高效性电文传送时的高效性在计算机及通信中，在计算机及通信中，常用二进制编码来表示字符，常用二进制编码来表示字符，假设某电文通信中只使用假设某电文通信中只使用A B C DA B C D四个字符四个字符每个字母用两位二进制数表示，例如每个字母用两位二进制数表示，例如传输传输100100个字母需要用个字母需要用2

3、00200个二进制位个二进制位此种编码方式为等长编码，此种编码方式为等长编码， 此时电文长度由电文字符数决定此时电文长度由电文字符数决定对于电文：对于电文：DABCDABC可翻译为编码：可翻译为编码：对于编码：对于编码：01 00 11 1001 00 11 10可准确翻译为：可准确翻译为：0000表示表示A A0101表示表示B B1010表示表示C C1111表示表示D DB A D CB A D C11 00 01 1011 00 01 10实际情况：实际情况：字符在实际使用中出现频率不一样！字符在实际使用中出现频率不一样！新问题新问题1：如何让电文编码缩短如何让电文编码缩短为提高电文传

4、送效率，应让电文编码尽量短为提高电文传送效率，应让电文编码尽量短考虑问题：考虑问题：出现频率高的字符编码位数少出现频率高的字符编码位数少 出现频率低的字符编码位数多出现频率低的字符编码位数多 以此降低电文总长度以此降低电文总长度 常用汉字常用汉字63356335个，最常用字个，最常用字560560个，常个，常用字用字807807个，次常用字个，次常用字10331033个，共个，共24002400个。这些字占了书刊物汉字出现次数的个。这些字占了书刊物汉字出现次数的99%99%A 8.19 B 1.47 C 3.83 D 3.91A 8.19 B 1.47 C 3.83 D 3.91E 12.25

5、 F 2.26 G 1. 71 H 4.57 E 12.25 F 2.26 G 1. 71 H 4.57 I 7.10 J 0.14 K 0.41 L 3.77 I 7.10 J 0.14 K 0.41 L 3.77 前面十位是：前面十位是：E T A O I N R S D CE T A O I N R S D C假定：假定：某电文通信中只由某电文通信中只由ABCDABCD四个字符构成四个字符构成且出现频率分别为：且出现频率分别为：000 01 1 001 000 000 01 1 001 000 考虑问题：考虑问题：出现频率高的字符编码位数少出现频率高的字符编码位数少 出现频率低的字符编码

6、位数多出现频率低的字符编码位数多 以此降低电文总长度以此降低电文总长度 000000表示表示A A001001表示表示B B 01 01表示表示C C 1 1表示表示D DA 5% A 5% B 10% B 10% C 15% C 15% D 70%D 70%假定：假定：问题：问题：传输传输100100个字母所用的二个字母所用的二进制位为进制位为电文：电文：ACDBAACDBA翻译成编码：翻译成编码：编码：编码：000 01 1 001000 01 1 001翻译成电文翻译成电文: :3 35 5 + + 3 31010 + + 2 215151 17070+ += = 145145A C D

7、 BA C D B此种编码方式为不等长编码，此种编码方式为不等长编码，采用不等长编码可缩短电文编码长度，采用不等长编码可缩短电文编码长度，从而提高电文传送效率从而提高电文传送效率假定：假定：某电文通信中只由某电文通信中只由ABCDABCD四个字符构成四个字符构成且出现频率分别为：且出现频率分别为：考虑问题：考虑问题：出现频率高的字符编码位数少出现频率高的字符编码位数少 出现频率低的字符编码位数多出现频率低的字符编码位数多 以此降低电文总长度以此降低电文总长度 000000表示表示A A001001表示表示B B 01 01表示表示C C 1 1表示表示D DA 5% A 5% B 10% B

8、10% C 15% C 15% D 70%D 70%假定：假定：假定：假定：翻译：翻译：C B D BC B D B翻译：翻译：C B D C DC B D C D新问题新问题2 2：随意的不等长编码可能导致编码翻译时出现歧义随意的不等长编码可能导致编码翻译时出现歧义编码：编码：000011001000011001问题：编码是任意给定的吗？问题：编码是任意给定的吗？000000表示表示A A 001001表示表示B B 00 00表示表示C C 1 1表示表示D D假定：假定：某电文通信中只由某电文通信中只由ABCDABCD四个字符构成四个字符构成且出现频率分别为：且出现频率分别为：A 5%

9、A 5% B 10% B 10% C 15% C 15% D 70%D 70%000 01 1 00 1000 01 1 00 100 001 1 00100 001 1 00100 001 1 00 100 001 1 00 1错误！错误！错误！错误！新知识：新知识：设计不等长编码时，必须做到：任何一个字符的编码设计不等长编码时，必须做到：任何一个字符的编码不能是另一个字符编码的前缀，这种编码为不能是另一个字符编码的前缀，这种编码为前缀码前缀码新问题新问题2 2：随意的不等长编码可能导致编码翻译时出现歧义随意的不等长编码可能导致编码翻译时出现歧义000000表示表示A A001001表示表示

10、B B 01 01表示表示C C 1 1表示表示D D我们设计的第一种编码我们设计的第一种编码是前缀码是前缀码新问题新问题3 3：如何设计前缀码：如何设计前缀码知识点知识点4： 哈夫曼树与哈夫曼编码哈夫曼树与哈夫曼编码知识点知识点4： 哈夫曼树与哈夫曼编码哈夫曼树与哈夫曼编码dcab2475dcab2475WPL=4*2 + 7*3 + 5*3 + 2*1 = 46dcab2475abcd7524WPL=7*2 + 5*2 + 2*2 + 4*2 = 36abcd7524WPL= 7*1 + 5*2 + 2*3 + 4*3 = 35WPL= 7*1 + 4*3 + 2*3 + 5*2 = 35

11、abdc74259例如例如: : 已知权值已知权值 W= 5, 6, 2, 9, 7 W= 5, 6, 2, 9, 7 构造以权值为叶子的哈夫曼树构造以权值为叶子的哈夫曼树5627第一步：把每个权值看作只有一个结点的树第一步：把每个权值看作只有一个结点的树9例如例如: : 已知权值已知权值 W= 5, 6, 2, 9, 7 W= 5, 6, 2, 9, 7 构造以权值为叶子的哈夫曼树构造以权值为叶子的哈夫曼树5267第二步：取权值最小的两棵树，合并成，第二步：取权值最小的两棵树，合并成， 新树的权值为两棵子树权值之和新树的权值为两棵子树权值之和79例如例如: : 已知权值已知权值 W= 5,

12、6, 2, 9, 7 W= 5, 6, 2, 9, 7 构造以权值为叶子的哈夫曼树构造以权值为叶子的哈夫曼树5267第三步：从森林中去掉被合并的结点，并将新第三步：从森林中去掉被合并的结点，并将新合并的树加入到森林中，继续执行第合并的树加入到森林中，继续执行第二步，直到森林合并成为一棵树二步，直到森林合并成为一棵树79例如例如: : 已知权值已知权值 W= 5, 6, 2, 9, 7 W= 5, 6, 2, 9, 7 构造以权值为叶子的哈夫曼树构造以权值为叶子的哈夫曼树5267713第三步：从森林中去掉被合并的结点，并将新第三步：从森林中去掉被合并的结点，并将新合并的树加入到森林中，继续执行第

13、合并的树加入到森林中，继续执行第二步，直到森林合并成为一棵树二步，直到森林合并成为一棵树9例如例如: : 已知权值已知权值 W= 5, 6, 2, 9, 7 W= 5, 6, 2, 9, 7 构造以权值为叶子的哈夫曼树构造以权值为叶子的哈夫曼树526771316第三步：从森林中去掉被合并的结点，并将新第三步：从森林中去掉被合并的结点，并将新合并的树加入到森林中，继续执行第合并的树加入到森林中，继续执行第二步，直到森林合并成为一棵树二步，直到森林合并成为一棵树9例如例如: : 已知权值已知权值 W= 5, 6, 2, 9, 7 W= 5, 6, 2, 9, 7 构造以权值为叶子的哈夫曼树构造以权

14、值为叶子的哈夫曼树526771316第三步：从森林中去掉被合并的结点，并将新第三步：从森林中去掉被合并的结点，并将新合并的树加入到森林中，继续执行第合并的树加入到森林中，继续执行第二步，直到森林合并成为一棵树二步，直到森林合并成为一棵树9例如例如: : 已知权值已知权值 W= 5, 6, 2, 9, 7 W= 5, 6, 2, 9, 7 构造以权值为叶子的哈夫曼树构造以权值为叶子的哈夫曼树52677131629第三步：从森林中去掉被合并的结点，并将新第三步：从森林中去掉被合并的结点，并将新合并的树加入到森林中，继续执行第合并的树加入到森林中，继续执行第二步，直到森林合并成为一棵树二步，直到森林

15、合并成为一棵树构造完成构造完成设计电文编码时，设计电文编码时，随意的不等长编码可能导致编码翻译时出现歧义随意的不等长编码可能导致编码翻译时出现歧义使用前缀码，可解决不等长编码出现的歧义使用前缀码，可解决不等长编码出现的歧义利用哈夫曼树可构造前缀码利用哈夫曼树可构造前缀码构造方法：构造方法：1 1，将字符集中的每个字符作为节点，将字符集中的每个字符作为节点2 2，每个字符的出现频率作为节点的权值，每个字符的出现频率作为节点的权值3 3，构造哈夫曼树，构造哈夫曼树4 4，令哈夫曼树中的左分支为，令哈夫曼树中的左分支为0 0，右分支为，右分支为1 1 从根到叶子节点的从根到叶子节点的0101序列即为

16、叶子节点的编码序列即为叶子节点的编码假定：假定：某电文通信中只由某电文通信中只由ABCDABCD四个字符构成四个字符构成且出现频率分别为：且出现频率分别为：A 5% B 10% C 15% D 70%A 5% B 10% C 15% D 70%0.050.10.150.7假定：假定：某电文通信中只由某电文通信中只由ABCDABCD四个字符构成四个字符构成且出现频率分别为：且出现频率分别为：A 5% B 10% C 15% D 70%A 5% B 10% C 15% D 70%0.050.10.150.70.15假定：假定：某电文通信中只由某电文通信中只由ABCDABCD四个字符构成四个字符构成

17、且出现频率分别为：且出现频率分别为：A 5% B 10% C 15% D 70%A 5% B 10% C 15% D 70%0.050.10.150.70.150.3假定：假定：某电文通信中只由某电文通信中只由ABCDABCD四个字符构成四个字符构成且出现频率分别为：且出现频率分别为：A 5% B 10% C 15% D 70%A 5% B 10% C 15% D 70%0.050.10.150.70.150.31A AB BC CD D0 01 10 01 10 01 1A A的编码：的编码：000000B B的编码：的编码：001001C C的编码：的编码： 0101D D的编码：的编码：

18、 1 1电文：电文： D A B CD A B C编码：编码： 1 000 001 011 000 001 01每个字符的编码都不是每个字符的编码都不是另一字符编码的前缀另一字符编码的前缀n(nn(n0)0)个结点的树的高度个结点的树的高度: :最低是多少？最高是多少？最低是多少？最高是多少？ 答案：答案：1 1，n nABD答案：答案：一棵树应满足下列条件：一棵树应满足下列条件：（1 1）有且仅有一个结点没有前驱（双亲）有且仅有一个结点没有前驱（双亲）, ,称该结称该结点为树根点为树根; ;（2 2）除根结点以外）除根结点以外, ,其余每个结点有且仅有一个直其余每个结点有且仅有一个直接前驱接

19、前驱; ;（3 3）树中每个结点可以有多个直接后继）树中每个结点可以有多个直接后继( (孩子结点孩子结点) )。0.10.20.301练习：练习：假设有字符集假设有字符集AA，B B，C C，DD其在电文中的使用频率分别为其在电文中的使用频率分别为0.10.1，0.40.4，0.30.3，0.20.2请给出该字符集中每个字符的哈夫曼编码请给出该字符集中每个字符的哈夫曼编码并将并将AABCDDAABCDD电文翻译为哈夫曼编码电文翻译为哈夫曼编码0.30.6010.4101ADCB编码：编码：A 100B 0C 11D 101AABBCDD翻译：翻译：100001110110120092009年年

20、1010月考题：月考题：2727、由字符集、由字符集ss，t t，a a，e e，II及其在电文中出现的及其在电文中出现的频度构建的哈夫曼树如图所示。已知某段电文的哈夫频度构建的哈夫曼树如图所示。已知某段电文的哈夫曼编码为曼编码为111000010100111000010100，请根据该哈夫曼树进行译码，请根据该哈夫曼树进行译码，写出原来的电文。写出原来的电文。 二叉树的性质及应用二叉树的性质及应用ABCDEFHMABCACB123456789 10 11 12 13 14 15证明：二叉树的结点个数为：证明：二叉树的结点个数为：1 + 2 + 1 + 2 + + 2 + 2k-1k-1= 2

21、= 2k k-1-1123456789 10 11 12 13 14 15证明：设证明：设n1n1为为T T中度为中度为1 1的结点数，则总结点数：的结点数，则总结点数：n = n0 + n1 + n2 (1)n = n0 + n1 + n2 (1) 另：根据各个结点的前驱和后继情况另：根据各个结点的前驱和后继情况分支条数分支条数 = n - 1= n - 1分支条数分支条数 = n1 + 2 = n1 + 2 * * n2 (2) n2 (2)由由(1)(1)和和(2)(2)有：有：n1 + 2 n1 + 2 * * n2 = n0 + n1 + n2 - 1 n2 = n0 + n1 +

22、n2 - 1故故 n0 = n2 + 1;n0 = n2 + 1;w考虑到有序性，任一结点在树中都有确切的位置，考虑到有序性，任一结点在树中都有确切的位置，因此可以对满二叉树进行编号。编号方式为：从上因此可以对满二叉树进行编号。编号方式为：从上到下，从左到右。到下，从左到右。123456789 10 11 12 13 14 15abcdefghij证明：假设证明：假设n n个结点的完全二叉树的深度为个结点的完全二叉树的深度为k k，则，则n n的值的值应大于深度为应大于深度为k-1k-1的满二叉树的结点数的满二叉树的结点数2 2k-1k-1-1-1，小于等，小于等于深度为于深度为k k的满二叉

23、树的结点数的满二叉树的结点数2 2k k-1-1，即，即 2 2k-1k-1-1n2-1n2k k-1 -1 进一步可推导出进一步可推导出 2 2k-1 k-1 n2n2k k两边取对数后，有两边取对数后，有 k-1 k-1 loglog2 2(n) k(n) k进一步可推导出进一步可推导出 log2(n) k log2(n) +1log2(n) lchild ); Preorder( r-rchild ); AECBGL中（根）序的遍历算法：中（根）序的遍历算法：void Inorder ( bitreptr r ) / 中序遍历二叉树中序遍历二叉树 if ( r ！=NULL ) Inor

24、der( r-lchild ); visit ( r ); Inorder( r-rchild ); AECBGL后（根）序的遍历算法：后（根）序的遍历算法：void Postorder ( bitreptr r ) / 后序遍历二叉树后序遍历二叉树 if ( r ！=NULL ) Postorder( r-lchild ); Postorder( r-rchild ); visit ( r ); AECBGL二叉树的遍历算法：二叉树的遍历算法：AECBGLD DL LR RLDRLDR、LRDLRD、DLRDLRABCDEF前序序列：前序序列：abcdefabcdef中序序列：中序序列：cb

25、efdacbefda后序序列：后序序列：cfedbacfedbaA.LRNB.NRLC.RLND.RNL答案：答案：D答案答案1）不含左子树的二叉树）不含左子树的二叉树2）不含右子树的二叉树）不含右子树的二叉树3）空二叉树或只含根结点的二叉树）空二叉树或只含根结点的二叉树先序：根左右先序：根左右后序：左右根后序：左右根答案：答案：BABCDEFGHK例如例如: :先序序列先序序列: : A B C D E F G H K中序序列中序序列: : B D C A H G K F E后序序列后序序列: : D C B H K G F E A一、何谓线索二叉树？一、何谓线索二叉树？遍历二叉树的结果是，

26、求得结点的一个线性序列遍历二叉树的结果是，求得结点的一个线性序列ADEBCF rootABDCEF缺点：空指针较多，找某个序列缺点：空指针较多，找某个序列的前序后继不方便的前序后继不方便指向某遍历序列中的指向某遍历序列中的“前驱前驱”和和“后继后继” 的指针，的指针， 称作称作“线索线索”包含包含 “线索线索” 的存储结构，称作的存储结构，称作 “线索链表线索链表”与其相应的二叉树，称作与其相应的二叉树，称作 “线索二叉树线索二叉树”利用链表中空的左指针指向遍历序列的前驱利用链表中空的左指针指向遍历序列的前驱利用链表中空的右指针指向遍历序列的后继利用链表中空的右指针指向遍历序列的后继对线索链表

27、中结点的约定：对线索链表中结点的约定： 在二叉链表的结点中增加两个标志域，在二叉链表的结点中增加两个标志域，标志二叉树中的左右指针指向的是前驱还是后继标志二叉树中的左右指针指向的是前驱还是后继Tag Tag 值为值为1 1表示存的是线索表示存的是线索 值为值为0 0表示存的是孩子表示存的是孩子Tag Tag 值为值为1 1表示存的是线索表示存的是线索 值为值为0 0表示存的是孩子表示存的是孩子中序线索中序线索Tag Tag 值为值为1 1表示存的是线索表示存的是线索 值为值为0 0表示存的是孩子表示存的是孩子中序线索中序线索typedef struct BiThrNodtypedef stru

28、ct BiThrNod TElemType TElemType data; data; struct BiThrNode struct BiThrNode * *lchild, lchild, * *rchildrchild; ; PointerThr LTag, RTag PointerThr LTag, RTag; ; BiThrNode, BiThrNode, * *BiThrTreeBiThrTree; ;线索链表的类型线索链表的类型typedef enum Link, Thread PointerThrtypedef enum Link, Thread PointerThr; ;LinkLink值为值为0:0:指针，指针， ThreadThread值为值为1:1:线索线索二、线索链表的遍历算法二、线索链表的遍历算法:中序线索中序线索由于在线索链表中添加了遍历中得到的由于在线索链表中添加了遍历中得到的“前前驱驱”和和“后继后继”的信息，从而简化了遍历的的信息，从而简化了遍历的算法。算法。中序线索化链表的遍历算法中序线索化链表的遍历算法 中序遍历的第一个结点中序遍历的第一个结点