二叉树的学习

发表于 更新于

二叉树的性质

  • 在二叉树的第 i 层上最多有 2 <sup>i-1 </sup> （ i >= 1 ）个节点
  • 深度为 k 的二叉树最多有 2 <sup>k </sup> - 1 （ k >= 1 ）个节点
  • 对任何一个二叉树 如果其终端节点数为 n <sub>0 </sub> ,度为2的节点数为 n <sub>2 </sub> 则 n <sub>0 </sub> = n <sub>2 </sub> + 1
  • 具有 n 个节点的完全二叉树的深度为 log <sub>2 </sub>n + 1
  • 如果对一颗有 n 个节点的完全二叉树（其深度为 log <sub>2 </sub>n + 1 ）的节点按层序编号（从第一层到 log <sub>2 </sub>n + 1 每一层从左到右），则对任意节点 i （1 <= i <= n ）有：
    • 如果 i = 1，则节点 i 是二叉树的根，无双亲节点，如果 i > 1 则其双亲是节点 i / 2
    • 如果 2i > n，则节点 i 无左孩子（节点 i 为叶子节点）；否则其左孩子是节点 2i
    • 如果 2i + 1 > n ,则节点 i 无右孩子；否则其右孩子是节点 2i + 1