数据结构张华娣师树与二叉树PPT课件

1、 6.4.3树和森林的遍历 6.5 赫夫曼树及其应用 6.5.1 最优二叉树（赫夫曼树） 6.5.2 赫夫曼编码学习纲要第1页/共147页ACGBDE FK LHMIJ 非线性结构 该结构中至少存在一个数据元素，有两个或两个以上的直接前驱或直接后继.如： 树型结构、图型结构 树型结构是一类重要的非线性结构。 是结点之间有分支，并且具有层次关系的结构。（直观来看） 树型结构的逻辑特征 树中任一结点都可以有零个或多个后继结点，但至多只能有一个前趋结点，只有根结点无前趋，叶子结点无后继。 最为常用的树型结构 树 二叉树6.1 树的定义和基本术语第2页/共147页6.1 树的基本概念及相关术语 一、树

2、的定义 定义：树(Tree)是n(n=0)个结点的有限集T，n=0时称为空树，否则对任意一棵非空树，它满足如下两个条件：6.1 树的定义和基本术语ACGBDE FKLHMIJ（1）有且仅有一个特定的称为根(Root)的结点； (2)其余的结点可分为m(m0)个互不相交的子集T1,T2,T3Tm，其中每个子集又是一棵树，并称其为根的子树(Subtree)。树的定义是采用递归方法第3页/共147页6.1 树的定义和基本术语(a) 一棵树结构 (b)一个非树结构 (c)一个非树结构 一、树的定义ACBGFEDHIACBGFDACBGFDE第4页/共147页6.1 树的定义和基本术语树的应用举例文件结

3、构My ComputerC:D:E:etcWINDOWSProgram FilesPictureMusic第5页/共147页6.1 树的定义和基本术语ACGBDEFKLHMIJ二、树的特点第6页/共147页6.1 树的定义和基本术语三、树的基本术语结点：包含一个数据元素及若干指向其子树的分支结点的度：结点所拥有的子树的个数。树的度：树中各结点度的最大值。CGBDEFKLHMIJA第7页/共147页6.1 树的定义和基本术语三、树的基本术语叶子结点：度为0的结点，也称为终端结点。分支结点：度不为0的结点，也称为非终端结点。CGBDEFKLHMIJA第8页/共147页6.1 树的定义和基本术语三、

4、树的基本术语孩子、双亲：树中某结点子树的根结点称为这个结点的孩子结点，这个结点称为它孩子结点的双亲结点；兄弟：具有同一个双亲的孩子结点互称为兄弟。 CGBDEFKLHMIJA第9页/共147页6.1 树的定义和基本术语三、树的基本术语路径：如果树的结点序列n1, n2, , nk有如下关系：结点ni是ni+1的双亲（1=i=0)个结点的有限集合，此集合或者为空集（n=0），或者由一个根结点及两棵互不相交的左右子树组成，并且左右子树都是二叉树。123485679 10第19页/共147页6.2 6.2 二叉树二叉树 二、二叉树的特点 1.每个结点至多只有二棵子树（即二叉树中不存在度大于2的结点)

5、; 2.该两棵子树可以为空; 3.该两棵子树有次序之分，分别称之为左子树和右子树,其次序不能任意颠倒。123485679 10ABAB第20页/共147页6.2 6.2 二叉树二叉树 (a)空二叉树空二叉树 (b)仅有根结仅有根结点的二叉点的二叉树树 (c)右子树为右子树为空的二叉空的二叉树树L (d)左子树为空的二叉树R (e)左、右子树均非左、右子树均非空的二叉树空的二叉树LR三、二叉树的基本形态第21页/共147页6.2 6.2 二叉树二叉树a ab bc cd de e(a)a ac cd de eb b(b)b bc cd de ea a(c)四、二叉树与树和有序树的区别第22页/共

6、147页a ac cd de eb b(b)6.2 6.2 二叉树二叉树二叉树与树的区别：A树中结点的最大度数没有限制，二叉树结点最大度数为2。B树的每个结点的子树无左、右之分，二叉树的结点子树有明确的左、右之分。二叉树与有序树的区别：C.在有序树中，某个结点只有一个孩子时就无左、右之分 特别要注意：二叉树不是树的特殊情况，它们是两种不同的树型结构。四、二叉树与树和有序树的区别a ab bc cd de e(a)第23页/共147页练习：画出含有3个结点（非空）的树与二叉树的所有不同形态 树 二叉树第24页/共147页6.2 二叉树特殊的二叉树斜树1 . .所有结点都只有左子树的二叉树称为左斜

7、树2 . .所有结点都只有右子树的二叉树称为右斜树3.3.左斜树和右斜树统称为斜树。1. 在斜树中，每一层只有一个结点；2. .斜树的结点个数与其深度相同。 斜树的特点：ABCABC第25页/共147页满二叉树：在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子结点都在同一层上，这样的二叉树称为满二叉树。 特点：6.2 二叉树123485679 1011 1213 1415特殊的二叉树特殊的二叉树1. 叶子只能出现在最下一层；叶子只能出现在最下一层；2. 只有度为只有度为0和度为和度为2的结点。的结点。第26页/共147页6.2 二叉树特殊的二叉树特殊的二叉树不是满二叉树，虽然

8、不是满二叉树，虽然所有分支结点都有左所有分支结点都有左右子树，但叶子不在右子树，但叶子不在同一层上。同一层上。满二叉树在同样深度的二叉树中结点个数最多满二叉树在同样深度的二叉树中叶子结点个数最多A1523467BCDEFGLM89第27页/共147页6.2 二叉树 -深度为k的，有n个结点的二叉树，当且仅当每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称为完全二叉树（也称为近似满二叉树） 完全二叉树123485679 10特点：（1 1）叶子结点只可能在层次最大的两层上出现 （2 2）对任一结点，若其右分支下的子孙最大层次为L L，则其左分支下的子孙最大层次必为L L或L+1

9、L+1特殊的二叉树特殊的二叉树123485679 10 111213 1415第28页/共147页12345612345721367(a)完全二叉树(b)非完全二叉树( c)非完全二叉树满二叉树是完全二叉树的特例。满二叉树是完全二叉树的特例。6.2 二叉树特殊的二叉树特殊的二叉树第29页/共147页由此可得出如下结论：对一棵完全二叉树，有：1.至多只有最下面两层上结点的度数可以小于22.最下面一层结点都集中在该层的最左边3.满二叉树是完全二叉树，反之不然，在完全二叉树中，若某个结点没有左孩子，则它一定没有右孩子，即该结点必是叶结点。123485679 106.2 二叉树特殊的二叉树特殊的二叉树

10、第30页/共147页第31页/共147页6.2.2 6.2.2 二叉树的性质二叉树的性质 性质1： 在二叉树的第i层上至多有2i-1个结点(i=1)。第三层上(i=3)(i=3)，有2 23-13-1=4=4个结点。第四层上(i=4)(i=4)，有2 24-14-1=8=8个结点。第32页/共147页6.2.2 6.2.2 二叉树的性质二叉树的性质 性质2：深度为k的二叉树至多有2k1个结点（k=1)）.第33页/共147页6.2.2 6.2.2 二叉树的性质二叉树的性质性质3： 对任何一棵二叉树，如果其终端结点数为n0，度为2的结点数为n2，则n0n21。第34页/共147页6.2.2 6.

11、2.2 二叉树的性质二叉树的性质 性质4：具有n个结点的完全二叉树的深度为 符号 表示不大于x的最大整数。1log2n x123485679 10413110log2K完全二叉树的两个重要特性第35页/共147页6.2.2 6.2.2 二叉树的性质二叉树的性质 性质5： 如果对一棵有n个结点的完全二叉树的结点按层次编号,则对编号为i的结点（1=i1，则其双亲是结点。 （2）如果2in，则结点i为叶子结点，无左孩子； 否则，其左孩子是结点。 （3）如果2i1n， 则结点i无右孩子 否则，其右孩子是结点。123485679 10完全二叉树的两个重要特性性质5表明，在完全二叉树中，结点的层序编号反映

12、了结点之间的逻辑关系。第36页/共147页6.2.2 6.2.2 二叉树的性质二叉树的性质 i/2ii+12i2i+12(i+1)2i+3i+12(i+1)2i+3i2i2i+1完全二叉树中结点i和i+1(a)i和i+1结点在同一层 (b)i和i+1结点不在同一层如图所示为完全二叉树上结点及其左右子如图所示为完全二叉树上结点及其左右子树在结点之间的关系。树在结点之间的关系。第37页/共147页6.2.2 6.2.2 二叉树的性质二叉树的性质 在此过程中，可以从（2）和（3）推出（1），所以先证明（2）和（3）。 对于i1，由完全二叉树的定义，其左孩子是结点2，若2n，即不存在结点2，此是，结点

13、i无孩子。结点i的右孩子也只能是结点3，若结点3不存在，即3n，此时结点i无右孩子。 对于i1，可分为两种情况： （1）设第j（1=jn，则无左孩子：第38页/共147页6.2.2 6.2.2 二叉树的性质二叉树的性质 其右孩子必定为第j1层的第二个结点，编号为2i1。若2i+1n，则无右孩子。 （2）假设第j（1=j=log2n)层上的某个结点编号为i（2j-1=i= 2j -1),且2i11时，如果i为左孩子，即2（i/2)=i,则i/2是i的双亲；如果i为右孩子，i2p+1,i的双亲应为p，p（i1）/2=i/2. 证毕。第39页/共147页6.2.3 二叉树的存储结构顺序存储结构二叉树

14、的顺序存储结构就是用一组连续的存储单元存储二叉树中的结点，并且结点的存储位置（下标）应能体现结点之间的逻辑关系 如何利用数组下标来反映结点之间的逻辑关系? ?完全二叉树和满二叉树中结点的序号可以惟一地反映出结点之间的逻辑关系 。二叉树的逻辑关系父子关系。 第40页/共147页6.2.3 二叉树的存储结构 A B C D E F G H I J数组下标 1 2 3 4 5 6 7 8 9 10完全二叉树的顺序存储CDEFGHIJ以编号为下标第41页/共147页6.2.3 二叉树的存储结构二叉树的顺序存储ABC DE F G数组下标 1 2 3 4 5 6 7 8 9 1

15、0 11 12 13ABCDEGF以编号为下标ABCDEGF123561013按照完全二叉树编号第42页/共147页6.2.3 二叉树的存储结构一棵斜树的顺序存储会怎样呢？深度为k的右斜树，k个结点需分配2k1个存储单元。 一棵二叉树改造后成完全二叉树形态，需增加很多空结点，造成存储空间的浪费。二叉树的顺序存储结构一般仅存储完全二叉树ABC137D15第43页/共147页6.2.3 二叉树的存储结构二叉链表基本思想：令二叉树的每个结点对应一个链表结点，链表结点除了存放与二叉树结点有关的数据信息外，还要设置指示左右孩子的指针。 第44页/共147页二叉树的链表表示lChild data rChi

16、lddatalChildrChild每个结点由数据域、左指针域和右指针域组成。二叉链表其中，data：数据域，存放该结点的数据信息； lchild：左指针域，存放指向左孩子的指针； rchild：右指针域，存放指向右孩子的指针。 结点结构第45页/共147页6.2.3 二叉树的存储结构GFEDBAABCDEFGC二叉链表具有n个结点的二叉链表中，有多少个空指针？n+1个第46页/共147页6.2.3 二叉树的存储结构ABCDEFGGFEDBAC在二叉链表中，如何求某结点的双亲？二叉链表第47页/共147页6.2.3 二叉树的存储结构leftChild data parent rightChil

17、dparentdataleftChildrightChild三叉链表三叉链表 在二叉链表的基础上增加了一个指向双亲的指针域。第48页/共147页6.2.3 二叉树的存储结构ABCDEFGABDEFCG三叉链表第49页/共147页6.2.3 二叉树的存储结构 在二叉链表这种存储结构上，二叉树的多数基本运算如求根、求左、右孩子等很容易实现。但求双亲运算的实现比较麻烦，而且其时间性能较低 空间利用不高，在含有n个结点的二叉链表中有n+1个空链域， 三叉链表 优点： 求双亲运算很容易实现，且时间性能很好二叉链表与三叉链表的比较第50页/共147页6.2.3 二叉树的存储结构typedef struct

18、 BiTNode /树结点定义 ElemType data; /结点数据域 struct BiTNode *lChild, *rChild; /左右孩子指针左右孩子指针 BiTNode ,*BiTree;datalChildrChild第51页/共147页二叉树存储结构课堂练习 练习 分别画出下图所示二叉树的二叉链表、三叉链表和顺序存储结构示意图ABECFD第52页/共147页6.3 遍历二叉树和线索二叉树 6.3.1遍历二叉树 二叉树的遍历是指从根结点出发，按照某种次序访问二叉树中的所有结点，使得每个结点被访问一次且仅被访问一次。二叉树遍历操作的结果？非线性结构线性化抽象操作，可以是对结点进

19、行的各种处理，这里简化为输出结点的数据。第53页/共147页6.3.16.3.1遍历二叉树遍历二叉树6.3 6.3 遍历二叉树和线索二叉树遍历二叉树和线索二叉树(右子树)(根结点)(左子树)DLR考虑二叉树的组成：二叉树的遍历方式：DLR、LDR、LRD、DRL、RDL、RLD 如果限定先左后右，则二叉树遍历方式有三种：先序：DLR中序：LDR后序：LRD层序遍历：按二叉树的层序编号的次序访问各结点。 第54页/共147页6.3.1遍历二叉树- -/ /+ +* *abcdef.（前缀表示波兰式）先序遍历 (Preorder Traversal)(Preorder Traversal)第55页

20、/共147页6.3.1遍历二叉树void PreOrder (BiTNode *T) if (T = = NULL) return error; /递归调用的结束条件 visit (T-data); PreOrder (T-lChild); PreOrder (T-rChild);二叉树递归的先序遍历算法第56页/共147页6.3.1遍历二叉树- -/ /+ +* *abcdef.（中缀表示）中序遍历 (Inorder Traversal)第57页/共147页6.3.1遍历二叉树void InOrder (BiTNode *T) if (T != NULL) InOrder (T-lChild

21、); visit (T-data); InOrder (T-rChild); 第58页/共147页6.3.1遍历二叉树.(后缀表示逆波兰式)后序遍历 (Postorder Traversal)- -/ /+ +* *abcdef第59页/共147页6.3.1遍历二叉树void PostOrder (BiTNode *T) if (T != NULL) PostOrder (T-lChild); PostOrder (T-rChild); visit (T-data); 二叉树递归的后序遍历算法第60页/共147页AB1111111112222222223333先序序列：A B D E A B

22、D E H I C F GH I C F G中序序列：D B D B H E I A F C GH E I A F C G后序序列：D H D H I E B F G C AI E B F G C A333336.3.1遍历二叉树第61页/共147页6.3.1遍历二叉树BEAFDCGHIJBEAFDCGHIJ先序序列：A B C D A B C D E F G H I JE F G H I J中序序列：B C D B C D A F E H J I GA F E H J I G后序序列：D C B D C B F J I H G E A F J I H G E A 课堂练习二第62页/共147

23、页6.3.1遍历二叉树层序遍历二叉树的层次遍历是指从二叉树的第一层（即根结点）开始，从上至下逐层遍历，在同一层中，则按从左到右的顺序对结点逐个访问。 - -/ /+ +* *abcdef遍历结果：- + / a * e f b c d第63页/共147页6.3.1遍历二叉树若已知一棵二叉树的先序（或中序，或后序，或层序）序列，能否惟一确定这棵二叉树呢？遍历的性质性质1 1、由一棵二叉树的先序序列和中序序列可惟一确定这棵二叉树性质2 2、由一棵二叉树的后序序列和中序序列可惟一确定这棵二叉树由遍历序列恢复二叉树第64页/共147页6.3.1遍历二叉树例如，已知一棵二叉树的中序序列和后序序列分别为B

24、DCEAFHG和DECBHGFA，试画出这棵二叉树。BDCEFHGAFHGABDCE由遍历序列恢复二叉树第65页/共147页FHGABDCEFABECDGHFHGABCDEHGABCDEF由遍历序列恢复二叉树中序序列BDCEAFHG 后序序列DECBHGFA6.3.1遍历二叉树第66页/共147页6.3.1遍历二叉树练习三第67页/共147页6.3.1遍历二叉树HBDFEKCGAEKCGABHDF第68页/共147页6.3.1遍历二叉树KCGEKCGABHDFEKCGABHFDEABHFDEABHFDCKG 第69页/共147页6.3.1遍历二叉树int Height (BiTNode *T)

25、 if (T = NULL) return 0 0; else int m = Height (T-lChild); int n = Height (T-rChild); return (m n) ? m+1 : n+1; 第70页/共147页Status CreateBiTree(BiTree &T)Status CreateBiTree(BiTree &T)/建立一棵二叉树建立一棵二叉树 scanf(&ch); scanf(&ch); /依次输入字符，空格字符表示空树依次输入字符，空格字符表示空树 if(ch=) T=NULL;if(ch=) T=NULL;

26、 else else if(!(T=(BiTNode if(!(T=(BiTNode * *)malloc(sizeof(BiTNode) )malloc(sizeof(BiTNode) exit(OVERFLOW); exit(OVERFLOW); T Tdata=ch; data=ch; /生成根结点生成根结点 CreateBiTree(TCreateBiTree(Tlchild); lchild); /构造左子树构造左子树 CreateBiTree(TCreateBiTree(Trchildd); rchildd); /构造右子树构造右子树 return OK; return OK; 例

27、二：构建一棵二叉树（使用先序遍历）6.3.1遍历二叉树第71页/共147页AB1111111112222222223333先序序列：A B D E A B D E H I C F GH I C F G中序序列：D B D B H E I A F C GH E I A F C G后序序列：D H D H I E B F G C AI E B F G C A333336.3.2二叉树遍历的非递归实现第72页/共147页6.3.2二叉树遍历的非递归实现先序遍历的定义：1）访问根结点2）先序遍历左子树3）先序遍历右子树(右子树)(根结点)(左子树)vLRXTPre(T)Pre(t-lchild)Pre

28、(t-rchild). .XLXR(a)(b)第73页/共147页6.3.26.3.2二叉树遍历的非递归实现abcde先序遍历的定义：1）访问根结点2）先序遍历左子树3）先序遍历右子树cdcc访问访问a进栈进栈c左进左进b访问访问b进栈进栈d左进左进空空退栈退栈d访问访问d左进左进空空退栈退栈c访问访问c左进左进e访问访问e左进左进空空退栈退栈 结束结束第74页/共147页6.3.2二叉树遍历的非递归实现void PreOrder(BiTree T) stack S; InitStack(&S); /递归工作栈 BiTNode * p = T; Push (&S, NULL);

29、 while (p != NULL) visit(p-data); if (p-rChild != NULL) Push(&S, p-rChild); if (p-lChild != NULL) p = p-lChild; /进左子树 else Pop(&S, p-rChild); /左子树空, 进右子树 第75页/共147页6.3.2二叉树遍历的非递归实现abcdebaadaa左空左空退栈退栈访问访问左空左空 退栈退栈访问访问退栈退栈访问访问左空左空ec退栈访问退栈访问cc右空右空退栈访问退栈访问 栈空结束栈空结束中序遍历的定义：1）中序遍历左子树2）访问根结点3）中序遍历右

30、子树第76页/共147页6.3.2二叉树遍历的非递归实现void InOrder(BiTree T) stack S; InitStack(S); /递归工作栈 BiTNode *p = T; /初始化 while (p | !StackEmpty(S) if (p) Push(S, p); p = p-lChild; /根指针进栈，根指针进栈，遍历左子树遍历左子树 else Pop(S, p); /退栈 visit(p-data); /访问根结点 p = p-rChild; /遍历右子树 第77页/共147页6.3.2二叉树遍历的非递归实现 思考：后序遍历的非递归算法第78页/共147页6.

31、3.2 线索二叉树如何保存二叉树的某种遍历序列？ 将二叉链表中的空指针域指向其前驱结点和后继结点 当以二叉链表作为存储结构时, ,只能找到结点的左右孩子的信息, ,而不能找到结点的任一序列的前驱与后继信息, ,这种信息只有在遍历的动态过程中才能得到。第79页/共147页6.3.2 线索二叉树线索：将二叉链表中的空指针域指向前驱结点和后继结点的指针被称为线索；线索化：使二叉链表中结点的空链域存放其前驱或后继信息的过程称为线索化；加上线索的二叉链表称为线索链表线索二叉树：加上线索的二叉树称为线索二叉树。第80页/共147页6.3.2 线索二叉树 ltag lchild data child rta

32、g0: lchild指向该结点的左孩子1: lchild指向该结点的前驱结点0: rchild指向该结点的右孩子1: rchild指向该结点的后继结点ltag=rtag=结点结构线索链表第81页/共147页例如下图（a）是一棵中序线索二叉树，它的线索链表如图 (b)所示。 （a）n注：不同的遍历次序注：不同的遍历次序其得到的线索二叉树其得到的线索二叉树也不同也不同( (可分别称为可分别称为先序线索二叉树、中先序线索二叉树、中序线索二叉树和后序序线索二叉树和后序线索二叉树线索二叉树) )6.3.2 线索二叉树第82页/共147页线索链表preprep(b)6.3.2 线索二叉树第83页/共147

33、页如何在线索二叉树中找结点的前驱和后继结点？： 1）树中所有叶结点的左链是线索，因此叶结点的左链域直接指向其前驱结点。 2）对于非终端结点，若该结点无左孩子，则其左链域为线索，直接指向其前驱结点。若有左孩子，则该结点的前驱为中序遍历其左子树时最后访问的那个结点，即左子树中最右下的结点为其前驱结点。 1）树中所有叶结点的右链是线索，因此叶结点的右链域直接指示该结点的后继结点。 2）非终端结点若无右孩子，则其右链是线索，指向后继，若有右孩子，则其后继是中序遍历其右子树时访问的第一个结点，即右子树中最左下结点 。6.3.2 线索二叉树第84页/共147页线索链表preprepT T6.3.2 线索二

34、叉树第85页/共147页如何进行二叉树的线索化呢？ 线索化的实质是将二叉链表中的空指针改为指向结点前驱或后继的线索，而一个结点的前驱和后继的信息只有在遍历时才能得到，因此线索化过程即为在遍历的过程中修改空指针的过程。6.3.2 线索二叉树第86页/共147页6.4 树与森林实现树的存储结构，关键是什么? ?树中结点之间的逻辑关系是什么? ?思考问题的出发点：如何表示结点的双亲和孩子如何表示树中结点之间的逻辑关系。6.4.1 6.4.1 树的存储结构父子关系第87页/共147页6.4.1 树的存储结构双亲表示法基本思想：用一组连续的存储空间（一维数组）存储树的各个结点（一般按层序存储），同时在每

35、个结点中附设一个指示器指示其双亲结点在数组中的位置。 data parentdata：存储树中结点的数据信息parent：存储该结点的双亲在数组中的下标结点结构： 第88页/共147页6.4.1 树的存储结构 #define MAXNODE typedef struct PTNode /结点结构 elemtype data; int parent; /双亲位置域 PTNode;PTNode tMAXNODE; data parent树的双亲表示法实质上是一个静态链表。双亲表示法第89页/共147页6.4.1 树的存储结构下标 data parent012345678 A - -1 B 0 C

36、0 D 1 E 1 F 1 G 2 H 2 I 4 双亲表示法ACBHFEDGI优点： 实现Parent（t，x）操作 和Root（x）操作很方便不足：求某结点的孩子结点，即实现Child（t，x，i）操作时，则需要查询整个数组。不能反映各兄弟结点之间的关系，所以实现RightSibling（t，x）操作也比较困难。第90页/共147页6.4.1 树的存储结构链表中的每个结点包括一个数据域和多个指针域，每个指针域指向该结点的一个孩子结点。 如何确定链表中的结点结构？ 方案一：指针域的个数等于树的度-同构data child1 child2 childd 其中：data：数据域，存放该结点的数据

37、信息； child1childd：指针域，指向该结点的孩子。 孩子链表表示法第91页/共147页6.4.1 树的存储结构缺点：浪费空间ACBHFEDGIABCDEFGHI 孩子链表表示法第92页/共147页6.4.1 树的存储结构链表中的每个结点包括一个数据域和多个指针域，每个指针域指向该结点的一个孩子结点。 如何确定链表中的结点结构？方案二： 指针域的个数等于该结点的度-异构 data degree child1 child2 childd其中：data：数据域，存放该结点的数据信息； degree：度域，存放该结点的度； child1childd：指针域，指向该结点的孩子孩子链表表示法第9

38、3页/共147页6.4.1 树的存储结构缺点：结点结构不一致，操作不方便ACBHFEDGIA 2B 3C 2E 1I 0G 0H 0F 0D 0孩子链表表示法第94页/共147页6.4.1 树的存储结构孩子链表表示法基本思想：把每个结点的孩子排列起来，看成是一个线性表，且以单链表存储，则n个结点共有 n 个孩子链表。这 n 个单链表共有 n 个头指针，这 n 个头指针又组成了一个线性表，为了便于进行查找采用顺序存储。最后，将存放 n 个头指针的数组和存放n个结点的数组结合起来，构成孩子链表的表头数组。 如何确定链表中的结点结构？将结点的所有孩子放在一起，构成线性表。第95页/共147页6.4.

39、1 树的存储结构孩子链表表示法ACBHFEDGI012345678下标 data firstchild A B C D E F G H I 12 345 7 68 child next孩子结点data firstchild表头结点第96页/共147页ACBHFEDGI6.4.1 树的存储结构双亲孩子表示法012345678 A - -1 B 0 C 0 D 1 E 1 F 1 G 2 H 2 I 4 data parent firstchild12 345 7 68 第97页/共147页6.4.1 树的存储结构孩子兄弟表示法(二叉链表表示法)ACBHFEDGI某结点的第一个孩子是惟一的某结点的

40、右兄弟是惟一的设置两个分别指向该结点的第一个孩子和右邻兄弟的指针 第98页/共147页6.4.1 树的存储结构类型描述如下：Typedef struct CSNode elemtype data; /结点信息 struct CSNode *firstchild, /指向第一个孩子结点的指针 *nextsibling; /指向下一个兄弟结点的指针 CSNode,*CSTree; /用指向树的根结点的指针来表示一棵树结点结构firstchild data nextsiblingdata：数据域，存储该结点的数据信息；firstchild：指针域，指向该结点第一个孩子；nextsibling：指针域

41、，指向该结点的右兄弟结点。 孩子兄弟表示法第99页/共147页6.4.1 树的存储结构孩子兄弟表示法ACBHFEDGI A B C D E F G H I第100页/共147页优缺点： 可以直接实现树的大部分操作，如找结点的孩子、兄弟等操作。但对树结点作Parent操作时需遍历树。如果要反复执行Parent操作， 则可为每个结点增设一个parent域，这样就能方便地实现parent(T,x)运算6.4.1 树的存储结构第101页/共147页6.4.1 树的存储结构画出下列树的孩子兄弟表示法的结构图(a)(c)树二叉树ABCDEFGA BCED F GAEBCFDG(b)练习第102页/共147

42、页 以二叉链表为媒介可导出树与二叉树之间的对应关系。将树转换为二叉树，这样，对树的操作就可以借助二叉树存储，利用二叉树上的操作来实现。6.4.2 树、森林与二叉树的转换第103页/共147页6.4.2 树、森林与二叉树的转换方法一：借助二叉链表，让该结点的左分枝指向该结点的第一个孩子，右分枝指向该结点的下一个兄弟。ABCDEFGAEBCFDG第104页/共147页 I A B C DE F G H(b) A B CDE G H FI(a)ABEFCDGHI(d)ABCDEFGHI(c)方法二： 在树中所有的兄弟结点之间加一连线； 对每个结点，除保留与其长子（最左孩子）的连线外，去除该结点与其它

43、孩子之间的联线； 以根结点为轴心，将整个树顺时针转4545度。6.4.2 树、森林与二叉树的转换第一步：在树中所有的兄弟结点之间加一连线第二步：对每个结点，除保留与其长子（最左孩子）的连线外，去除该结点与其它孩子之间的联线；第三步：以根结点为轴心，将整个树顺时针转45度。第105页/共147页6.4.2 树、森林与二叉树的转换 将下列的树转换为二叉树课堂练习第106页/共147页6.4.2 树、森林与二叉树的转换 将下列的树转换为二叉树DIABECFGH转换后的二叉树课堂练习第107页/共147页6.4.2 树、森林与二叉树的转换2. 森林转换为二叉树 森林转换为二叉树的方法： 逐个转换 将森

44、林中的每一棵树分别转换成二叉树； 加线 将各二叉树的根结点视为兄弟用线连起来； 层次调整 以第一棵树的根结点作为二叉树的根结点，按顺时针方向适当旋转。第108页/共147页ADCBEFHIGJEFADCBHIGJADCBEFHIGJADCBEFHIGJ6.4.2 树、森林与二叉树的转换将如图所示的森林转换为二叉树第109页/共147页ADCBEFHIGJ二、二叉树转换成树、森林二、二叉树转换成树、森林方法一方法一1.二叉树的根作为森林中第一棵树的根二叉树的根作为森林中第一棵树的根2.二叉树的左子树转换成森林中第一棵树的子树二叉树的左子树转换成森林中第一棵树的子树森林森林3.二叉树的右子树转换成

45、森林中其它的树二叉树的右子树转换成森林中其它的树6.4.2 树、森林与二叉树的转换第110页/共147页6.4.2 树、森林与二叉树的转换ADCBEFHIGJEFADCBHIGJADCBEFHIGJ二叉树转换为森林第111页/共147页方法二1）将结点的左孩子的右孩子、右孩子的右孩子与该结点连接起来2）去掉所有结点与其右孩子的连线EFADCBEFHIGJADCBHIGJ6.4.2 树、森林与二叉树的转换第112页/共147页将如图所示的森林转换为二叉树将如图所示的森林转换为二叉树GHIJLNKOMADCBFE6.4.2 树、森林与二叉树的转换课堂练习第113页/共147页将如图所示的森林转换为

46、二叉树将如图所示的森林转换为二叉树GHIJLNKOMADCBFEFADBECGHIJLKOMN6.4.2 树、森林与二叉树的转换第114页/共147页FADBECGHIJLKOMN最后转换成的二叉树最后转换成的二叉树第115页/共147页6.4.3 树与森林的遍历1、先序（根）遍历树-先访问树根结点n，然后从左到右，依次先序遍历根的每棵子树T1,T2,.,Tk 。2、后序（根）遍历树-先从左到右，依次对树的每棵子树T1,T2,.,Tk进行后序遍历，最后访问树根结点n。 设T以n为树根，树根的子树从左到右依次为T1,T2,.,Tk，那么有：第116页/共147页6.4.3 树与森林的遍历先根：A

47、 B E F C D G H I 后根：E F B C G H I D A 例如例如,右图树右图树 AEI B CD E G H FI树树ABFCDGH二叉树二叉树右图二叉树右图二叉树先序先序: A B E F C D G H I 中序：中序：E F B C G H I D A先根遍历树先根遍历树 先序遍历该树先序遍历该树对应的二叉树对应的二叉树后根遍历树后根遍历树 中序遍历该树中序遍历该树对应的二叉树对应的二叉树第117页/共147页6.4.3 树与森林的遍历按照树与森林相互递归定义，可推出森林的两种遍历方法：一、先序遍历森林 若森林非空，则可按下述规则遍历：1.访问森林中第一棵树的根结点;

48、2.先序遍历第一棵树中根结点的子树森林;3.先序遍历除去第一棵树之后剩余的树构成的森林。二、中序遍历森林 若森林非空，则可按下述规则遍历：1.中序遍历森林中第一棵树的根结点的子树森林;2.访问第一棵树的根结点;3.中序遍历除去第一棵树之后剩余的树构成的森林 第118页/共147页6.4.3 树与森林的遍历ADCBEFHIGJ先序遍历序列：先序遍历序列：A B C D E F G H J I中序遍历序列：中序遍历序列：B C D A F E J H I G先序遍历森林 先序遍历该森林对应的二叉树中序遍历森林 中序遍历该森林对应的二叉树ADCBEFHIGJ第119页/共147页6.4.3 树与森林

49、的遍历总 结 由上述讨论可知: 当用二叉链表作树和森林的存储结构时，树和森林的先根遍历（先序）和后根遍历（中序）可借助二叉树的先序遍历和中序遍历算法来实现第120页/共147页相关概念1.1.结点间的路径长度-从树中一个结点到另一个结点之间的分支数目6.5 赫夫曼树及其应用2.叶子结点的权值-对叶子结点赋予的一个有意义的数值。 3.3.结点带权的路径长度从该根结点到该结点之间的路径长度与该结点上权值的乘积。2347第121页/共147页6.5 赫夫曼树及其应用4.4.二叉树的带权路径长度（weighted path weighted path length of treelength of t

50、ree）-二叉树中所有叶子结点的带权路径长度之和。WPL= nkkklw1第k个叶子的权值；从根结点到第k个叶子的路径长度AB CD2347WPL=2*2+3*2+4*2+7*2=32第122页/共147页6.5 赫夫曼树及其应用5.赫夫曼树：给定一组具有确定权值的叶子结点，带权路径长度最小的二叉树。例：给定4个叶子结点，其权值分别为2，3，4，7，可以构造出形状不同的多个二叉树。 WPL=32 WPL=41 WPL=30234723477423第123页/共147页6.5 赫夫曼树及其应用赫夫曼树的特点：1. 权值越大的叶子结点越靠近根结点，而权值越小的叶子结点越远离根结点。 2. 只有度为

51、0（叶子结点）和度为2（分支结点）的结点，不存在度为1的结点. 2347WPL=32 WPL=41 WPL=3023477423第124页/共147页6.5 赫夫曼树及其应用赫夫曼算法基本思想：赫夫曼算法基本思想： 初始化初始化：由给定的：由给定的n n个权值个权值 w w1 1，w w2 2，w wn n 构构造造n n棵只有一个根结点的二叉树，从而得到一个棵只有一个根结点的二叉树，从而得到一个二叉树集合二叉树集合F F T T1 1，T T2 2，T Tn n ； 选取与合并选取与合并：在：在F F中选取根结点的权值中选取根结点的权值最小最小的的两棵二叉树分别作为左、右子树构造一棵新的两棵

52、二叉树分别作为左、右子树构造一棵新的二叉树，这棵新二叉树的根结点的权值为其左二叉树，这棵新二叉树的根结点的权值为其左、右子树根结点的权值之和；、右子树根结点的权值之和； 删除与加入删除与加入：在：在F F中删除作为左、右子树的两中删除作为左、右子树的两棵二叉树，并将新建立的二叉树加入到棵二叉树，并将新建立的二叉树加入到F F中；中； 重复重复、两步，当集合、两步，当集合F F中只剩下一棵二叉中只剩下一棵二叉树时，这棵二叉树便是赫夫曼树。树时，这棵二叉树便是赫夫曼树。 怎样构造一棵赫夫曼树呢？第125页/共147页第1步：初始化例：给定权值 W2，3，4，5 ，构造赫夫曼树3524第2步：选取与

53、合并32 5第3步：删除与加入5432 5赫夫曼树的构造过程6.5 赫夫曼树及其应用第126页/共147页W2，3，4，5 赫夫曼树的构造过程重复第2步5432 554 9重复第3步 554 9326.5 赫夫曼树及其应用第127页/共147页W2，3，4，5 赫夫曼树的构造过程重复第2步重复第3步 554 932 554 932146.5 赫夫曼树及其应用第128页/共147页6.5 赫夫曼树及其应用 给定权值7，18，3，32，5，26，12，8，构造相应的赫夫曼树,要求左子树根结点的权值尽可能地小于右子树根结点的权值。课堂练习第129页/共147页赫夫曼树的应用-判定树在解决某些判定问题

54、时，利用赫夫曼树可以得到最佳判定算法。例1 将学生百分成绩按分数段分级的程序。若学生成绩分布是均匀的，可用图（a)二叉树结构来实现。 a60 a70 a80 a90 不及格中等良好优秀及格YNYNYNYN(a)输入10000个数据，则需进行31500次比较。6.5 赫夫曼树及其应用第130页/共147页分数分数0596069707980899099比例比例0.050.150.40.30.10 70a 80 a60 及格中等良好 80a90 60a70 不及格优秀YNYYYNNN(b) 不及格Y a90 a80 a70 a60 优秀中等及格良好YNNN(c)YYY 学生成绩分布不是均匀的情况：以

55、比例数为权构造一棵赫夫曼树，如（b)判断树所示。再将每一比较框的两次比较改为一次，可得到（c)判定树。输入10000个数据，仅需进行22000次比较。6.5 赫夫曼树及其应用第131页/共147页赫夫曼树的应用-赫夫曼编码 利用赫夫曼树构造通讯中电文编码例如：要传输一个电文：CAS；CAT；SAT；AT;要传输的字符集是 D=C，A，S，T， ；每个字符出现的频率是W= 2，4， 2，3， 3 6.5 赫夫曼树及其应用等长编码等长编码：C(000)A(001)S(010)T(011);(100)000001010100000001011100010001011100001011 42位不等长编

56、码不等长编码：C(0)A(00)S(1)T(01);(10)000110000011010001100001 24位 无法翻译前缀编码：前缀编码：任一个字符的编码都不是另一个字符编码的前缀任一个字符的编码都不是另一个字符编码的前缀C(0)A(10)S(110)T(1110);(1111)0101101111010111011111101011101111101110 40位前缀码第132页/共147页6.5 赫夫曼树及其应用电文总长达到最短的前缀编码的方法-构造一棵赫夫曼树（1）用频率作为叶子结点的权值生成一棵赫夫曼树，并将对应权值wi的叶子结点注明对应的字符；（2）约定左分支表示字符“0”，

57、右分支表示字符1 则从根结点到每个叶结点所经过的路径分支组成的0和1的序列便为该结点对应字符的编码，我们称之为赫夫曼编码。求编码的过程：从叶子结点出发走一条从叶子到根的路径求译码的过程：从根出发走一条从根到叶子的路径怎样才能使总的串长达到最小呢？第133页/共147页例子：要传输的电文是CAS；CAT；SAT；AT要传输的字符集是 D=C，A，S，T， ；每个字符出现的频率是W= 2，4， 2，3， 3 各字符编码是 T ； A C S 00 01 10 110 111上述电文编码：（32位）1101011101110100001111100001100003342200111T;ACS106

58、14846.5 赫夫曼树及其应用第134页/共147页赫夫曼树的存储结构及其算法的实现1. 设置一个数组huffTree2n-1保存赫夫曼树中各点的信息，数组元素的结点结构 ：其存储结构为：Typedef struct float weight; int lchild,rchild,parent; hufmtree;hufmtree treem;/设patent域不仅是为了使涉及双亲的运算方便，其主要作用是区分根和非根结点，若parent的值为-1，则表示该结点是无双亲的根结点，否则非根结点。weightweightLchildLchildParentParentrchildrchild结点结构第135页/共147页6.5 赫夫曼树及其应用1. 数组huffTree初始化，所有元素结点的双亲、左、右孩子都置为- -1；2. 数组huffTree的前n个元素的权值置给定值wn；3. 进行n- -1次合并 3.1 在二叉树集合中选取两个权值最小的根结点，其下标分别为i1, i2； 3.2 将二叉树i1、i2合并为一棵新的二叉树k；在上述存储结构上实现hufmtreehufmtree算法的基本步骤：第136页/共1