资源描述：
《中南大学数据结构与算法第6章树和二叉树课后作业答案》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第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为根的子树的深
2、度是多少?(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，均需确定其左右次序，也就是说二叉树的结点次序不是相对于另一结点而
3、言而是确定的。6.3试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。答： 三个结点的树如下：只有两种形态 ○ ○ /
4、 ○○ ○
5、 ○ 三个结点的二叉树如下所示：有五种形态： (1) (2) (3) (4) (5) ○ ○ ○ ○ ○ / / /
6、○ ○ ○ ○ ○ ○ / / ○ ○ ○ ○ 6.4已知一棵度为m的树中有n1个度为1的结点，n2个度为2的结点，...nm个度为m的结点，问该树中有多少片叶子?解： 设该树中的叶子数为n0个。该树中的总结点数为n个，则有： n=n0+n1+n2+…+nm(1)又有除根结点外，树中其他结点都有双亲结点，且是唯一的(由树中的分支表示)
7、，所以，有双亲的结点数为： n-1=0*n0+1*n1+2*n2+…+m*nm(2) 联立(1)(2)方程组可得： 叶子数为：n0=1+0*n1+1*n2+2*n3+...+(m-1)*nm6.5一个深度为h的满k叉树有如下性质：第h层上的结点都是叶子结点，其余各层上每个结点都有k棵非空子树。如果按层次顺序(同层自左至右)从1开始对全部结点编号，问： (1)各层的结点数目是多少? (2)编号为i的结点的双亲结点(若存在)的编号是多少? (3)编号为i的结点的第j个孩子结点(若存在)的编号是多少? (4)编号为i的结点的有右兄弟的条件是什么?其右兄弟的编号
8、是多少?解： (1)层号为h的结点数目为kh-1 (2)编号为i的结点的双亲结点的编号是：
9、_(i-2)/k_
10、+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叉链表表示中，有多少个
11、空指针?解： 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
