题目：一棵高度为h的满m叉树有如下性质：根结点所在层次为第1层，第h层上的结点都是叶结点，其余各层上每个结点都有m棵非空子树，若按层次自顶向下，同一层自左向右，顺序从1开始对全部结点进行编号，试问：
（1）各层的结点个数是多少？
（2）编号为i的结点的双亲结点（若存在）的编号是多少？
（3）编号为i的结点的第k个孩子结点（若存在）的编号是多少？
（4）编号为i的结点有右兄弟的条件是什么？其右兄弟结点的编号是多少？
分析：考察对于树的性质的理解。
（1）因为是满m叉树。满m叉树意味着每个结点都有m个孩子。那么第1层有一个结点，是根节点。第2层是根节点的m个孩子。第3层是第二层每个结点的m个孩子的总和，是m^2个。....第h层是m^(h-1)个结点。
（2）给定一个孩子结点的编号,我们希望能够求出它的双亲结点的编号。换句话说，我们希望找到孩子结点编号与双亲结点编号之间的函数关系（纳尼？竟然是函数关系？没错，就是函数关系，嗯嗯！）
那怎么找到这个函数关系呢？我们可以利用的信息有两个：
一个是前2层的结点编号。如果我们以孩子结点的编号作为自变量，那么我们可以写出下面的等式：f(2)=1， f(3)=1,...f(m)=1, f(m+1)=1
另一个是每层与相邻层之间是m倍的关系（第一题可以看出来吧？）那么，如果孩子结点的编号是i，那么双亲结点要除以m。考虑到一个双亲有多个孩子，除以m之后会出现小数，我们希望得到的是整数编号，所以我们有一个取整的操作。不妨令它们之间的关系为 ⌊ (i+a)/m⌋ + b. （emmm，这里为什么是向下取整呢？）
那么，我们利用前两层的等式把a,b这两个参数确定下来就可以找到孩子与双亲结点之间的函数关系了。
于是，我们就观察！当i=2时，双亲为1，i=3是，双亲为1，看起来似乎这个双亲编号不受i的影响，那么必然就是b了。也就是b=1.
我们继续观察，i=m时，双亲为1，要使(m+a)/m为0，则a至少为-1，再看i=m+1时，双亲仍为1，此时a至少为-2才行了。所以a=-2,那么双亲结点的编号就是⌊ (i-2)/m⌋ + 1.
我们再找个结点试试看，我们的函数是否对。比如，第3层的第一个结点是m+2,双亲是⌊ m/m⌋ + 1=2,对了。不妨再试
试m+3,双亲也是2，也对。那么，就是这个函数关系了。
（3）做完第二题，让你做第3题，你是不是有了自己的一些想法了呢？对，也是类似的做法。不过这里的自变量是双亲编号，f(1)=k+1, 好像还不够，那么我们不妨再加上一层。f(2) = m+k+1, 我们的函数关系可以设为 (i+a)*m + b。这里不需要取整了，因为没有小数呀。
那么a,b分别取多少呢？通过观察，可以看出来，b=k+1,a=-1.所以，第k个孩子结点的编号就是（i-1）*m+k+1
那么找个结点来试试吧！比如，编号为2的第3个孩子是m+4,确实是呢。
（4）一个结点，有右兄弟的条件是什么？它本身不是双亲的最右一个孩子结点呗。
那么如果一个孩子结点的编号是i,它的双亲结点编号是多少来着？这是第（2）问。双亲结点编号是⌊ (i-2)/m⌋ + 1.
那么如果一个结点的编号是⌊ (i-2)/m⌋ + 1，它的第m个孩子的编号是多少来着？这是第（3）问。将双亲结点编号带入，得⌊ (i-2)/m⌋ *m+m+1.所以，条件就是i<⌊ (i-2)/m⌋ *m+m+1。那么i的右兄弟是谁呢？i+1呗。
我们也可以找个点试一试。比如，编号为m的结点，它的双亲的第m个结点是m+1,m有右兄弟。
以上。
转载本文请联系原作者获取授权，同时请注明本文来自邵明玉科学网博客。
链接地址：https://wap.sciencenet.cn/blog-3417649-1286855.html?mobile=1
收藏
