二叉树

特性：

• 对于一个非空二叉树，其**\(叶子节点数=度为2的节点数+1\)**。
• 非空二叉树的第k层最多有\(2^k-1\)个节点。（根节点处于第1层）
• 高度为H的二叉树最多有\(2^H-1\)个节点。（高度=层数，根节点在第1层，叶子节点在第H层）（满二叉树）
• 对完全二叉树从上到下，从左到右依次编号\(1,2,3,...,n\)，则有以下关系：
  • 最后一个分支节点的编号为：\(\left\lfloor n/2 \right\rfloor\)。如果\(i<\left\lfloor n/2\right\rfloor\)，则节点i为非叶子节点，否则为叶子节点。
  • 叶子节点只能出现在最后两层。
  • 若存在度为1的节点，则最多只可能有一个。且该节点只有左孩子，没有右孩子。
  • 若总节点数n为奇数，则每个非叶子节点都有左右孩子。如果总节点数n为偶数，则编号最大的非叶子节点只有左孩子，没有右孩子。其余非叶子节点都有左右孩子。
  • 当i>1时，节点i的双亲节点编号为：\(\left\lfloor i/2\right\rfloor\)。（如果i==0，那么节点i就是整个树的根节点。）