当前位置:网站首页>满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