一棵深度为H的满k叉树有如下性质:第H层上的结点都是叶子结点,其余各层上每个结点都有k棵非空子树,如果按层次自上至下,从左至右顺序从1开始对全部结点编号,回答下列问题:(1)各层的结点数目是多少?(2)编号为n的结点的父结点如果存在,编号是多少?(3)编号为n的结点的第i个孩子结点如果存在,编号是多少?(4)编号为n的结点有有兄弟的条件是什么?其右兄弟的编号是多少?


一棵深度为H的满k叉树有如下性质:第H层上的结点都是叶子结点,其余各层上每个结点都有k棵非空子树,如果按层次自上至下,从左至右顺序从1开始对全部结点编号,回答下列问题:(1)各层的结点数目是多少?(2)编号为n的结点的父结点如果存在,编号是多少?(3)编号为n的结点的第i个孩子结点如果存在,编号是多少?(4)编号为n的结点有有兄弟的条件是什么?其右兄弟的编号是多少?

正确答案:(1)第i层上的结点数目是mi-1。(2)编号为n的结点的父结点如果存在,编号是((n-2)/m)+1。(3)编号为n的结点的第i个孩子结点如果存在,编号是(n-1)*m+i+1。(4)编号为n的结点有右兄弟的条件是(n-1)%m≠0。其右兄弟的编号是n+1。


Tag:数据结构 结点 编号 时间:2022-05-19 20:32:54