当前位置: 首页> 健康> 知识 > 数据结构----高度为h的m叉树(记录一题)

数据结构----高度为h的m叉树(记录一题)

时间:2025/7/30 22:01:33来源:https://blog.csdn.net/weixin_69884785/article/details/141906432 浏览次数:0次

(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

关键字:数据结构----高度为h的m叉树(记录一题)

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: