数据结构第章数和二叉树

《数据结构第章数和二叉树》由会员分享，可在线阅读，更多相关《数据结构第章数和二叉树（116页珍藏版）》请在金锄头文库上搜索。

1、第一章 绪论第二章 线性表第三章 栈和队列第四章 串第五章 数组和广义表目目录1第六章第六章 树树和二叉和二叉树树第第 七七章章 第八章第八章 态态存管存管理理第九章第九章 找找第十章第十章 内部排序内部排序目目211、树、树的定和基本的定和基本3. 3. 遍二叉遍二叉树树和索二叉和索二叉树树4. 4. 数和森林数和森林2. 2. 二叉二叉树树定及存定及存5 5. . 哈夫曼数及其用哈夫曼数及其用3课前思考课前思考家族谱系图 ， ， ， ， ， ， ， 关系表示法46.16.1树的定义和基本术语树的定义和基本术语6.1树的定义和基本术语5概述树型结构是一类重要的树型结构是一类重要的非线性结构非

2、线性结构树是树是以分支关系定义的层次结构以分支关系定义的层次结构树的应用树的应用人类社会的族谱人类社会的族谱社会组织结构社会组织结构在编译程序中的语法树在编译程序中的语法树在数据库系统中，可用树来组织信息在数据库系统中，可用树来组织信息6树的定义树树是由是由n n（n0 ）个点个点成成的的 有有限集限集合合 A （b ）含含 有有根点的根点的树树A B C D I H G F E J K L M （c） 含含 有多有多个点的个点的树树 （a）空空 树树 T1T2T3若若 n=0n=0，称空称空树；树；有一有一个特定的称个特定的称根根（rootroot）的点的点。它只它只有有直接直接后后 ，但没

3、但没有有直接前直接前；递递定子定子树树7树基本操作（P119）：8树的基本术语A A B B C C D D II H H G G FF EE JJ KK LL MM 点点 ：包：包含含 一一个元素及若干个元素及若干指向指向其子其子树树的的 分分支支 ，大写字母表示大写字母表示度度 ：一：一个点个点包包含子含子树树的数目的数目，称点的度称点的度A:3,B:2,F:0A:3,B:2,F:0叶子叶子：度度 00的点的点，称叶子点称叶子点或树或树叶叶 ，也叫端点也叫端点(J,K,L)。9树的基本术语A B C D I H G F E J K L M 孩子点孩子点：若点若点X X有有子子 树，则树，则

4、子子 树树的根点的根点X X的孩子点的孩子点A:B,C,DA:B,C,D双点双点：若点若点A A有有子女子女B B，则，则A A B B的双点的双点。 祖先点祖先点：从根点到点所从根点到点所分分枝枝 上上的所的所有有点点的祖先点点的祖先，MM的祖先点的祖先点：H,D,AH,D,A10树的基本术语A B C D I H G F E J K L M 子点子点：某某 一一点的子女及子女的子女都点子点的子女及子女的子女都点子。A:C,G兄弟结点：具有同一个双亲的结点，称为兄弟结点。E，F 分分枝点枝点：除叶子点除叶子点外外的所的所有有点点 ， 分分枝点枝点，也叫非端点也叫非端点.C C11树的基本术语

5、A B C D I H G F E J K L M 数数 ：根点的数根点的数11，其它点的数从根点到点所的其它点的数从根点到点所的分分支数目再加支数目再加11。 树树的高度的高度（深度深度） ：树：树中点所中点所处处的的 最最大数称大数称树树的高度的高度。12有有序序 树树 若 一棵 树中所有子 树从左到右的排序是有序的，不能 倒次序。称 树有序 树。无序无序树树若 一棵 树中所有子 树的次序无关要，则称无序树。 森林森林（树（树林林 ） 若干棵互不相交的树成的集合森林。一棵 树可以看成是 一个特殊的森林。去 一棵非空树的根点，树就 成身森林；反之,若增加一个根点,森林中每一棵 树的根点都成它

6、的子女,森林就成一棵 树13树与线性结构的区别性构性构树树构构有有 ：存在唯存在唯一一的没的没有有前前 的的首元素首元素存在唯存在唯一一的没的没有有前的前的根点根点有有尾尾 ：存在唯存在唯一一的没的没有后有后的的尾元素尾元素存在存在多多个没个没有后有后的的叶子叶子有有前前 有后有后：其余元素均存在唯其余元素均存在唯一一的的前元素前元素和唯和唯一一的的 后后元素元素其余点均存在唯其余点均存在唯一一的的前前 (双双 )点点 和和 多多个个 后后 (孩子孩子)点点 14A AB BC CD DEEFFG GH HIIJJKKLLMM点点 A A的度的度：3 3点点 B B的度的度：2 2点点 MM的

7、度的度：00叶子叶子：KK，LL，FF，G G，MM，II，JJ点点 A A的孩子的孩子：B B，C C，D D点点 B B的孩子的孩子：EE，FF点点 II的双的双：D D点点 LL的双的双：EE点点 B B，C C，D D兄兄 弟弟点点 KK，LL兄兄 弟弟树树的度的度：3 3点点 A A的次的次：11点点 MM的次的次：44树树的深度的深度：44点点 FF，G G 堂堂兄兄 弟弟点点 A A是点是点FF，G G的祖先的祖先15练习1列出下图所示树的叶结点、分支结点和每个结点的层次。166.2 6.2 二叉树二叉树6.2 二叉树17二叉树什么是二叉树？什么是二叉树？每个点每个点最多有最多有

8、两个孩子两个孩子度度 =2=2有有序序 树（分树（分左右左右） (a) (b) L R (e) L (c) R (d)18一个典型的二叉树19练习试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。 20回顾 树的基本特点、基本术语A B C D E G H F 一个三层的二叉树最多有几个节点、最少有几个节点。21有一棵树的括号表示为A(B,C(E,F(G),D)，回答下面的问题：1、这棵树的根结点是多少2、这棵树的叶子结点是什么3、结点C的度是多少4、这棵树的度是多少5、这棵树的深度是多少6、结点C的孩子结点是哪些7、结点C的双亲结点是谁22若一棵度为4的树中度为1、2、3、4的结点

9、个数分别为4、3、2、2，则该树叶子结点的个数是多少？总结点个数是多少？23二叉树的性质1性性性性 1111在二叉在二叉树树的第的第 i i 上上至至 多有多有 2 2i-1i-1 个点个点(i1)。 A A B B C C D D EE G G H H FF 24二叉树的性质2性质性质2 2深度深度kk的二叉的二叉树树中至中至多多含含 有有 2 2kk-1-1 个点个点，(k1)。A B C D E G H F 25二叉树的性质3性质性质3 3任任 意一意一棵二叉棵二叉树，树，如果叶子点个数如果叶子点个数n n00，度度 2 2的点个数的点个数n n2 2，则有则有n n00=n=n2 2+

10、1+1。A B C D E G H F n=n0+n1+n2 1n=n1+2n2+1 2n0=n2+126两种特殊形态的二叉树A B C D E F G H I J K L M N O 特 点1.所有的分支结点的度数都为22.叶子结点都在同一层次上3.结点个数=2K-127两种特殊形态的二叉树A B C D E G H F A B C D E G H F A B C D E G H F 如果一棵具有n个结点的深度为k的二叉树，它的每一个结点都与深度为k的满二叉树中编号为1 n的结点一一对应，则称这棵二叉树为完全二叉树。特 点1.叶子结点只能在层次最大的两层出现2.对任一结点,若其右分支的子孙的

11、最大层次为L，则其左分支子孙的最大层必为L或L+128实例112 23 3445 5112 23 3445 5非完全二叉非完全二叉树树29二叉树的性质4性性性性 4444具具 有有n n个点的完全二叉个点的完全二叉树树高度高度 loglog2 2n n +1 +1 A B C D E G H F 3.33.3 =3 =3 3.33.3 =4=4根据性质2和完全二叉树性质：2k-1 1n 2k 1或 2k-1 n 2k k-1 log2n 1，则其双亲结点 parent(i) 的编号是 i/2i/2 。如果 2in，则编号 i 的点无左孩子（编号 i 的点叶子点）；否 则其左孩子点 lChild

12、(i) 的 编号是 2i 。(3) 如果 2i+1n，则编号 i 的点无右孩子；否 则其右孩子点 rChild(i) 的 编号是点 2i+1，左孩子 2i31i2i2i+132练习1、具有100个结点的完全二叉树的深度为(从1层开始计数)( ) A.6 B.5 C.4 D.72、二叉树第i（i=1）层上至多有（ ）结点。 A. 2i B. 2i C. 2i-1 D. 2i-1 3、将一棵有50个结点的完全二叉树按层编号(从1开始)，则对编号为25的结点x，该结点（ ）A.无左、右孩子 B.有左孩子，无右孩子C.有右孩子，无左孩子 D.有左、右孩子 33回顾 二叉树的5个性质1.某一层上的最大结

13、点数为：2.K深度的二叉树最多结点数为：3.n0=n2+14.n结点完全二叉树深度：5.n结点完全二叉树任一结点i有：2i-12k-1 log2n +1双亲双亲 i/2 左孩子左孩子2i 2i右孩子右孩子 2i+12i+1344. 二叉树的存储结构顺序存储结构链式存储结构 二叉链表 三叉链表 线索链表35二叉树的顺序存储结构/二叉二叉树树的序存表示的序存表示#define MAX_TREE_SIZE 100 #define MAX_TREE_SIZE 100 typedeftypedef TElemTypeTElemType SqBiTreeSqBiTree MAX_TREE_SIZEMAX_

14、TREE_SIZE；/0/0号元存根点号元存根点SqBiTreeSqBiTree btbt；36完全二叉树的数组表示表示方法：对完全二叉树所有得结点按照层次次序自顶向下，同一层次自左向右顺序编号1,2 ,n,得到一线性序列，并把此序列放入到一维数组中。这种方法可以很容易的找到一个结点的双亲、兄弟、子女（性质5）。比如结点C37一般二叉树的树组表示若该二叉树为非完全二叉树，则必须将相应位置空出来，使存放的结果符合完全二叉树形状。如图给出了顺序存贮形式。38ABCDE再比如左图所示：共5个结点（0,2,6,14,30），但却占用了至少31个存储空间。39设二叉树的顺序存储结构如下： 11 2 23

15、 3445 56 677 8899 11001111112 2113 31144115 5116 61177118811992 200EEA AFF D D H H C C G GII B B根据其存构，画出二叉树。40二叉树的存储结构链式存储结构适用范围：一般的二叉树，并且如果在一棵树中进行添加删除时，要移动许多结点。 式式式式存表示存表示存表示存表示typedef struct BiTNode ElemType data; struct BiTNode *Lchild, *Rchild; / 左 、右孩子指 BiTNode, *BiTree;DATALCHILDRCHILD41二叉链表AB

16、CDEFGABDCFEG42与单链表类似整个二叉树可以整个二叉树可以 以一个指向根结点的指针以一个指向根结点的指针( (表头指针表头指针) )表示表示43/ / 基本操作的原型基本操作的原型Status Status CreateBiTreeCreateBiTree( ( BiTreeBiTree &T ); &T );Status Status PrePreOrderTraverseOrderTraverse ( ( BiTreeBiTree &T, Status (* Visit )(&T, Status (* Visit )(TElemTypeTElemType e ) e ) ););

17、Status Status InInOrderTraverseOrderTraverse ( ( BiTreeBiTree &T, &T, Status (* Visit )(Status (* Visit )(TElemTypeTElemType e ) ); e ) );Status Status PosPosOrderTraverseOrderTraverse ( ( BiTreeBiTree &T, &T, Status (* Visit )(Status (* Visit )(TElemTypeTElemType e ) ); e ) );Status Status LevelLev

18、elOrderTraverseOrderTraverse ( ( BiTreeBiTree &T, Status (* Visit )(&T, Status (* Visit )(TElemTypeTElemType e ) e ) ););44也可以有类似于双向链表的结构-三叉链表parparententLchLchildilddatdataaRchRchildild 式式式式存表示存表示存表示存表示typedeftypedef structstruct TriTNodeTriTNode ElemTypeElemType data; data; structstruct BiTNodeBiT

19、Node * *LchildLchild, *, *RchildRchild; ; / / 左左 、右孩子右孩子指指 structstruct BiTNodeBiTNode *parent; *parent; / / 双双 指指 * *TriTreeTriTree;45二叉链表和三叉链表DATADATALCHILLCHILD DRCHILRCHILD Dparparententparentrchilddatalchild46ABCDEFGABCDEFG三叉链表47三叉链表结构图48可以证明在含有n个结点的二叉链表中有n+1个空链域。线索链表线索链表496.3 6.3 遍历二叉树和线索二叉树遍历

20、二叉树和线索二叉树6.3 遍历二叉树和线索二叉树50何为遍历二叉树DLR按某种顺序 访问 一次所有结点读取数据修改数据必须先左后右DLR前序遍历LDR中序遍历LRD后序遍历51先序遍历定义如下 若二叉树空 ，则空操作;否 则（1）根点（2）前序遍左子树;（3）前序遍右子树;A B D E G H C F I J52前序遍历动画演示53中序遍历定义如下若二叉树空 ，则空操作；否 则(1) 中序遍左子树；(2) 根点；(3) 中序遍右子树D B G E H A C I J F54中序遍历动画演示55后序遍历定义如下若二叉树空 ，则空操作；否 则(1) 后序遍左子树；(2) 后序遍右子树；(3) 根

21、点。D G H E B J I F C A56后序遍历动画演示57前序遍历算法实现-递规算法voidvoidPreorder (BiTree T，voidvoid(*visit)( BiTree ) / 先序遍历以先序遍历以T T为根指针的二叉树为根指针的二叉树if if(T) /T=NULL时，二叉树为空树，不做任何操作visit(T);/通过函数指针 *visit 访问根结点Preorder(T-L Lchild, visit);/先序遍历左子树Preorder(T-R Rchild, visit);/先序遍历右子树 /if 58 a+b*(c-d)-e/f a+b*(c-d)-e/f-*

22、/+-efcabd先序先序-+a*b-cd/ef中序中序a+b*c-d-e/f后后序序abcd-*+ef/-59练习 A B C D E F G H 先序遍历序列：中序遍历序列：后序遍历序列：ABDGCEFH BGDAECFHGDBEHFCA60经典题：写出三个结点的二叉树的前序、中序、后序遍历的序列前序ABCABCABCABCABC中序CBABCABACACBABC后序CBACBABCACBACBAABCAAAABBBBCCCC61画出和下列已知序列对应的二叉树1.二叉树的前序访问序列为:EBADCFHGIKJ 二叉树的中序访问序列为:ABCDEFGHIJK2.二叉树的中序访问序列为:DCB

23、GEAHFIJK 二叉树的后序访问序列为:DCEGBFHKJIA62写出前、中、后序遍历1237654863画出和下列已知序列对应的二叉树前：A B E F C D G H中：F E B A D C G H后：F E B D H G C A中：F E B A D C G H64线索二叉树如何保存在遍程中得到的前和后信息？ n个点有 n+1 个域的NULL65线索二叉树的结构如下：lchildltagDatartagrchild 0 0 lchildlchild 域域 指指示点的左孩子示点的左孩子 ltagltag= 1 1 lchildlchild 域域 指指示点的前示点的前 0 0 rchi

24、ldrchild 域域 指指示点的右孩子示点的右孩子 rtagrtag= 1 1 rchildrchild 域域 指指示点的示点的后后 以这种结构构成的二叉链表作为二叉树的存储结构以这种结构构成的二叉链表作为二叉树的存储结构, ,叫叫做做线索链表线索链表, ,其中指向结点其中指向结点前驱前驱与与后继后继的指针叫做的指针叫做线索线索. .加加上线索的二叉树称之为上线索的二叉树称之为线索二叉树。线索二叉树。 对二叉树以对二叉树以某种某种次序遍历使其变为线索二叉树的过程次序遍历使其变为线索二叉树的过程叫叫线索化线索化。66b+/a*efcd中序中序线索二叉索二叉树a + b * c d e / a

25、+ b * c d e / f f67中序线索链表在二叉树的线索链表在二叉树的线索链表上添加了一个头结点。上添加了一个头结点。P P134134。000+0000*01a11b10-01c11d11e11f10068结点的前趋：若其左标志为“1”，则左链为线索，指示其前驱，否则遍历左子树时的最后访问的一个结点（左子树最右下的结点）为其前驱。b+/a*efcd70什么时候采用线索链表做存储结构？程序中所用二叉树需要经常遍历或查找结点在遍历所得线性序列中的前驱和后继时。716.4 6.4 树和森林树和森林6.4 树和森林72树的存储结构1-双亲表示法序存构constMAX_TREE_SIZE =

26、100;typedef struct /点构 ElemType data; int parent;/双位置域PTNode;typedef struct /树构PTNode nodesMAX_TREE_SIZE;intr, n;/根的位置和点数PTree; A-1B0E1H2I2J2C0D0F7G7K9dataparent01234567891073双亲表示法示例A-1B0E1H2I2J2C0D0F7G7K9dataparent012345678910利用唯一双亲的性质适用于：PARENT(T,x)74孩子表示法多重链表 同同构构 ：树：树中每个点除了数据域中每个点除了数据域而外，而外， 有有d

27、d个域个域，分，分存放存放 点的每个孩子点的位点的每个孩子点的位置。置。其中其中dd是是 树树的度的度，即即 树树的的 各各个点的个点的 最最大度大度。种存构的种存构的缺缺点是点是，浪存空浪存空。一。一棵具棵具有有n n个个 点的度点的度kk的的 树树中必中必有有n(k-1)+1n(k-1)+1个空域个空域。datachild1child2childd 异异构构 ：若若 树树的每个点除了数据域的每个点除了数据域而外，而外，存存 各各自的孩子自的孩子 点的位点的位置，则置，则每个点每个点将将是是 异异构的构的。然可以然可以 存空存空，但是操作麻但是操作麻。datadegreechild1chil

28、d2childd752 树的孩子表示法typedeftypedef structstructCTNode/孩子点intintchild;structstructCTNode *next; *ChildPtr;typedeftypedef structstruct ElemType data;/点的数据元素ChildPtr firstchild;/孩子表指 CTBox;typedeftypedef structstruct CTBox nodesMAX_TREE_SIZE;intintn, r;/点数和根点的位置 CTree; J J76孩子表示法示例适用于：求孩子的操作J J77J J为了方便

29、我们可以-10122200779012345678910784 二叉链表表示法（孩子兄弟表示法）以二叉表做以二叉表做树树的存构的存构,表中点的两个域表中点的两个域分分 指向指向点的第点的第一一个孩子点和个孩子点和下一下一个兄个兄弟弟点点 (fchildfchild 和和 nsiblingnsibling)TypedefTypedef structstruct CSNodeCSNode ElemTypeElemType data; data; StructStruct CSNodeCSNode * * firstchildfirstchild ,* ,*nextsiblingnextsiblin

30、g; CSNodeCSNode,*,*CSTreeCSTree;79RADEBCFGHKRADBECFGHK 点点 xx的第的第 i i 个孩子个孩子，则，则只只要从要从firstchildfirstchild域找到第域找到第11个孩子点个孩子点，然然 后后沿沿着孩子点的着孩子点的nextsiblingnextsibling域走域走i -i -11步步 ，则，则可以找到第可以找到第 i i 个孩子个孩子。 如果每个点增如果每个点增一一个个 PARENTPARENT域域 ，则同，则同能方便能方便PARENTPARENT（T, xT, x）操操作作 。80ABDCEABCDEABCEDABCEDA

31、BCDE树和二叉和二叉树的的对应81练习画出此树的 双亲表示、孩子链表表示、二叉链表表示法。82森林与二叉树的转换森林是树的有限集合。从树的二叉链表表示定义知道：任何一棵和树对应的二叉树的右子树必空。若将森林中第二棵树的根结点看成第一棵树的根结点的兄弟，则可以导出森林和二叉树的对应关系。83森林和二叉树的对应：森林和二叉树的对应：84二叉树转换成森林85练习 86森林和树的遍历树的遍历：（1）先根遍历：先访问树的根结点，然后依次先根遍历根的每棵子树；（2）后根遍历：先依次后根遍历每棵子树，然后访问根结点。ABDCE树的先根序列为：ABCDE树的后根序列为：BDCEA 当以二叉链表作为树的存储结

32、构时，树的先根遍历和后根遍历分别 对应二叉树的先序遍历和中序遍历算法。ABCED87森林的遍历： （1）先序遍历森林：若森林非空，则可按下述规则遍历之：（2 2）中序遍历森林：若森林非空，则可按下述规则遍历之：）中序遍历森林：若森林非空，则可按下述规则遍历之： 访问森林中第一棵树的根结点； 先序遍历第一棵树中根结点的子树森林； 先序遍历除去第一树之后剩余的树构成的森林。 中序遍历第一棵树中根结点的子树森林； 访问森林中第一棵树的根结点； 中序遍历除去第一树之后剩余的树构成的森林。88先序遍先序遍历：ABCDEFGHIKJ中序遍中序遍历: BCEDAGFKIJH森林的先序遍历和中序遍历分别对应二

33、叉树的先序和中序遍历。896.6 6.6 赫夫曼树及其应用赫夫曼树及其应用6.6 赫夫曼树及其应用90赫夫曼树路径长度 定义：在树中从一个结点到另一个结点之间的分支构成了这两个结点间的路径，路径上的分支条数称为它的路径长度。树的路径长度 等于从树的根结点到树中各个结点的路径长度之和。12376548911237654812376548二叉树(a)二叉树(b)可以得到：a的路径长度PL=13，b的路径长度PL=14。为什么分支数相同、结点数相同，而路径长度不同？92赫夫曼树带权路径长度WPL什么是权？ 若将树中叶子结点赋给一个有着某种含义的数值，则这个数值称为该叶子结点的权。假定一个有n个权值的

34、集合w1,w2wn，其中wi=0。若T是一棵有n个叶子结点的二叉树，并且将权值w1,w2wn分别赋给T的n个叶结点，则我们称T是权值为w1,w2wn的扩充二叉树。带权值的称为外结点，不带权值的称为内结点。93树的带权路径长度 树的带权路径长度规定为所有叶子结点的带权路径长度之和，其中n 为叶子结点数目，wi为第i 个叶子结点的权值，li 为第i 个叶子结点的路径长度。WPL=在权值为w1,w2wn的扩充二叉树中，其WPL最小的扩充二叉树称为最优二叉树。94判断哪棵树是最优二叉树95457245725247上图中的3棵二叉树都是权值为7,5,2,4的扩充二叉树 a的带权路径长度WPL为：36；b

35、的为46，c的为35。由此可见，带权路径长度最小的扩充二叉树不一定是完全二叉树。直观的看：带权路径长度最小的二叉树应是权值大的外结点离根最近的扩充二叉树，这就是赫夫曼树。（a）（b）（c）96解某些判定问题，利用赫夫曼树可以得到最佳判定算法例如，例如，编制一制一个个程序程序实现从从百分制到五百分制到五级分制的分制的转换。if ( a60 ) b=“bad”;else if ( a70 ) b=“pass”; else if ( a80 ) b=“general”; else if ( a90 ) b=“good”; else b=“excellent”; 97a60不及格不及格YNa70及格及

36、格YNa80中等中等YNa80良好良好YN良好良好98中等中等YNa80a70YNa60及格及格Ya0），构造赫夫曼树HT。 if ( n=1) return; m = 2*n-1; HT = ( HuffmanTree ) malloc( (m+1)*sizeof(HTNode) ); /0号单元未用 for ( p=HT+1 , i=1 ; i=n ; +i, +p, +w) *p =*w, 0, 0, 0; for ( ; i=m ; +i, +p ) *p = 0, 0, 0, 0; for ( i = n+1; I=m ; +I ) /建赫夫曼树 /在HT 1 i-1 选择paren

37、t为0且weight最小的两个结点，其序号分别为s1和s2 Select( HT, i-1 , s1, s2); HTs1.parent = i; HTs2.parent = i ; HTi.lchild = s1; Hti.rchild = s2; Hti.weight = HTs1.weight + HTs2.weight;108/从叶子到根逆向获得每个字符的赫夫曼编码 HC = ( HuffmanCode) malloc( (n+1)*sizeof( char*); ch = ( char *) malloc( n*sizeof(char) ); /分配求编码的工作空间 cd n-1 =

38、 “0”; /编码结束符 for ( I =1; I=n; +i) /逐个字符求赫夫曼编码 start = n-1; /从叶子到根逆向求编码 for ( c=I , f = HTi.parent; f != 0; c=f, f = HTf.parent; ) if ( HTf.lchild = c ) cd -start = “0”; else cd -start = “1”; /为第i个字符编码分配空间 HCi = ( char*) malloc( n-start ) * sizeof( char ); strcpy( HCi, &cd start); free( cd );109基础习题总

39、结1. 已知一棵树边的集合为, , ，请画出这棵树，并回答下列问题：(1) 哪个是根结点?(2) 哪些是叶子结点?(3) 哪个是结点 G 的双亲?(4) 哪些是结点 G 的祖先?(5) 哪些是结点 G 的孩子?(6) 哪些是结点E的子孙?(7) 哪些是结点 E 的兄弟?哪些是结点F的兄弟?(8) 结点 B 和 N 的层次号分别是什么 ?(9) 树的深度是多少?(10) 以结点 C 为根的子树的深度是多少? 110 2、已知在一棵含有n个结点的树中，只有度为k的分支结点和度为0的叶子结点，试求该树的叶子结点数目解答：设有nk个度为k的分支结点，n0个度为0的分支结点各点度数总和为：n=k*nk+

40、1,最后计算得到叶节点个数为n-(n-1)/k 。 1114、画出与该树对应的二叉树，并写出该树的先根遍历序列和后根遍历序列 1135、将森林转换为相应的二叉树 114 6、假设用于通讯的电文仅由 8 个字母组成，字母在电文中出现的频率分别为 0.07, 0.19, 0.02, 0.06, 0.32, 0.03, 0.21, 0.10。试为这 8 个字母设计哈夫曼编码 115练习2如果一棵树有n1个度为1的结点, 有n2个度为2的结点, , nm个度为m的结点, 试问有多少个度为0的结点? 试推导之 。 点点 数数 n n = = n n0 0 + + n n11 + + n n2 2 + + + + n nmm 分分支支 数数 e e = = n-1 n-1 = = n n0 0 + + n n11 + + n n2 2 + + nmm-1-1= = m*nm*nmm + + (m-1)*n(m-1)*nm-1m-1 + + 2*n2 2 + n + n11则有则有 116