第十章树和二叉树

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

1、曾祖父曾祖父 爷爷爷爷 二爷二爷 三爷三爷 父亲父亲 二叔二叔独生子独生子族谱族谱树树是以分支关系定义的层次结构。是以分支关系定义的层次结构。第十章第十章树树树型树型结构是一类重要的结构是一类重要的非线性非线性结构。结构。学习重点学习重点: 树的基本概念树的基本概念 二叉树的基本概念、相关操作二叉树的基本概念、相关操作 树和森林与二叉树之间的相互转换树和森林与二叉树之间的相互转换 二叉树的应用二叉树的应用第十章第十章树树树的定义和基本术语树的定义和基本术语树树(Tree) : 是具有层次结构的是具有层次结构的 n(n0) 个结点的有限集。个结点的有限集。ABCDEFGHIJKLM一般树一般树第

2、第十十章章树树只有根结点的树只有根结点的树A树树(Tree) : 是是 n(n0) 个结点的有限集。个结点的有限集。n0 ，有且仅有一个称为有且仅有一个称为根根的结点。的结点。n1 ，除根结点外，其余结点可分为除根结点外，其余结点可分为 m(m0) 个互个互不相交的有限子集不相交的有限子集 T1 , ,T2 , ,Tm ，其中每个子集都其中每个子集都称为称为根结点的子树根结点的子树 。A. . .T1T2Tmn1第十章第十章树和二叉树树和二叉树基本术语基本术语结点结点(node)表示树中的元素，包括数据项及若干表示树中的元素，包括数据项及若干指向其子树的分支指向其子树的分支结点的度结点的度(d

3、egree)结点拥有的子树数结点拥有的子树数叶子叶子(leaf)度为度为0的结点的结点孩子孩子(child)结点子树的根称为该结点的孩子结点子树的根称为该结点的孩子双亲双亲(parents)孩子结点的上层结点叫该结点的孩子结点的上层结点叫该结点的兄弟兄弟(sibling)同一双亲的孩子同一双亲的孩子树的度树的度一棵树中最大的结点度数一棵树中最大的结点度数深度深度(depth)树中结点的最大层次数树中结点的最大层次数第十章第十章树和二叉树树和二叉树ABCDEFGHIJKLM结点结点A的度：的度：3结点结点B的度：的度：2结点结点M的度：的度：0叶子：叶子：K，L，F，G，M，I，J结点结点A的孩

4、子：的孩子：B，C，D结点结点B的孩子：的孩子：E，F结点结点I的双亲：的双亲：D结点结点L的双亲：的双亲：E结点结点B，C，D为兄弟为兄弟结点结点K，L为兄弟为兄弟树的度：树的度：3结点结点A的层次：的层次：1结点结点M的层次：的层次：4树的深度：树的深度：4结点结点F，G为堂兄弟为堂兄弟结点结点A是结点是结点F，G的祖先的祖先第十章第十章树和二叉树树和二叉树树的其它表示方法树的其它表示方法 a. 嵌套集合嵌套集合大集合表示树，小集合表示子树，相互嵌套。大集合表示树，小集合表示子树，相互嵌套。ABDCEFK LGHJIM第六章第六章树树b. 层次表示法层次表示法类似书的编目类似书的编目ABC

5、DEFGHIJKLM第六章第六章树树二叉树二叉树二叉树的定义二叉树的定义二叉树二叉树是是 n(n0) 个结点的有限集，它或者是个结点的有限集，它或者是空集空集，或者是由，或者是由一个一个根根和称为和称为左、右子树左、右子树的两个互不相交的的两个互不相交的二叉树二叉树组成组成。 二叉树是一个二叉树是一个递归定义递归定义。树树的子树次序不作规定，二叉树的两个子树有的子树次序不作规定，二叉树的两个子树有左、右之分左、右之分。树树中结点的度没有限制，二叉树中结点的度只能取中结点的度没有限制，二叉树中结点的度只能取 0、1、2。空二叉树空二叉树ABCDEF一般二一般二叉树叉树根根左子树左子树右子右子树树

6、第十章第十章树和二叉树树和二叉树根据定义，二叉树通常具有根据定义，二叉树通常具有 5 种基本形态种基本形态:空二叉树空二叉树A仅有根结点的二叉树仅有根结点的二叉树A右子树为空的二叉树右子树为空的二叉树A左、右子树均非空左、右子树均非空的二叉树的二叉树A左子树为空的二叉树左子树为空的二叉树关于树的基本术语也都适用于二叉树。关于树的基本术语也都适用于二叉树。二叉二叉树与与树的区的区别树：1、树最少有一个根最少有一个根结点（点（n0）2、树的度的度 03、树不要求子不要求子树顺序序二叉二叉树：1、二叉、二叉树可以可以为空空(n0)2、二叉、二叉树的度的度23、二叉、二叉树是有序是有序树，有左、右子，

7、有左、右子树之分。之分。例例10-1：试写出具有写出具有3个个结点的所有不同形点的所有不同形态的的树和二叉和二叉树。二叉树的性质二叉树的性质性质性质1 : 在二叉树的第在二叉树的第 i 层上层上至多有至多有 2i- -1 个结点个结点(i1)。归纳法证明归纳法证明:(1) i = 1，只有一个根结点，只有一个根结点，2i- -1 = 20 = 1，正确；正确；(2) 假设假设 i-1-1 成立，即第成立，即第 i-1-1 层上至多有层上至多有 2i- -2 个结点个结点；(3) 由于二叉树的结点的度至多为由于二叉树的结点的度至多为 2 ，故在第，故在第 i 层上层上的最大结点数为第的最大结点数

8、为第 i-1-1 层上的最大结点数的层上的最大结点数的 2 倍，即倍，即2 2i- -2 = 2i- -1 。性质性质2 : 深度为深度为 k 的二叉树至多有的二叉树至多有 2k 11 个结点个结点(k1) 。i = 1k(第第 i 层上的最大结点数层上的最大结点数)i = 1k2i- -1 2k 11练习练习: 归纳法证明。归纳法证明。引论引论: 一棵树有一棵树有 n 个个结点，则必有结点，则必有 n 1 条分支。条分支。证明证明:除根结点外，其它结点都有一个分支进入，除根结点外，其它结点都有一个分支进入，设设 B 为分支总数，故为分支总数，故 n = B + 1 ，故故 B = n - -

9、 1得得证。证。ABCDEF性质性质3 : 对任何一棵二叉树对任何一棵二叉树 T ，如果其终端结点数为如果其终端结点数为 n0，度为度为 2 的结点数为的结点数为 n2 ，则则 n0 = n2 + 1 。证明证明:(1)已知，终端结点数为已知，终端结点数为 n0 ，度为度为 2 的结点数为的结点数为 n2 ，设度为设度为 1 的结点数为的结点数为 n1 ，由于二叉树中的所有结点的度只能为由于二叉树中的所有结点的度只能为 0、1、2 ，故二叉树的结点总数为故二叉树的结点总数为 n = n0 + n1 + n2 ；(2)除根结点外，其它结点都有一个分支进入，除根结点外，其它结点都有一个分支进入，设

10、设 B 为分支总数，故为分支总数，故 n = B + 1 ，由于这些分支均是由度为由于这些分支均是由度为 1 或或 2 的结点引出的的结点引出的，所以有所以有 B = n1 + 2n2 ，故故 n = n1 + 2n2 + 1 ，由由 (1) 和和 (2) ，可得，可得 n0 + n1 + n2 = n1 + 2n2 + 1 ，故故有有 n0 = n2 + 1 。两种特殊形态二叉树两种特殊形态二叉树: 满二叉树满二叉树、完全二叉树完全二叉树。一棵深度为一棵深度为 k 且有且有 2k- -1 个结点的二叉树称为个结点的二叉树称为满二叉树满二叉树。 特点特点: 1 24 5满二叉树满二叉树3 67

11、(1) 每一层的结点数都达到每一层的结点数都达到最大结点数最大结点数。(2) 叶子结点在叶子结点在最大层最大层。(3) 任一结点，其左、右分支下的子孙的任一结点，其左、右分支下的子孙的最大层次相等最大层次相等。对对满二叉树的结点进行连续编号，从根结点起，自上而下，满二叉树的结点进行连续编号，从根结点起，自上而下，自左至右，自左至右，1、2、3、 、2k- -1 。深度为深度为 k 的，有的，有 n 个结点的二叉树，个结点的二叉树，当且仅当当且仅当其每一个结其每一个结点都与深度为点都与深度为 k 的满二叉树中编号从的满二叉树中编号从 1 至至 n 的结点一一对的结点一一对应时，称为应时，称为完全

12、二叉树完全二叉树。 1 24 53 6 1 23 4 5非完全二叉树非完全二叉树 1 24 53完全二叉树完全二叉树(1)特点特点: (1) 叶子结点只可能在层次最大的两层上出现。叶子结点只可能在层次最大的两层上出现。(2) 对任一结点，若其右分支的子孙的最大层次为对任一结点，若其右分支的子孙的最大层次为 l ，则则其左分支下的子孙的最大层次必为其左分支下的子孙的最大层次必为 l 或或 l+1。完全二叉树完全二叉树(2) 1 24 53 67满二叉二叉树和完全二叉和完全二叉树的区的区别：1、满二叉二叉树一定是完全二叉一定是完全二叉树，它是完全二叉，它是完全二叉树的特例。的特例。2、完全二叉、完

13、全二叉树不一定是不一定是满二叉二叉树。3、满二叉二叉树中中n1=0，完全二叉，完全二叉树中中n1=0或或1.性质性质4: :具有具有 n 个结点的完全二叉树的深度为个结点的完全二叉树的深度为 log2n+ 1。 证明证明:设设 n 结点完全二叉树的深度为结点完全二叉树的深度为 k ，k 层满二叉层满二叉树结点数树结点数k 层完全二层完全二叉树结点数叉树结点数k- -1 层满二层满二叉树结点数叉树结点数因为，因为，故故 2k-1-1- -1 n 2k- -1 有有 2k-1-1 n 2k又又 k- -1 log2n k因为因为 k 是整数，所以是整数，所以 k = log2n+ 1 。性质性质5

14、: : 如果对一棵有如果对一棵有n个结点的完全二叉树的结点按层序个结点的完全二叉树的结点按层序编号编号( (从第从第 1 层到第层到第 log2n+ 1 层，每层从层，每层从左左到到右右) )，则，则对任一结点对任一结点 i( (1in) )，有有 (1) 如果如果 i = 1，则结点则结点 i 为根，无父亲；如果为根，无父亲；如果 i 1，则结点则结点 i 的父结点的父结点 parent(i) 是结点是结点 i/ /2。 /求父亲求父亲(2) 如果如果 2i n，则结点则结点 i 的左儿子的左儿子 LChild(i) 是结点是结点 2i ；否则无否则无左儿子。左儿子。 /求左儿子求左儿子(3

15、) 如果如果 2i+1 n，则结点则结点 i 的右儿子的右儿子 RChild(i) 是结点是结点 2i+1 ；否否则无右儿子。则无右儿子。 /求右儿子求右儿子证明证明 (1) : 如果如果 (2)、(3) 成立，则成立，则 (1) 成立。成立。证明证明 (2) 和和 (3) :归纳法归纳法若有左儿子，应为若有左儿子，应为 2i = 2；i = 1: 根结点根结点 1 23若有右儿子，应为若有右儿子，应为 2i + 1 = 3；设对结点设对结点 i 成立，即结点成立，即结点 i 的左儿子为结点的左儿子为结点 2i，右儿子为结点右儿子为结点 2i+1；求证对结点求证对结点 i+1 也成立也成立:完

16、全二叉树中，结点完全二叉树中，结点 i 和和结点结点 i+1 之间的关系通常有两种情况，之间的关系通常有两种情况，或在或在同一层同一层上，或分别在上，或分别在相邻两层相邻两层上，且上，且最左和最右最左和最右。i+1i2i2i+1 2i+22i+3情况情况 1i+1i2i2i+12i+22i+3情况情况 2i+1i2i2i+1 2i+22i+3情况情况 1i+1i2i2i+12i+22i+3情况情况 2结点结点 i+1 的儿子的序号一定紧挨在结点的儿子的序号一定紧挨在结点 i 的儿子的序号的后面，的儿子的序号的后面，根据归纳假设，结点根据归纳假设，结点 i 的儿子的序号为的儿子的序号为 2i 和

17、和2i+1，则结点则结点 i+1 的左、右儿子的序号应为的左、右儿子的序号应为2i+2=2(i+1)、2i+3=2(i+1)+1。若若 2(i+1)+1n 则无右儿子，若则无右儿子，若 2(i+1)n 则无左儿子。则无左儿子。得证。得证。二叉树的存储结构二叉树的存储结构 (顺序、链式顺序、链式)1. 顺序存储结构顺序存储结构用一组用一组地址连续地址连续的存储单元依次的存储单元依次自上而下、自左至右自上而下、自左至右存储二叉树上的结点元素。存储二叉树上的结点元素。# define MAX_TREE_SIZE 100typedef TElemType SqBiTreeMAX_TREE_SIZE 1

18、 24 53完全二叉树完全二叉树: 编号为编号为 i 的元素存储在数组下标为的元素存储在数组下标为 i- -1 的分量中；的分量中；123450 1 2 3 4 1 23 4 5一般二叉树一般二叉树: 对照完全二叉树，存储在数组的相应分量中；对照完全二叉树，存储在数组的相应分量中；在最坏情况下，深度为在最坏情况下，深度为 k 的的右单支二叉树右单支二叉树需要需要 2k- -1 个存储空间。个存储空间。 1 23结论结论: 顺序存储结构适用于存储完全二叉树。顺序存储结构适用于存储完全二叉树。空间浪费空间浪费12345000 表示不存在此结点表示不存在此结点0 1 2 3 4 5 6 7 1230

19、0000 1 2 3 4 5 6 7例10-3 一个深度为K且只有K个结点的二叉树顺序存储最多需要多少个存储空间？最少需要多少个？例10-4 一个完全二叉树结点个数为1000，则n0、n1、n2和高度h各为多少？2. 链式存储结构链式存储结构D ( root，DL，DR )。链表结点包含链表结点包含 3 个域个域 : 数据域数据域、左指针域左指针域、右指针域右指针域数据域数据域左指针域左指针域右指针域右指针域datarchildlchilddatalchildrchild由这种结点结构得到的二叉树存储结构称为由这种结点结构得到的二叉树存储结构称为二叉链表二叉链表。二叉链表存储表示二叉链表存储表

20、示typedef struct BitNode BitNode,*BitTree;TElemType data ；struct BitNode * lchild ，* rchild ；ABCDEFGH有时还可以在结点结构中增加一个指向父亲的指针。有时还可以在结点结构中增加一个指向父亲的指针。数据域数据域左指针域左指针域右指针域右指针域datarchildlchildfather父指针域父指针域datalchildrchildfather采用何种存储结构，依赖于进行何种操作采用何种存储结构，依赖于进行何种操作基本操作基本操作 P:InitBiTree ( &T )DestroyBiTree (

21、&T )CreateBiTree ( &T)BiTreeEmpty ( T )InsertChild ( T ，A，X )操作操作: 二叉树二叉树 T 存在，向存在，向 T 中插入一个信息域为中插入一个信息域为 A 的结点，的结点，作为作为 T 中信息域为中信息域为 X 的结点的左儿子，而其原来的左子树的结点的左儿子，而其原来的左子树为新结点的左子树为新结点的左子树 。DeleteChild ( T ，p，LR )操作操作: 根据根据 LR 为为 0 或或 1 ，删除，删除 T 中中 p 所指结点的左或右子树。所指结点的左或右子树。 PreOrderTraverse ( T ，visit()

22、)操作操作: 先序遍历二叉树先序遍历二叉树 T 。 InOrderTraverse ( T ，visit() )操作操作: 中序遍历二叉树中序遍历二叉树 T 。 PostOrderTraverse ( T ，visit() )操作操作: 后序遍历二叉树后序遍历二叉树 T 。 LevelOrderTraverse ( T ，visit() )操作操作: 层次遍历二叉树层次遍历二叉树 T 。 二叉树的基本操作二叉树的基本操作遍历二叉树遍历二叉树遍历二叉树遍历二叉树 : : 如何按某条如何按某条搜索路径搜索路径巡访树中每个结点，巡访树中每个结点，使得每个结点均被使得每个结点均被访问一次访问一次，而且

23、仅被访问一次。，而且仅被访问一次。 D ( root，DL，DR )。如果能依次遍历这三部分，就可以遍历整个二叉树；如果能依次遍历这三部分，就可以遍历整个二叉树；设设以以 D、L、R 分别表示分别表示访问根结点访问根结点、遍历左子树遍历左子树、遍遍历右子树历右子树，则可以存在，则可以存在 6 种遍历方案种遍历方案: DLR、DRL、 LDR、LRD、RDL、RLD；若限定若限定先左后右先左后右的原则，则只有的原则，则只有 3 种情况种情况: 先先(根根)序序遍历、遍历、中中(根根)序序遍历、遍历、后后(根根)序序遍历。遍历。DLRLDR、LRD、DLRRDL、RLD、DRL先先(根根)序遍历序

24、遍历: 若若二叉树为空，则返回；否则二叉树为空，则返回；否则(1) 访问根结点；访问根结点；(2) 先先(根根)序遍历左子树；序遍历左子树；(3) 先先(根根)序遍历右子树；序遍历右子树；A AABCA B CADBCD L RAD L RD L RBDCD L R先序遍历序列：先序遍历序列：A B D C先序遍历先序遍历:printf(T-data) ; PreOrderTraverse ( T-lchild) ;PreOrderTraverse ( T-rchild) ;if (T) Status PreOrderTraverse ( BiTree T)算法算法 10.1 先序遍历递归算法

25、先序遍历递归算法else return OK ;算法的C语言实现：void PreOrderTraverse ( BiTree T) if(T!=NULL) printf(%dt,T-data); PreOrderTraverse(T-lchild); PreOrderTraverse(T-rchild); ABCDEFGH先序遍历先序遍历000000000beginend先序遍历顺序先序遍历顺序:A B D F G C E HABDFGCEH中中(根根)序遍历序遍历: 若若二叉树为空，则返回；否则二叉树为空，则返回；否则(2) 访问根结点；访问根结点；(1) 中中(根根)序遍历左子树；序遍历

26、左子树；(3) 中中(根根)序遍历右子树；序遍历右子树；A AABCB A CADBCL D RBL D RL D RADCL D R中序遍历序列：B D A C中序遍历:printf(T-data) ; InOrderTraverse ( T-lchild) ;InOrderTraverse ( T-rchild) ;If (T) else return OK ;Status InOrderTraverse ( BiTree T ) ) 算法算法 10.2 中序遍历递归算法中序遍历递归算法ABCDEFGH中序遍历中序遍历000000000beginend中序遍历顺序中序遍历顺序:ABDFGC

27、 E HBFDGACEH后后(根根)序遍历序遍历: 若若二叉树为空，则返回；否则二叉树为空，则返回；否则(3) 访问根结点；访问根结点；(1) 后后(根根)序遍历左子树；序遍历左子树；(2) 后后(根根)序遍历右子树；序遍历右子树；A AABCB C AADBC L R DL R DL R DADCL R D后序遍历序列： D B C A后序遍历:Bprintf(T-data) ; PostOrderTraverse ( T-lchild) ;PostOrderTraverse ( T-rchild) ;If (T) else return OK ;Status PostOrderTraver

28、se ( BiTree T ) 算法算法 10.3 后序遍历递归算法后序遍历递归算法ABCDEFGH后序遍历后序遍历000000000beginend后序遍历顺序后序遍历顺序:F G D B H E C AABDFGCEH例，表达式例，表达式 a + b * c d / e- -+ /*d ebca先序遍历先序遍历: + a * b c / d e前缀式，波兰式前缀式，波兰式中序遍历中序遍历:a + b * c d / e中缀式，算术表达式中缀式，算术表达式后序遍历后序遍历:a b c * + d e / - -后缀式，逆波兰式后缀式，逆波兰式中缀表示中缀表示: 适于人的思维适于人的思维后缀表

29、示后缀表示: 适于计算机的思维适于计算机的思维a + b * c d / ea b c * + d e / - -ABCDEFGH000000000beginend中序遍历顺序中序遍历顺序:ABDFGC E HBFDGACEH用栈实现中序遍历的非递归算法用栈实现中序遍历的非递归算法栈栈用来打印用来打印结点信息及结点信息及访问右子树访问右子树 InitStack (S) ; p=T ;pop (S, p) ; p=p-rchild ; /遍历右子树遍历右子树 if (p) Push (S, p) ; p=p-lchild ; /遍历左子树遍历左子树else While ( p | ! Stack

30、Empty(S) )Return OK;Status InOrderTraverse ( BiTree T )printf (p-data) ; /打印根结点打印根结点用C语言实现中序遍历的非递归算法void InOrderTraverse ( BiTree T ) int i=0; BiTree p,sM; p=T; while(p!=NULL|i0) if(p) /如果当前结点非空 si+=p; /则当前结点入栈 p=p-lchild; /然后将p的左子树作为新的当前结点(遍历左子树) else p=s-i; /否则弹出当前栈顶元素 printf(“%dt”,p-data); /输出元素的

31、值 p=p-rchild; /然后将p的右子树作为新的当前结点(遍历右子树) ABCDEFGH000000000beginend中序遍历顺序中序遍历顺序:ABDFGC E H例，例，AB DFGC E H对二叉树除可以进行先序、中序、后序的遍历外，还对二叉树除可以进行先序、中序、后序的遍历外，还可以进行可以进行层次遍历层次遍历。 H CF ED A层次遍历层次遍历: H , C , D , F , E , A过程过程: 打印打印 H；打印打印 H 的左儿子的左儿子 C；打印打印 C 的左、右儿子的左、右儿子 F、E；打印打印 D 的左、右儿子的左、右儿子 A；打印打印 H 的右儿子的右儿子 D

32、；队列实现层次遍历队列实现层次遍历 H CF ED AH入队入队出队出队HC DCF EDAFEAEnQueue(Q , T) ; While ( ! QueueEmpty(Q) ) Return OK;Status LevelOrderTraverse ( BiTree T ) printf (p-data) ; /打印结点打印结点DeQueue(Q , p) ;EnQueue(Q , p-lchild ) ; EnQueue(Q , p-rchild ) ; H CF ED AHCDFEA占用了六个空间占用了六个空间HHCDCFEDAFE A二叉树插入操作二叉树插入操作利用遍历可以实现二叉

33、树的插入、删除操作。利用遍历可以实现二叉树的插入、删除操作。InsertChild ( T ，A，X )操作操作: 二叉树二叉树 T 存在，向存在，向 T 中插入一个数据域为中插入一个数据域为 X 的结点，的结点，作为作为 T 中数据域为中数据域为 A 的结点的左儿子，而其原来的左子树的结点的左儿子，而其原来的左子树为新结点的左子树为新结点的左子树 。思想思想:1. 首先找到首先找到数据数据域为域为 A 的结点的结点 p 。2. 建立建立数据数据域为域为 X 的新结点的新结点 q 。3. q-lchild = p-lchild 。4. p-lchild = q 。p H AF ED GXq/找

34、到信息域为找到信息域为 A 的结点的结点 p 。q = ( BiTNode * ) malloc ( sizeof(BiTNode) ) ； /新结点新结点 if ( ! q ) exit (OVERFLOW) ；q-data=x; q-lchild = p-lchild ；p-lchild = q ；InsertChild ( BiTree &T ，TElemType A ，TElemType X ) InitStack (S) ; p=T ;Pop (S, p) ; p=p-rchild ; /遍历右子树遍历右子树If (p) Push (S, p) ; p=p-lchild ; /遍历左

35、子树遍历左子树Else While ( p | ! StackEmpty(S) ) Return ERROR;Status InOrderTraverse ( BiTree T, TElemType A, BitNode &p ) if ( p-data = A ) return OK; /找到结点找到结点/用中序遍历的方法，找到信息域为用中序遍历的方法，找到信息域为 A 的结点的结点 p 。性质性质: 含有含有 n 个结点的二叉链表中有个结点的二叉链表中有 n+1 个空链域。个空链域。证明证明:(1)设，终端结点数为设，终端结点数为 n0 ，度为度为 1 的结点数为的结点数为 n1 ，故二叉

36、树的结点总数为故二叉树的结点总数为 n = n0 + n1 + n2 ；度为度为 2 的结点数为的结点数为 n2 ，(2)空链域个数为空链域个数为 2n0 + n1 ，已知，已知，n0 = n2 + 1 ，故，故， 2n0 + n1= n0 + n1 + n2 + 1= n + 1树和森林树和森林树的存储结构树的存储结构 父亲表示法父亲表示法 儿子表示法儿子表示法链式存储链式存储顺序存储顺序存储 父亲儿子表示法父亲儿子表示法 二叉树表示法二叉树表示法RBACDEFHGK一一. 父亲表示法父亲表示法用一组地址连续空间存储树的结点，每个结点由两个域组成。用一组地址连续空间存储树的结点，每个结点由两

37、个域组成。RBACDEFHGKdatafather数据域数据域 指示器，指向其父结点指示器，指向其父结点R - -1A 0B 0C 0D 1E 1F 30123456789G 6H 6K 6无父无父结点结点父结父结点为点为R父结父结点为点为Atypedef struct PTNode PTNode ； /定义树结点定义树结点TElemType data ； /数据域数据域int father ； /指示器，指向其父结点指示器，指向其父结点# define MAX_TREE_SIZE 100 /定义最大结点定义最大结点数数typedef struct PTree ； /定义树定义树PTNode

38、nodesMAX_TREE_SIZE ； /顺序结构存储顺序结构存储int r ，n ； /根的位置和结点总数根的位置和结点总数树的父亲表示法存储表示树的父亲表示法存储表示R - -1A 0B 0C 0D 1E 1F 30123456789G 6H 6K 6结构特点结构特点:优优: 获取获取祖先结点祖先结点(根结点根结点)比较方便比较方便RBACDEFHGK缺缺: 获取某个结点的获取某个结点的儿子结点儿子结点需要遍历整个结构需要遍历整个结构二二. 儿子表示法儿子表示法1. 多叉树表示法多叉树表示法链式存储链式存储AchildA1childA2childA3BchildB1childB2chil

39、dB3CchildC1childC2childC3DchildD1childD2childD3链表中的结点存在两种格式链表中的结点存在两种格式:childnchild2child1data. . .每个结点均采用定长格式，每个结点均采用定长格式，n 为树的度。为树的度。childnchild2child1data. . .degree每个结点采用变长格式，每个结点采用变长格式，degree = n 为该结点的度。为该结点的度。定长操作方便，变长操作不方便定长操作方便，变长操作不方便结构分析结构分析定长浪费空间，变长节省空间定长浪费空间，变长节省空间采用定长存储格式，链表中存在很多采用定长存储格

40、式，链表中存在很多空链域空链域，造成空间浪费。，造成空间浪费。定义定义: 在一棵有在一棵有 n 个结点，度为个结点，度为 k 的树中必有的树中必有 (k- -1)n+1 个空链域。个空链域。证明证明:(1)设设度为度为 0、1、 、k 的结点数分别为的结点数分别为 n0、 n1、 、nk . . . . .设设树中空链域总数为树中空链域总数为 X则有则有 X = kn0 + (k- -1)n1 + + (k- -(k- -1)nk- -1 + (k- -k)nk. . .= kn0 + kn1 + + knk- -1 + knk. . .- - ( n1 + 2n2 + + (k- -1)nk

41、- -1 + knk ). . .(2)另外除根结点外，其它结点都有一个分支进入，另外除根结点外，其它结点都有一个分支进入，设设 B 为分支总数，故为分支总数，故 n = B + 1 ，首先首先 n = n0 + n1 + + nk . . .又由于这些分支均是由度为又由于这些分支均是由度为 1 、2 、 、k的结点引出的的结点引出的，. . .所以有所以有 B = n1 + 2n2 + + (k- -1)nk- -1 + knk . . .= kn0 + kn1 + + knk- -1 + knk. . .- - ( n1 + 2n2 + + (k- -1)nk- -1 + knk ). .

42、 .X= kn - - B= kn (n- -1)= (k1)n+1得证得证2. 顺序存储顺序存储把每个结点的儿子结点以把每个结点的儿子结点以单链表单链表的结构存储的结构存储 ；则则 n 个结点就构成了个结点就构成了 n 条条儿子单链表儿子单链表 ；将将 n 条单链表头指针以条单链表头指针以顺序线性表顺序线性表存储存储 ；RBACDEFHGK0123456789B A C D E R F G H K 4513267980123456789B A C D E R F G H K 451326798typedef struct CTNode * ChildPtr ； /儿子结儿子结点点 int c

43、hild ； struct CTNode * next ；typedef struct CTBox ； /儿子头指针儿子头指针 TElemType data ； ChildPtr firstchild ；typedef struct CTree ； /树结构树结构# define MAX_TREE_SIZE 100 /定义最大结点数定义最大结点数 CTBox nodesMAX_TREE_SIZE ；int r ，n ； /根的位置和结点总数根的位置和结点总数RBACDEFHGK0123456789B A C D E R F G H K 451326798优点优点: 方便搜索儿子结点方便搜索儿子

44、结点缺点缺点: 查找父结点需要从头遍历整个顺序表查找父结点需要从头遍历整个顺序表三三. 父亲儿子表示法父亲儿子表示法如何既能方便搜索儿子结点，又能方便查找父结点？如何既能方便搜索儿子结点，又能方便查找父结点？0123456789B A C D E R F G H K 451326798- -1000113666四四. 二叉树表示法二叉树表示法将树以二叉树的形式表示。将树以二叉树的形式表示。令令结点的结点的两个链域两个链域分别指向该结点的分别指向该结点的第一个儿子第一个儿子和和右边的兄弟右边的兄弟。RBACDEFHGKRADBECFGHKRADBECFGHKtypedef struct CSNo

45、de CSNode ； /结点结点TElemType data ；struct CSNode * firstchild ；struct CSNode * nextsibling ；查找结点的儿子查找结点的儿子:沿结点的沿结点的 firstchild 域可找到第一个儿子，域可找到第一个儿子，然后再沿然后再沿 nextsibling 域可找到其它儿子。域可找到其它儿子。查找结点的兄弟查找结点的兄弟:沿结点的沿结点的 nextsibling 域可找到所有兄弟。域可找到所有兄弟。查找结点的父亲查找结点的父亲:为每个结点增加一个为每个结点增加一个 father 域指向父结点。域指向父结点。RBACDEF

46、HGKRADBECFGHK性质性质:1. 树可以表示成二叉树的形式树可以表示成二叉树的形式启示启示: 树与二叉树的转换树与二叉树的转换2. 树转换成一棵只有树转换成一棵只有左子树左子树的二叉树的二叉树森林与二叉树的转换森林与二叉树的转换 ACBDEFGHIJ(1). 任何一棵树都可以转换为一棵任何一棵树都可以转换为一棵没有没有右右子树子树的二叉树。的二叉树。(2). 森林是由若干棵树构成的集合，若把森林中森林是由若干棵树构成的集合，若把森林中第二棵树第二棵树的的根结点看成是根结点看成是第一棵树第一棵树的根结点的根结点兄弟兄弟，就可以导出森林与二叉，就可以导出森林与二叉树的转换。树的转换。1.

47、森林转换成二叉树森林转换成二叉树(1) 增加增加一个根结点，作为原一个根结点，作为原森林中各树根结点的森林中各树根结点的父结点父结点。(2) 将将新树新树转换成二叉树。转换成二叉树。(3) 删除删除二叉树的根结点。二叉树的根结点。ACBDEFGHIJRBECDFGHIJRA2. 二叉树转换成森林二叉树转换成森林(1) 增加增加一个新根结点，原二叉树根一个新根结点，原二叉树根结点做为新根结点的结点做为新根结点的左儿子左儿子。(2) 将将新二叉树新二叉树转换成树。转换成树。(3) 删除删除树的根结点变为森林。树的根结点变为森林。BECDFGHIJARACBDEFGHIJR2. 二叉树转换成森林二叉

48、树转换成森林(1) 增加增加一个新根结点，原二叉树根一个新根结点，原二叉树根结点做为新根结点的结点做为新根结点的左儿子左儿子。(2) 将将新二叉树新二叉树转换成树。转换成树。(3) 删除删除树的根结点变为森林。树的根结点变为森林。BECDFGHIJARACBDEFGHIJR森林和树的遍历森林和树的遍历 1. 分割分割从结构上，可以把任意的森林分成三部分从结构上，可以把任意的森林分成三部分:1) 第一棵树的根结点。第一棵树的根结点。2) 第一棵树根结点的子树构成的森林。第一棵树根结点的子树构成的森林。3) 其余的树构成的森林。其余的树构成的森林。按按这三部分的不同排列次序可把森林的遍历次序分为前

49、序、中序、这三部分的不同排列次序可把森林的遍历次序分为前序、中序、后序。后序。2) 访问第一棵树的根结点。访问第一棵树的根结点。3) 按前序遍历根结点的子树构成的森林。按前序遍历根结点的子树构成的森林。4) 按前序遍历其余的树构成的森林。按前序遍历其余的树构成的森林。森林的前序遍历森林的前序遍历1) 如果森林中树的个数为如果森林中树的个数为 0 ，则返回。，则返回。ACBDEFGHIJBECDFGHIJAABCDEFGHIJ3) 访问第一棵树的根结点。访问第一棵树的根结点。2) 按中序遍历第一棵树根结点的子树构按中序遍历第一棵树根结点的子树构成的森林。成的森林。4) 按中序遍历其余的树构成的森

50、林。按中序遍历其余的树构成的森林。森林的中序遍历森林的中序遍历1) 如果森林中树的个数为如果森林中树的个数为 0 ，则返回。，则返回。ACBDEFGHIJBECDFGHIJABCDAFEHJIG4) 访问第一棵树的根结点。访问第一棵树的根结点。2) 按后序遍历第一棵树根结点的子树构按后序遍历第一棵树根结点的子树构成的森林。成的森林。3) 按后序遍历其余的树构成的森林。按后序遍历其余的树构成的森林。森林的后序遍历森林的后序遍历1) 如果森林中树的个数为如果森林中树的个数为 0 ，则返回。，则返回。ACBDEFGHIJBECDFGHIJABCDFHJIGEA森林的前、中、后序遍历与对应二叉树的前、

51、中、后序遍历一致。森林的前、中、后序遍历与对应二叉树的前、中、后序遍历一致。树的应用树的应用1. 二叉分类树二叉分类树(二叉排序树二叉排序树)2. 判定树判定树3. 赫夫曼树赫夫曼树(最优二叉树最优二叉树)赫夫曼树赫夫曼树 Huffman (最优二叉树最优二叉树)基本概念基本概念:从树中一个结点到另一个结点之间的分支构成这两个结点之间的从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径路径。 路径上的分支数目称做路径上的分支数目称做路径长度路径长度。 XYZX 到到 Y 的路径的路径路径长度为路径长度为 2树的路径长度树的路径长度是从树根到是从树根到每一个每一个结点的路径长度之结点的

52、路径长度之和和。 在具有相同结点数的所有二叉树中，在具有相同结点数的所有二叉树中， 的路径长度是最短的。的路径长度是最短的。完全二叉树完全二叉树推广：为结点加权推广：为结点加权 w 。735ABCDE结点的带权路径长度结点的带权路径长度为从根结点到该结点之间的路径长度与结点上为从根结点到该结点之间的路径长度与结点上权值的乘积。权值的乘积。树的带权路径长度树的带权路径长度为树中所有为树中所有叶子结点叶子结点的带权路径长度之和，通常的带权路径长度之和，通常记做记做 WPL = wk L(vk ) nk=1wk 为叶子结点为叶子结点 vk 的的权值权值L(vk )为叶子结点为叶子结点 vk 的路径长

53、度的路径长度例，例，3 棵二叉树，都有棵二叉树，都有 4 个叶子结点个叶子结点 a、b、c、d，分别带权分别带权7、5、2、4，求它们各自的带权路径长度。，求它们各自的带权路径长度。abcd7524(1)abdc7542(2)cdba2457(3)(1) WPL = 72 + 52 + 22 + 42 = 36(2) WPL = 73 + 53 + 21 + 42 = 46(3) WPL = 71 + 52 + 23 + 43 = 35假设有假设有n个权值个权值 w1,w2, wn ，试构造一棵有试构造一棵有n个叶子结点个叶子结点的二叉树，每个叶子结点带权为的二叉树，每个叶子结点带权为 wi

54、，则其中带权路径长度则其中带权路径长度WPL最小最小的二叉树称的二叉树称做做最优二叉树最优二叉树或或赫夫曼树赫夫曼树。 如何构造如何构造赫夫曼树赫夫曼树？(1) 根据给定的根据给定的 n 个权值个权值 w1,w2, wn 构成构成 n 棵二叉树的集合棵二叉树的集合 F = T1,T2, Tn，其中每棵二叉树其中每棵二叉树 Ti 中只有一个权值为中只有一个权值为 wi 的的根结根结点点。(2) 在在 F 中选取两棵根结点中选取两棵根结点权值最小权值最小的树作为左、右子树构造一棵的树作为左、右子树构造一棵新的二叉树，且置新二叉树的根结点的权值为其左、右子树根结点新的二叉树，且置新二叉树的根结点的权

55、值为其左、右子树根结点的权值之和。的权值之和。(3) 在在 F 中删除这两棵树，同时将新得到的二叉树加入集合中删除这两棵树，同时将新得到的二叉树加入集合 F 中。中。(4) 重复重复 (2) 和和 (3) ，直到，直到 F 中只含一棵树为止。中只含一棵树为止。例，例， 4 个叶子结点个叶子结点 a、b、c、d，分别带权分别带权7、5、2、4。cd24b5a7初始初始cd246b5cd24611a7b5cd2461118赫夫曼编码赫夫曼编码1. 编码编码例，例，传送传送 ABACCD，四，四种字符，可以分别编码为种字符，可以分别编码为 00,01,10,11。则原电文转换为则原电文转换为 00

56、01 00 10 10 11。对方接收后，采用二位一分进行译码。对方接收后，采用二位一分进行译码。电文电文编码编码二进制二进制二进制二进制译码译码电文电文当然，为电文编码时，总是希望总长越短越好，当然，为电文编码时，总是希望总长越短越好，如果对每个字符设计长度不等的编码，且让电文中出现次数较多如果对每个字符设计长度不等的编码，且让电文中出现次数较多的字符采用较短的编码，则可以减短电文的总长。的字符采用较短的编码，则可以减短电文的总长。例，例，对对 ABACCD 重新编码，分别编码为重新编码，分别编码为 0 , 00 , 1 , 01。A B C D则原电文转换为则原电文转换为 0 00 0 1

57、 1 01。 减短了。减短了。问题问题: 如何译码？如何译码？前四个二进制字符就可以多种译法。前四个二进制字符就可以多种译法。AAAABB2. 前缀编码前缀编码若设计的长短不等的编码，满足任一个编码都不是另一个编码的若设计的长短不等的编码，满足任一个编码都不是另一个编码的前缀，则这样的编码称为前缀，则这样的编码称为前缀编码前缀编码。例，例， A , B , C , D 前缀编码可以为前缀编码可以为 0 , 110 , 10 , 111利用利用二叉树二叉树设计二进制前缀编码。设计二进制前缀编码。叶子结点表示叶子结点表示 A , B , C , D 这这 4 个字符个字符ACBD000111左分支

58、表示左分支表示 0，右分支表示，右分支表示 1从根结点到叶子结点的路径上经过的二从根结点到叶子结点的路径上经过的二进制符号串作为该叶子结点字符的编码进制符号串作为该叶子结点字符的编码A(0)B(110)C(10)D(111)路径长度为编码长度路径长度为编码长度如何得到最短的二进制前缀编码？如何得到最短的二进制前缀编码？3. 赫夫曼编码赫夫曼编码设设每种字符在电文中出现的概率每种字符在电文中出现的概率 wi 为，则依此为，则依此 n 个字符出现的概个字符出现的概率做权，可以设计一棵赫夫曼树，使率做权，可以设计一棵赫夫曼树，使WPL = wi li 最小最小ni=1wi 为叶子结点的出现概率为叶子

59、结点的出现概率 ( 权权)li 为根结点到叶子结点的路径长度为根结点到叶子结点的路径长度例，某通信可能出现例，某通信可能出现 A B C D E F G H 8 个字符，其概率分别为个字符，其概率分别为 0.05 , 0.29 , 0.07 , 0.08 , 0.14 , 0.23 , 0.03 , 0.11 ，试设计赫夫曼编码，试设计赫夫曼编码不妨设不妨设 w = 5 , 29 , 7 , 8 , 14 , 23 , 3 , 11 排序后排序后 w = 3 , 5 , 7 , 8 , 11 , 14 , 23 , 29 7 , 8 , 8 , 11 , 14 , 23 , 29 8 , 11

60、 , 14 , 15 , 23 , 29 14 , 15 , 19 , 23 , 29 19 , 23 , 29 , 29 29 , 29 , 42 42 , 58 100 100 01100110101010A (0110)B (10)C (1110)D (1111)E (110)F (00)G (0111)H (010)AG8537815CD1119H1429E F4223 B5829ACEA 编码为编码为 0110 1110 110 0110如何译码？如何译码？1. 从根结点出发，从左至右扫描编码，从根结点出发，从左至右扫描编码，2. 若为若为 0 则走左分支，若为则走左分支，若为1 则

61、走右分支，直至叶结点为止，则走右分支，直至叶结点为止，3. 取叶结点字符为译码结果，返回重复执行取叶结点字符为译码结果，返回重复执行 1,2,3 直至全部译完为止直至全部译完为止10001100110101010A (0110)B (10)C (1110)D (1111)E (110)F (00)G (0111)H (010)AG8537815CD1119H1429E F4223 B5829ACEA作业作业: 假设用于通讯的电文由假设用于通讯的电文由 8 个字母组成，个字母组成，A B C D E F G H ，字母在电文中的出现频率分别为字母在电文中的出现频率分别为 0.07，0.19，0.

62、02，0.06，0.32，0.03，0.21，0.10，试设计，试设计赫赫夫曼编码。夫曼编码。本章重点本章重点1二叉树的存储结构及其各种操作，遍历二叉树二叉树的存储结构及其各种操作，遍历二叉树2树和森林与二叉树的转换关系，树的遍历树和森林与二叉树的转换关系，树的遍历3.哈夫曼树和哈夫曼编码哈夫曼树和哈夫曼编码本章难点本章难点1遍历二叉树的算法遍历二叉树的算法2树和森林与二叉树的转换关系，哈夫曼树及编码树和森林与二叉树的转换关系，哈夫曼树及编码典型例题：一、选择题一、选择题1、在树中，互为堂兄弟的结点拥有相同的在树中，互为堂兄弟的结点拥有相同的( )( )。 A A、双亲双亲 B B、祖先祖先

63、C C、层次层次 D D、孩子孩子 2 2、树最适合用来表示树最适合用来表示 （）。（）。 A A、有序数据元素有序数据元素 B B、无序数据元素无序数据元素 C C、元素之间具有分支层次关系的数据元素之间具有分支层次关系的数据 D D、元素之间无联系的数据元素之间无联系的数据3 3、在一棵高度为在一棵高度为h h的满四叉树中，结点总数为的满四叉树中，结点总数为( )( )。 A A、( (4h-14h-1)/3)/3 B B、(4h-1)/2 (4h-1)/2 C C、(4h-1)/4 (4h-1)/4 D D、4h4h4 4、若一棵二叉树具有若一棵二叉树具有1010个度为个度为2 2的结点

64、，则该的结点，则该二叉树的度为二叉树的度为0 0的结点个数是的结点个数是( )( )。 A. 9 A. 9 B. 11 B. 11 C. 12 C. 12 D. D. 不确定不确定5 5、按二叉树的定义，具有按二叉树的定义，具有3 3个结点的二叉树有个结点的二叉树有( ) ( ) 种。种。 A A、3 B3 B、4 C4 C、5 D5 D、6 6二、填空二、填空1 1、在树中，度为在树中，度为( )( )的结点称为叶子。的结点称为叶子。2 2、在树中，除根结点外，其他结点都有且只有在树中，除根结点外，其他结点都有且只有一个一个( )( )结点。结点。3 3、有有100100个结点的树有个结点的

65、树有( )( )条边。条边。4 4、若将树中的每个结点的各子树看成从左到右若将树中的每个结点的各子树看成从左到右有次序，则该树为有次序，则该树为( )( )树。树。5 5、一棵二叉树有一棵二叉树有6767个结点，这些结点的度要么个结点，这些结点的度要么是是0 0，要么是，要么是2 2。这棵二叉树中度为。这棵二叉树中度为2 2的结点有的结点有( ( ) )个。个。6 6、深度为、深度为K K的完全二叉树至少有的完全二叉树至少有2(k-1)2(k-1)个结点，个结点，至多有至多有2(k-1)+12(k-1)+1个结点，若按自上而下，从左个结点，若按自上而下，从左到右次序给结点编号（从到右次序给结点

66、编号（从1 1开始），则编号最小开始），则编号最小的叶子结点的编号是的叶子结点的编号是( )( )。三、问答题：三、问答题：1、若二叉树中各结点的值均不相同，则由二叉若二叉树中各结点的值均不相同，则由二叉树的前序序列和中序序列，或由其后序序列和树的前序序列和中序序列，或由其后序序列和中序序列均能唯一地确定一棵二叉树，但由前中序序列均能唯一地确定一棵二叉树，但由前序序列和后序序列却不一定能唯一地确定一棵序序列和后序序列却不一定能唯一地确定一棵二叉树。二叉树。(1)已知一棵二叉树的前序序列和中序序列分已知一棵二叉树的前序序列和中序序列分别为别为ABDGHCEFI和和GDHBAECIF，请画出此请画

67、出此二叉树。二叉树。(2)已知一棵二叉树的中序序列和后序序列分已知一棵二叉树的中序序列和后序序列分别为别为BDCEAFHG和和DECBHGFA，请画出此二请画出此二叉树。叉树。(3)已知一棵二叉树的前序序列和后序序列分已知一棵二叉树的前序序列和后序序列分别为别为AB和和BA，请画出这两棵不同的二叉树。请画出这两棵不同的二叉树。2、一棵度为一棵度为2的有序树与一棵二叉树有何的有序树与一棵二叉树有何区别区别?答：一棵度为二的有序树与一棵二叉树的答：一棵度为二的有序树与一棵二叉树的区别在于区别在于:有序树的结点次序是相对于另有序树的结点次序是相对于另一结点而言的，如果有序树中的子树只一结点而言的，如

68、果有序树中的子树只有一个孩子时，这个孩子结点就无须区有一个孩子时，这个孩子结点就无须区分其左右次序，而二叉树无论其孩子数分其左右次序，而二叉树无论其孩子数是否为是否为2，均需确定其左右次序，也就是，均需确定其左右次序，也就是说二叉树的结点次序不是相对于另一结说二叉树的结点次序不是相对于另一结点而言而是确定的。点而言而是确定的。3、试分别画出具有试分别画出具有3个结点的树和个结点的树和3个结点个结点的二叉树的所有不同形态。的二叉树的所有不同形态。三个结点的树如下：只有两种形态三个结点的树如下：只有两种形态/|三个结点的二叉树如下所示：有五种形态：三个结点的二叉树如下所示：有五种形态：(1)(2)

69、(3)(4)(5)/4、已知一棵度为已知一棵度为m的树中有的树中有n1个度为个度为1的结点，的结点，n2个度为个度为2的结点，的结点，.nm个度为个度为m的结点，的结点，问该树中有多少片叶子问该树中有多少片叶子?解：设该树中的叶子数为解：设该树中的叶子数为n0n0个。该树中的总个。该树中的总结点数为结点数为n n个，则有：个，则有： n=nn=n0 0+n+n1 1+n+n2 2+ +n+nm m (1) (1)又又树的结点个数也可以由分枝数得到，即树的结点个数也可以由分枝数得到，即 结点个数树中的分支数结点个数树中的分支数1 1，所以，所以， n=0*nn=0*n0 0+1*n+1*n1 1

70、+2*n+2*n2 2+ +m*n+m*nm m1 1 (2)(2) 联立联立(1)(2)(1)(2)方程组可得：方程组可得： 叶子数为：叶子数为：n n0 0=1+0*n=1+0*n1 1+1*n+1*n2 2+2*n+2*n3 3+.+(m-+.+(m-1)*n1)*nm m 5、一个深度为一个深度为h的满的满k叉树有如下性质：叉树有如下性质：第第h层上的结点都是叶子结点，其余各层上的结点都是叶子结点，其余各层上每个结点都有层上每个结点都有k棵非空子树。如果棵非空子树。如果按层次顺序按层次顺序(同层自左至右同层自左至右)从从1开始对开始对全部结点编号，问：全部结点编号，问：(1)各层的结点

71、数目是多少各层的结点数目是多少?(2)编号为编号为i的结点的双亲结点的结点的双亲结点(若存在若存在)的编号是多少的编号是多少?(3)编号为编号为i的结点的结点的第的第j个孩子结点个孩子结点(若若存在存在)的编号是多少的编号是多少?(4)编号为编号为i的结点的有右兄弟的条件是的结点的有右兄弟的条件是什么什么?其右兄弟的编号是多少其右兄弟的编号是多少?解：解：(1) (1) 层号为层号为h h的结点数目为的结点数目为k kh-1h-1(2) (2) 编号为编号为i i的结点的双亲结点的编号是：的结点的双亲结点的编号是：|_ (i-2)/k _|+1(|_ (i-2)/k _|+1(不大于不大于(i

72、-2)/k(i-2)/k的最大整数。的最大整数。也也 就是就是(i-2)(i-2)与与k k整除的结果整除的结果. .以下以下/ /表示整除。表示整除。(3) (3) 编号为编号为i i的结点的第的结点的第j j个孩子结点编号个孩子结点编号是：是：k*(i-1)+1+j;k*(i-1)+1+j;(4) (4) 编号为编号为i i的结点有右兄弟的条件是的结点有右兄弟的条件是(i-(i-1)1)能能不不被被k k整除右兄弟的编号是整除右兄弟的编号是i+1.i+1. 6 6、高度为、高度为h h的完全二叉树至少有多少个的完全二叉树至少有多少个结点结点? ?至多有多少个结点至多有多少个结点? ?7 7

73、、在具有、在具有n n个结点的个结点的k k叉树叉树(k=2)(k=2)的的k k叉叉链表表示中，有多少个空指针链表表示中，有多少个空指针? ?8 8、假设二叉树包含的结点数据为、假设二叉树包含的结点数据为1 1，3 3，7 7，1212。(1)(1)画出两棵高度最大的二叉树；画出两棵高度最大的二叉树；(2)(2)画出两棵完全二叉树，要求每个画出两棵完全二叉树，要求每个双亲结点的值大于其孩子结点的值。双亲结点的值大于其孩子结点的值。6 6、解：高度为、解：高度为h h的完全二叉树至少有的完全二叉树至少有2 2h-1h-1个结点，至多有个结点，至多有2 2h h-1-1个结点个结点( (也就是也

74、就是满二叉树满二叉树) )。 7 7、解：、解：n n个结点的个结点的K K叉树共有叉树共有n*kn*k个指针个指针域，已使用的指针域为域，已使用的指针域为n-1n-1（树中分枝树中分枝数即为指针的个数）数即为指针的个数）, ,所以空指针的个所以空指针的个数为：数为：n(k-1)+1n(k-1)+18 8解：解：(1)(1)高度最大的两棵二叉树如图：高度最大的两棵二叉树如图：1 1 1 1/ / 3 3 3 3/ / 7 7 7 7/ / 2 2 2 2/ / 12 12 1212 (2)(2)两棵完全二叉树如下：两棵完全二叉树如下：1212 1212/ / / / 7 37 3 7 37 3

75、/ / / / 1 21 2 2 12 1 9 9、以知一组元素为（、以知一组元素为（4646，2525，7878，6262，1212，3737，7070，2929），试画出按元素排），试画出按元素排列次序插入生成的一棵二叉排序树。列次序插入生成的一棵二叉排序树。1010、假设用于通讯的电文由、假设用于通讯的电文由 8 8 个字母组个字母组成，成，A B C D E F G H A B C D E F G H ，字母在电文字母在电文中的出现频率分别为中的出现频率分别为 0.070.07，0.190.19，0.020.02，0.060.06，0.320.32，0.030.03，0.210.21，0.100.10，试设计赫夫曼编码。，试设计赫夫曼编码。