我们知道在完全二叉树中 :
(孩子下标-1)/ 2 == 父节点下标
父节点下标*2+1 = 左孩子节点
父节点下标*2+2 = 右孩子节点
那我们该怎样理解以便之后不容易忘记呢?
以下是我的思考过程:观察下边的完全二叉树的下标规律
小结论一:首先可以轻易看出,完全二叉树的左孩子都是奇数,右孩子都是偶数
我们想象俩个相邻的数字,一个奇数一个偶数 ,那么这俩个数除以2得到的商有俩种情况:
若第一个数字为奇数 第二个数字为偶数(例如7,8)那么除以二后他俩的数字关系是差1
若第一个数字为偶数 第二个数字为奇数(例如8,9)那么除以二后他俩的数字是相同的
小结论二:俩个相邻的数字如果第一个是偶数,那么经过除以2的操作后结果是一样的
还是观察完全二叉树的结构,会发现孩子节点下标每走俩格,父节点就对应的走一格
,他们的变化率恒定为俩倍关系,
小结论三:孩子节点的变化与父节点的变化关系为二倍,只要在映射关系中符合二倍关系,只需证明某一个特殊值符合条件,即可证明式子的普适性
我们找一个特殊的孩子节点:最右下角的节点
我们如果设最后一行节点的数量为m,那么我们可以轻易的得出:
第一行到倒数第二行的节点数和为m-1,道理类似与一个绳子无限折半;
树的结点数为2m-1 ;
最后一个结点的下标为2m-2(数组从0开始算);显然为偶数
倒数第二个结点的下标为2m-3;显然为奇数
倒数第二行的最后一个结点(以上俩个结点的父结点)下标为m-2;
根据小结论2,对俩个孩子结点处理,处理为第一个偶数第二个奇数:
具体方式为-1;
左孩子-1 = 2m-4 为偶数
右孩子-1 = 2m-3 为奇数
观察可得(左孩子或右孩子-1)/2 = 父结点;特殊值成立
因为该式子孩子权重为0.5,父结点权重为1 符合小结论三,固(孩子下标-1)/ 2 == 父节点下标成立。
核心:知道-1的目的为让俩个数的关系变为第一个为偶数的相邻的数字
至于以下俩条:
父节点下标*2+1 = 左孩子节点
父节点下标*2+2 = 右孩子节点
我们继续用特殊数值延伸到普遍的办法:
父结点:m-2; 左孩子2m-3 右孩子2m-2
父结点*2 = 2m-4
父结点(2m-4)+1 = 左孩子 = 2m-3
父节点(2m-4)+2 = 右孩子 = 2m-2
由小结论三个只式子成立