首页 > 代码库 > 深度为H的满k叉树
深度为H的满k叉树
<pre>
一棵深度为H的满k叉树有如下性质:
第H层上的结点都是叶子结点,其余各层上每个结点都有k棵非空子树。如果按层次顺序从1开始对全部结点编号,问:
(1) 编号为p的结点的父结点(若存在)的编号是多少?
如果p是其双亲的最小的孩子(右孩子),则p减去根结点的一个结点,应是k的整数倍,该整数即为所在的组数,每一
组为一棵满k叉树,正好应为双亲结点4的编号。如果p是其双亲的最大的孩子(左孩子),则p+k-1为其最小的弟弟,再减
去一个根结点,除以k,即为其双亲结点的编号。综合来说,对于p是左孩子的情况,i=(p+k-2)/k;对于p是右孩子的情况,
i=(p-1)/k 如果左孩子的编号为p,则其右孩子编号必为p+k-1,所以,其双亲结点的编号为向下取整,如1.5向下取整为1
(2) 编号为p的结点的第i个儿子结点(若存在)的编号是多少?
结点p的右孩子的编号为kp+1,左孩子的编号为kp+1-k+1=k(p-1)+2,第i个孩子的编号为k(p-1)+2+i-1=kp-k+i+1。
(3) 编号为p的结点有右兄弟的条件是什么?其右兄弟的编号是多少?
当(p-1)%k != 0时,结点p有右兄弟,其右兄弟的编号为p+1。
</pre>
深度为H的满k叉树
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。