满m叉树编号为i的结点的子结点编号推导

满m叉树编号为i的结点的子结点编号推导

习题正文：设有一颗满m叉树：

1）求编号为i的双亲结点编号（若存在）

2）求编号为i的结点的第k个孩子（若存在）编号

3）编号为i的结点有右兄弟的条件

先求问题2）

我们可以找到这样一颗完全m叉子树，这颗树按编号排序的最后一个结点是结点i的第一个孩子，这个不难想象。我们只需要求出这颗子树的结点总数即可解决问题2。这不难求解

设结点总数为n，由于结点i是完全m叉子树中最后一个非叶结点，所以非叶结点数有i个，其中有i-1个度为m的结点和一个度为1的结点（即结点i）。根据结点总数比度大1的原则，我们可以列出方程：

[(i-1)m+1]+1=n

所以n=m(i-1)+2

到此我们就求出了结点i的第一个孩子的编号n = m(i-1)+1+1，要想求第k个孩子的结点编号，可以照上同理求出：n=(i-1)m+k+1

再看问题1:

把问题2的n和i对调求出编号为i的父结点编号n=⌊(i-2)/m⌋+1

问题3：

节点 i 有右兄弟，当且仅当 i 不是其双亲 j 的最后一个孩子（即第 m 个孩子）:

i = m(j-1) + k + 1，k不等于m，即i ≠ m * j + 1，(i - 1) / m ≠ j，

因为j是整数，所以也可以表示成(i - 1) % m ≠ 0