[回忆梳理] 2.二叉树的性质

二叉树的性质

二叉树的性质可以直接记忆，在理解的基础上记忆更好，如果暂时不能理解，就先记忆，便于以后直接使用

tip:以下出现所有【x】符号,均表示为不大于x的最大整数

• 二叉树的第 i 层之多有2^(i-1)次方个结点（i >= 1）
• 深度为 k 的二叉树至多有 2^(k-1)个结点（k >= 1）
• 对于任何一棵二叉树 T ,如果其叶子结点数为 n0, 度为2的结点树为 n2,则 n0 = n2 +1
• 具有 n 个结点的完全二叉树的深度为【log2n】 + 1 （【x】符号为不大于x的最大整数，log2n,是以2底的n对数）
• 若对一棵有 n 个结点的完全二叉树（深度为【log2n】 + 1）的节点按层序标号（从第一层到第【log2n】 + 1 层，每层从左到右),对任意节点i（1<= i <= n）有如下性质
  • 如果 i=1，则结点 i 是二叉树的根，无双亲，如果 i>1,则其双亲是节点【i/2】
  • 如果 2i>n,则结点 i 无左孩子(节点 i 为叶子节点), 否则其左孩子是节点 2i
• 如果 2i+1>n, 则结点 无右孩子；否则其有孩子节点为 2i + 1
  下一篇 [回忆梳理] 二叉树存储