一棵高度为h的满m叉树有如下性质：根结点所在层次为第1层，第h层上的结点都是叶结点，其余各层上每个结点都有m棵非空子树。若按层次自顶向下、同一层自左向右，从1开始对全部结点编号，求各层结点数、编号i结点的双亲编号、第k个孩子编号，以及有右兄弟的条件和右兄弟编号。

[tag_link]

参考答案

第r层有m^(r−1)个结点；parent(i)=floor((i−2)/m)+1(i>1)；child_k(i)=(i−1)m+k+1；有右兄弟当该结点不是双亲的第m个孩子且右兄弟存在，此时编号为i+1。

推导过程

按层序编号时第r层容量为m^(r−1)。第i结点的孩子编号连续为(i−1)m+2至(i−1)m+m+1，反解得到双亲公式；非第m孩子即(i−1)%m≠0。

评分要点

写出层容量；推导父/子下标；说明边界、右兄弟存在性。

易错点

忽略编号从1开始或把不存在的孩子当成右兄弟。