当前位置：网站首页>满k叉树编号为 i 的节点的孩子编号公式推导

满k叉树编号为 i 的节点的孩子编号公式推导

2022-06-11 16:58:00 【wozaizhe.55】

满k叉树编号为i的节点第一个孩子的编号 j 满足 j = (i - 1) * k + 2 ;

设: 节点 i 处在该 m 叉树的第 h层, (h = 1, 2, 3...)

则前 h - 1 层共有 $N1 =\frac{k^{h-1}-1}{k-1}$ 个节点

同理前 h 层共有 $N2 =\frac{k^{h} - 1}{k -1}$ 个节点

显然 i 是第 h 层的 i -N1 个节点, 即节点i 有 i -N1 - 1 个左兄弟

故节点i 的第一个孩子 j 有 (i -N1 -1)*k 个左兄弟

由此可得 j在第h + 1 层中的位置为 (i -N1 -1)*k + 1

那么节点j 在整棵满 k叉树的编号为 N2 + (i -N1 -1)*k + 1

即 $j =\frac{k^{h} - 1}{k -1} +(i -\frac{k^{h-1} -1}{k-1} -1)*k + 1$

整理可得: j = (i - 1) * k + 2

版权声明
本文为[wozaizhe.55]所创，转载请带上原文链接，感谢
https://blog.csdn.net/wozaizhe56/article/details/82765024