顺序存储的满m叉树
编号为 i 的结点的孩子结点的编号的范围
设其编号为k,在它之前的结点个数等于 i 结点之前的每个结点的孩子数,再加上一个根节点,于是
\[k=(i-1)m+1+1\\(i-1)m+2
\]
最后一个孩子结点的编号
\[k+m-1=(i-1)m+2+m-1\\=(i-1)m+m+1
\]
编号为 k 的结点的双亲结点的编号
假设编号为 k 的结点的双亲结点的编号为 i ,则它们一定满足下列关系
\[(i-1)m+2\le k \le(i-1)m+(m+1)
\]
同时减去2,方便取整
\[(i-1)m\le k-2\le(i-1)m+m-1
\]
两边同时除以m
\[(i-1)\le \frac{k-2}{m}\le(i-1)+1-\frac{1}{m}
\]
对 \(\frac{k-2}{m}\)下取整就得到
\[(i-1)\le \lfloor{\frac{k-2}{m}}\rfloor \le(i-1)\\
即\lfloor{\frac{k-2}{m}}\rfloor=i-1\\
i=\lfloor{\frac{k-2}{m}}\rfloor +1
\]