当前位置：网站首页>Derivation of child numbering formula for nodes numbered I in full k-ary tree

Derivation of child numbering formula for nodes numbered I in full k-ary tree

2022-06-11 17:05:00 【wozaizhe. fifty-five】

full k The fork tree number is i The number of the first child of the node j Satisfy j = (i - 1) * k + 2 ;

set up : node i In this m The second of a fork tree h layer , (h = 1, 2, 3...)

be front h - 1 There are layers in total $N1 =\frac{k^{h-1}-1}{k-1}$ Nodes

Empathy front h There are layers in total $N2 =\frac{k^{h} - 1}{k -1}$ Nodes

obviously i It's No h Layer of i -N1 Nodes , namely node i Yes i -N1 - 1 A left brother

So node i The first child of j Yes (i -N1 -1)*k A left brother

It can be obtained. j In the h + 1 The position in the layer is (i -N1 -1)*k + 1

that node j The whole tree is full k The number of the fork tree is N2 + (i -N1 -1)*k + 1

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

You can get : j = (i - 1) * k + 2

版权声明
本文为[wozaizhe. fifty-five]所创，转载请带上原文链接，感谢
https://yzsam.com/2022/162/202206111658245584.html