我们知道在完全二叉树中 :

      (孩子下标-1)/ 2 ==  父节点下标

        父节点下标*2+1 = 左孩子节点

        父节点下标*2+2 = 右孩子节点        

        那我们该怎样理解以便之后不容易忘记呢?

        以下是我的思考过程:观察下边的完全二叉树的下标规律

数据结构-思考完全二叉树-LMLPHP

        小结论一:首先可以轻易看出,完全二叉树的左孩子都是奇数,右孩子都是偶数

        我们想象俩个相邻的数字,一个奇数一个偶数 ,那么这俩个数除以2得到的商有俩种情况:

        若第一个数字为奇数 第二个数字为偶数(例如7,8)那么除以二后他俩的数字关系是差1

        若第一个数字为偶数 第二个数字为奇数(例如8,9)那么除以二后他俩的数字是相同的

        小结论二:俩个相邻的数字如果第一个是偶数,那么经过除以2的操作后结果是一样的

        还是观察完全二叉树的结构,会发现孩子节点下标每走俩格,父节点就对应的走一格

        ,他们的变化率恒定为俩倍关系,

        小结论三:孩子节点的变化与父节点的变化关系为二倍,只要在映射关系中符合二倍关系,只需证明某一个特殊值符合条件,即可证明式子的普适性

        我们找一个特殊的孩子节点:最右下角的节点

数据结构-思考完全二叉树-LMLPHP

         我们如果设最后一行节点的数量为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

        由小结论三个只式子成立  

        

05-29 15:29