source: https://blog.csdn.net/weixin_40646509/article/details/102828109
题目： 一个深度为 h 的满 k 叉树有如下性质：第 h 层上的结点都是叶子结点，其余各层上每个结点都有 k 棵非空子树。如果按层次顺序 (同层自左至右) 从 1 开始对全部结点编号，问： (1) 各层的结点数目是多少? (2) 编号为 i 的结点的双亲结点 (若存在) 的编号是多少? (3) 编号为 i 的结点的第 j 个孩子结点 (若存在) 的编号是多少? (4) 编号为 i 的结点的有右兄弟的条件是什么? 其右兄弟的编号是多少? 答：
(1) 各层的结点数目是多少?
第一层： 1 1 1 第二层： k k k 第三层： k ∗ k k*k k∗k 第四层： k ∗ k ∗ k k*k*k k∗k∗k 第 n 层： k n − 1 k^{ n-1} kn−1
(2) 编号为 i 的结点的双亲结点 (若存在) 的编号是多少?
我先画了一个满三叉树图，方便思考（并不是这道题就是三叉树，题目给的是满 k 叉树，我只是为了方便才选择三叉树的）
假设 i 的位置如上，j 是 i 的第一个子节点。
i 的前面有（i-1）个节点，每一个节点有 k 个子节点，
所以 j 前面有（（i-1）*k）+1 个节点，为什么要加 1 呢，
因为（i-1）*k 没有包括根节点，
所以 j 前面的节点再加一，（（i-1）*k）+2 就是 j 节点的编号。
（ （ i − 1 ） ∗ k ） + 2 （（i-1）*k）+2 （（i−1）∗k）+2
衍生问题，如果问的是 i 的第 k 个孩子的编号怎么办？ 第一个孩子 （ i − 1 ） ∗ k ） + 2 （i-1）*k）+2 （i−1）∗k）+2 那么第 k 个孩子 （ i − 1 ） ∗ k ） + 2 + k − 1 （i-1）*k）+2 + k -1 （i−1）∗k）+2+k−1
(3) 编号为 i 的结点的第 j 个孩子结点 (若存在) 的编号是多少?
再画一个图，把 i 和 j 的位置换一下
这次就是求 i 的父节点 j 的编号，我只会使用数学的推算方法，联想不出来这个题。 因为 i 是 j 子节点，所以可以用 j 来求 i 的编号， i = ( ( j − 1 ) ∗ k ) + 2 i=((j-1)*k)+2 i=((j−1)∗k)+2 i − 2 = ( j − 1 ) ∗ k i-2=(j-1)*k i−2=(j−1)∗k ( i − 2 ) / k = j − 1 (i-2)/k=j-1 (i−2)/k=j−1 j = ( ( i − 2 ) / k ) + 1 j=((i-2)/k)+1 j=((i−2)/k)+1
第三题就是通过第二题得到的结果，逆向推理得到的结果，这是目前我会的唯一方法。
(4) 编号为 i 的结点的有右兄弟的条件是什么? 其右兄弟的编号是多少?
图中红色的就是没有右兄弟，除了红色的节点，其他的节点都有右兄弟
通过图片可以发现，只要 i 不是每个节点的最右节点，
换个说法，只要 i 不是双亲的第 k 个孩子就有右兄弟
对于任意的节点 p ，其 k 个子节点的编号是 p*k+1
则有：
i ! = p ∗ k + 1 i!= p*k+1 i!=p∗k+1
i − 1 ! = p ∗ k i-1 != p*k i−1!=p∗k
最后结果可以写成：
( i − 1 ) % k ! = 0 (i-1)\% k !=0 (i−1)%k!=0
其实就是保证当前节点减一不是 k 的倍数，就可以保证该节点是有右兄弟的。