(1)各层结点个数:

类比二叉树可得:

所以各层结点个数:

(2)编号为i的结点的双亲结点(若存在)的编号是多少?

若存在表示:i>1(根节点没有双亲结点)

假设i结点有左兄弟和右兄弟,则从第1个结点~第i-1个结点总共有:

(i-1)*m+1个结点,这里的"+1",指的是根节点。

所以结点 i 第1个子女的编号为:

(i-1)*m+1+1=(i-1)*m+2。

设j=(i-1)*m+2。j 就是 i(双亲结点)的第1个子女编号,那么要求双亲结点的编号,那么就通过 j 反求 i 即可:

j=(i-1)*m+2

i =\left \lfloor (j-2)/m \right \rfloor+1

现在根据题目的意思变一下,我们这里的 j ,即题目中 的 i。 

\left \lfloor (i-2)/m \right \rfloor+1

答案:

(3)编号为 i 的结点的第k个孩子结点(若存在)的编号是多少?

由第(2)问可知,i 的第1个结点是(i-1)*m+1+1,那么第k个孩子就是(i-1)*m+1+k。

(4)编号为 i 的结点有右兄弟的条件是什么?其右兄弟结点的编号是多少? 

当结点 i 不是其双亲的第m个子女时才有右兄弟。假设结点 j 的第 m 个子女是 结点 i:

i =(j-1)*m+1+m= j*m+1

变形一下:

i-1 = j*m。

表示 i-1 是 m的整数倍,即 i-1%m=0。现在结点 i 不是双亲的第m个子女时才有右兄弟,所以:

i-1%m\neq0即可。

结点 i < j*m+1 才有右兄弟,其右兄弟为i+1

Logo

魔乐社区(Modelers.cn) 是一个中立、公益的人工智能社区,提供人工智能工具、模型、数据的托管、展示与应用协同服务,为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作,由全产业链共同建设、共同运营、共同享有,推动国产AI生态繁荣发展。

更多推荐