中南大学数据结构与算法第6章树和二叉树课后作业答案

第6章树(基础知识)习题练习答案6.1.假设在树中，结点x是结点y的双亲时,用(x,y)来表示树边.已知一棵树边的集合为{(i,m),(i,n),(e,i),(b,e),(b,d),(a,b),(g,j),(g,k),(c,g),(c,f),(h,l),(c,h),(a,c)}用树形表示法出此树，并回答下列问题：(1)哪个是根结点? (2)哪些是叶结点? (3)哪个是g的双亲? (4)哪些是g的祖先?(5)哪些是g的孩子? (6)哪些是e的子孙? (7)哪些是e的兄弟?哪些是f的兄弟?(8)结点b和n的层次各是多少? (9)树的深度是多少? (10)以结点c为根的子树的深度是多少? (11) 树的度数是多少?答：a是根结点；dmnfjkl是叶结点；c是g的双亲；c,a是g的祖先；j,k是g的孩子；imn是e的子孙；d是e的兄弟；g,h是f的兄弟；b的层次是2；n的层次是5；树的深度是5；以c为根的子树深度是3；树的度数是3；6.2 一棵度为2的有序树与一棵二叉树有何区别?答：一棵度为二的有序树与一棵二叉树的区别在于:有序树的结点次序是相对于另一结点而言的，如果有序树中的子树只有一个孩子时，这个孩子结点就无须区分其左右次序，而二叉树无论其孩子数是否为2，均需确定其左右次序，也就是说二叉树的结点次序不是相对于另一结点而言而是确定的。

6.3 试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。

答：三个结点的树如下：只有两种形态○○/ \ |○ ○○|○三个结点的二叉树如下所示：有五种形态：(1) (2) (3) (4) (5)○○○○○/ \ / / \ \○○○○○○/ \ / \○○○○6.4 已知一棵度为m的树中有n1个度为1的结点，n2个度为2的结点，...n m个度为m的结点，问该树中有多少片叶子?解：设该树中的叶子数为n0个。

该树中的总结点数为n个，则有：n=n0+n1+n2+…+n m (1)又有除根结点外，树中其他结点都有双亲结点，且是唯一的(由树中的分支表示)，所以，有双亲的结点数为：n-1=0*n0+1*n1+2*n2+…+m*n m (2)联立(1)(2)方程组可得：叶子数为：n0=1+0*n1+1*n2+2*n3+...+(m-1)*n m6.5一个深度为h的满k叉树有如下性质：第h层上的结点都是叶子结点，其余各层上每个结点都有k棵非空子树。

如果按层次顺序(同层自左至右)从1开始对全部结点编号，问：(1)各层的结点数目是多少?(2)编号为i的结点的双亲结点(若存在)的编号是多少?(3)编号为i的结点的第j个孩子结点(若存在)的编号是多少?(4)编号为i的结点的有右兄弟的条件是什么? 其右兄弟的编号是多少?解：(1) 层号为h的结点数目为k h-1(2) 编号为i的结点的双亲结点的编号是：|_ (i-2)/k _|+1(不大于(i-2)/k的最大整数。

也就是(i-2)与k整除的结果.以下/表示整除。

(3) 编号为i的结点的第j个孩子结点编号是：k*(i-1)+1+j;(4) 编号为i的结点有右兄弟的条件是(i-1)能被k整除右兄弟的编号是i+1.6.6高度为h的完全二叉树至少有多少个结点?至多有多少个结点?解：高度为h的完全二叉树至少有2h-1个结点，至多有2h-1个结点(也就是满二叉树)。

6.7 在具有n个结点的k叉树(k>=2)的k叉链表表示中，有多少个空指针?解：n个结点的K叉树共有n*k个指针域，已使用的指针域为n-1,所以空指针的个数为：n(k-1)+1;6.8 假设二叉树包含的结点数据为1，3，7，12。

(1)画出两棵高度最大的二叉树；(2)画出两棵完全二叉树，要求每个双亲结点的值大于其孩子结点的值。

解：(1)高度最大的两棵二叉树如图：○1○1/ \○3○3/ \○7○7/ \○2 ○2/ \○12 ○12(2)两棵完全二叉树如下：○12○12/ \ / \○7 ○3○7 ○3/ \ / \○1 ○2○2 ○16.9试找出分别满足下面条件的所有二叉树：(1)前序序列和中序序列相同；(2)中序序列和后序序列相同；(3)前序序列和后序序列相同；(4)前序、中序、后序序列均相同。

答：(1) 前序序列和中序序列相同的二叉树是：空二叉树或没有左子树的二叉树(右单支树)。

(2) 中序序列和后序序列相同的二叉树是：空二叉树或没有右子树的二叉树(左单支树)。

(3) 前序序列和后序序列相同的二叉树是：空二叉树或只有根的二叉树。

(4) 前序、中序、后序序列均相同的二叉树：空树或只有根结点的二叉树。

6.10 试采用顺序存储方法和链接存储方法分别画也6.30所示各二叉树的存储结构。

解：(1)顺序存储方法：二叉树(a):下标0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21__________________________________________________________________bt | |1 |2 |∮|∮|3 |∮|∮|∮|∮|4 |∮|∮|∮|∮|∮|∮|∮|∮|∮|∮| 5|__________________________________________________________________二叉树(b):下标0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 ____________________________________________________________________________ ______bt| |1 |∮|2 |∮|∮|3 |∮|∮|∮|∮|∮|∮|4 |∮|∮|∮|∮|∮|∮|∮|∮|∮|∮|∮|∮|5 |____________________________________________________________________________ ______二叉树(c):下标0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 ____________________________________________________________________________ ___bt | |1 |∮|2 |∮|∮|3 |4 |∮|∮|∮|∮|5 |6 |∮|∮|∮|∮|∮|∮|∮|∮|∮|∮|7 |8 | ____________________________________________________________________________ ___二叉树(d):下标0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15┌─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┐bt││1 │2 │3 │4 │∮│5 │6 │∮│7 │∮│∮│∮│∮│ 8│9 │└─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┘(2)链式存储结构：二叉树(a):↓root┌─┬─┬─┐││1 │∧│└┼┴─┴─┘↓┌─┬─┬─┐│∧│2 ││└─┴─┴┼┘↓┌─┬─┬─┐││3 │∧│└┼┴─┴─┘↓┌─┬─┬─┐│∧│4 ││└─┴─┴┼┘↓┌─┬─┬─┐│∧│5 │∧│└─┴─┴─┘二叉树(b):↓root┌─┬─┬─┐│∧│1││└─┴─┴┼┘↓┌─┬─┬─┐││2 │∧│└┼┴─┴─┘↓┌─┬─┬─┐│∧│3 ││└─┴─┴┼┘↓┌─┬─┬─┐││4 │∧│└┼┴─┴─┘↓┌─┬─┬─┐│∧│5 │∧│└─┴─┴─┘二叉树(c):↓root┌─┬─┬─┐│∧│1 ││└─┴─┴┼┘↓┌─┬─┬─┐││2 ││└┼┴─┴┼┘↓↓┌─┬─┬─┐┌─┬─┬─┐││3 │││∧│4 │∧│└┼┴─┴┼┘└─┴─┴─┘↓↓┌─┬─┬─┐ ┌─┬─┬─┐││5 ││ │∧│6 │∧│└┼┴─┴┼┘ └─┴─┴─┘↓↓┌─┬─┬─┐┌─┬─┬─┐│∧│7 │∧││∧│8 │∧│└─┴─┴─┘└─┴─┴─┘二叉树(d):↓root┌─┬─┬─┐││1 ││└┼┴─┴┼┘↓↓┌─┬─┬─┐┌─┬─┬─┐││2 │∧│││3 ││└┼┴─┴─┘└┼┴─┴┼┘↓↓↓┌─┬─┬─┐┌─┬─┬─┐┌─┬─┬─┐│∧│4 │││∧│5 │∧│││6 ││└─┴─┴┼┘└─┴─┴─┘└┼┴─┴┼┘↓↓↓┌─┬─┬─┐┌─┬─┬─┐┌─┬─┬─┐│∧│7 │∧││∧│8 │∧││∧│9 │∧│└─┴─┴─┘└─┴─┴─┘└─┴─┴─┘6.11 分别写出图6.30(下图)所示各二叉树的前序、中序和后序序列。

解：(a)前序序列：12345中序序列：24531后序序列：54321(b)前序序列：12345中序序列：13542后序序列：54321(c)前序序列：12357864中序序列：17583524后序序列：78563421(d)前序序列：124735689中序序列：742153896后序序列：7425896316.12若二叉树中各结点的值均不相同，则由二叉树的前序序列和中序序列，或由其后序序列和中序序列均能唯一地确定一棵二叉树，但由前序序列和后序序列却不一定能唯一地确定一棵二叉树。

(1)已知一棵二叉树的前序序列和中序序列分别为ABDGHCEFI和GDHBAECIF，请画出此二叉树。

(2)已知一棵二叉树的在序序列和后序序列分别为BDCEAFHG和DECBHGFA，请画出此二叉树。

(3)已知一棵二叉树的前序序列和后序序列分别为AB和BA，请画出这两棵不同的二叉树。

解：(1)已知二叉树的前序序列为ABDGHCEFI和中序序列GDHBAECIF，则可以根据前序序列找到根结点为A，由此，通过中序序列可知它的两棵子树包分别含有GDHB和ECIF结点，又由前序序列可知B和C分别为两棵子树的根结点...以此类推可画出所有结点：○A/ \○B ○C/ / \○D○E○F/ \ /○G ○H○I(2)以同样的方法可画出该二叉树：○A/ \○B ○F\ \○C○G/ \ \○D ○E○H(3)这两棵不同的二叉树为：○A○A/ \○B○B6.13对二叉树中的结点进行按层次顺序(每一层自左至右)的访问操作称为二叉树的层次遍历，遍历所得到的结点序列称为二叉树层次序列。

现已知一棵二叉树的层次序列为ABCDEFGHIJ,中序序列为DBGEHJACIF，请画出此二叉树。

解：类似于上一题的分析方法，可画出二叉树的所有结点：○A/ \○B○C/ \ \○D ○E○F/ \ /G○H○ ○I\○J6.14 试画出图6.30(下图)所示各二叉树的前序、中序和后序线索树及相应的线索链表。