2019考研数据结构C语言版详解答案：树和二叉树(1)

考研网

《数据结构(C语言版)》考试内容两大类：概念，算法。自从计算机专业课统考以后，专业课考试题型分为2类，一类选择题，一类综合应用题。要想把数据结构这门专业课复习好，除了做练习题，还要掌握2019考研计算机数据结构(C语言版)基础知识，只有基础知识掌握牢固，才能在做数据结构算法题目时得心应手。本次新东方在线整理了数据结构C语言版答案详解，各位考生可以对照着题目与答案详解，把计算机专业课的数据结构复习一遍。
    6.1一棵度为2的树与一棵二叉树有何区别?
    解：二叉树是颗有序树，但度为2的树则未必有序。
    6.4
一棵深度为H的满k叉树有如下性质：第H层上的结点都是叶子结点，其余各层上每个结点都有k棵非空子树。如果按层次顺序从1开始对全部结点编号，问：
    (1) 各层的结点数目是多少?
    (2) 编号为p的结点的父结点(若存在)的编号是多少?
    (3) 编号为p的结点的第i个儿子结点(若存在)的编号是多少?
    (4) 编号为p的结点有右兄弟的条件是什么?其右兄弟的编号是多少?
    解：
   

    (2)如果p是其双亲的最小的孩子(右孩子)，则p减去根结点的一个结点，应是k的整数倍，该整数即为所在的组数，每一组为一棵满k叉树，正好应为双亲结点的编号。如果p是其双亲的最大的孩子(左孩子)，则p+k-1为其最小的弟弟，再减去一个根结点，除以k，即为其双亲结点的编号。
    综合来说，对于p是左孩子的情况，i=(p+k-2)/k;对于p是右孩子的情况，i=(p-1)/k
    如果左孩子的编号为p，则其右孩子编号必为p+k-1，所以，其双亲结点的编号为
   

    (3)结点p的右孩子的编号为kp+1，左孩子的编号为kp+1-k+1=k(p-1)+2，第i个孩子的编号为k(p-1)+2+i-1=kp-k+i+1。
    (4)当(p-1)%k != 0时，结点p有右兄弟，其右兄弟的编号为p+1。