【数据结构】二叉树的性质随想总结

二叉树的性质

1. 在二叉树的第i层最多有$2^{i-1}$2i−1个节点($i\geq1$i≥1)，其中i为层数
2. 深度为k的二叉树最多多有$2^k-1$2k−1个节点($k\geq1$k≥1)，其中k为树的深度
3. 对于任意一棵二叉树，如果其叶节点为$n_0$n0​, 度为二的节点$n_2$n2​, 则有$n_0 = n_2 +1$n0​=n2​+1

如果树为满二叉树(节点只能在最大的两层出现)

4. 具有n个节点的完全二叉出的深度为$\lfloor\log_2n\rfloor+1$⌊log2​n⌋+1
5. 如果对一棵有n个节点的完全二叉树的节点按层序编号, 则对任意节点i有:
   • 如果i=1则节点i是二叉树的根, 无双亲; 如果i>1则其双亲节点是$\lfloor i /2 \rfloor$⌊i/2⌋
   • 如果2i>n, 则i节点无左孩子(i为叶子节点); 否则其左孩子是节点$2i$2i
   • 如果2i+1>n, 则i无右孩子; 否则其右孩子$2i+1$2i+1

想透彻理解知识需要不断问为什么, 这样才可以深刻记忆和理解知识. 下面是一点随想.

为什么二叉树第i层最多有$2^{i-1}$2i−1个节点??
二叉树, 它最基本的定义是, 一棵最多有两个子节点(孩子)的树, 且它的左右孩子是有序的.
如果是一块满二叉树, 那么, 第一层有1节点, 第二层有2个节点, 第三层有4个节点…可以推出第四层有8个节点…
即1 2 4 8…
根据二叉树的性质又可以表示为:$2^0 \quad 2^1 \quad 2^2 \quad 2^3 ....$20212223.... 它是一个等比数列, 它的q=2, 这是一个很有意义的等比数列.
满二叉树的每一次就代表了二叉树每一层节点的最大值, 因此二叉树每一层最大值是$2^{i-1}$2i−1, i是层数.

为什么深度为k的二叉树最多多有$2^k-1$2k−1个节点???
算满二叉树的k层就代表了, 二叉树k层最多的节点数.
求k层最大的节点的公式, 直接用等比数列前n项和公式推出来emm.

插张等比数列基本公式:

求满二叉树前n层节点的和, 已知$a_1=1和q=2$a1​=1和q=2, 带入$s_n = a_1*(1-q^n)/(1-q)$sn​=a1​∗(1−qn)/(1−q)得$(1-2^n)/(-1)$(1−2n)/(−1)
最终推得: $2^n-1$2n−1

ps:这里的是笔者随想而写的, 并不具有数学推理的严谨性.