二叉树

特性：

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