首页 > 试题广场 >

一棵深度为H的满k叉树有如下性质：第H层上的结点都是叶子结点

[问答题]

一棵深度为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，所以，其双亲结点的编号为