二叉树父子节点位置关系_满二叉树的父节点与子节点

作者：Monodyee | 2024-05-07 21:28:45

踩

满二叉树的父节点与子节点

二叉树的每一层节点数量是一个公比为2的等比数列，如第一层也就是根节点的数量是 $\large 2^{0}=1$ ，第二层 $\large 2^{1}=2$ ，第三层 $\large 2^{2}=4$ ，第 $\large k$ 层为 $\large 2^{k-1}$

等比数列的通项公式和求和公式如下

$\large a_{n}=a_{1}\times q^{(n-1)}$

$\large S_{n}=\frac{a_{1}\times (1-q^{n})}{1-q} (q\neq 1)$

假设根节点下标从0开始，第 $\large k$ 层最后一个节点的下标为 $\large 2^{k}-1-1$ ，第一个节点下标为 $\large 2^{k-1}-1$

假设父节点为第 $\large k$ 层的第 $\large m$ 个节点，则其下标为 $\large F=2^{k-1}+m-1-1=2^{k-1}+m-2$

根据二叉树的结构，其子节点得走完第 $\large k$ 层剩下的 $\large 2^{k-1}-m$ 个节点，到下一层后，还得走完左边 $\large m-1$ 个父节点对应的子节点，再加上本身的1一个值，即其左子节点的下标为

$\large \begin{align*} C &= F+(2^{k-1}-m)+(m-1)\times 2+1\\ &= 2^{k-1}+m-2+(2^{k-1}-m)+(m-1)\times 2+1\\ &= 2^{k}+2m-4+1\\ &= 2F+1 \end{align*}$

二叉树中父节点的下标为 $\large F$ ，则其左子节点下标为 $\large 2F+1$ ，右子节点下标为 $\large 2F+2$

参考

声明：本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：【wpsshop博客】