树和二叉树

二叉树的性质

以下为数据结构学习中关于二叉树的所有性质

  • 二叉树的第i(i>=)层上最多有2^(i-1)个节点
  • 高度为h的二叉树上至多有2^h-1个结点
  • 包含n个结点的二叉树的高度至少为[log2(n+1)],最高为h
  • 任意一棵二叉树中，若叶结点的数量为n0，度为2的结点数量为n2，则n0 = n2 + 1成立
  • 具有n个结点的完全二叉树的高度为[log2(n+1)]
  • 一棵包含n个结点的完全二叉树，对树中的节点按从上到下、从左到右的顺序从0到n-1编号，设树中某个结点的编号为i，0<=i < n,则有以下关系成立:
    • 当i=0时，该结点为二叉树的根
    • 若i>0，则该结点的双亲结点的编号为[(i-1)/2]
    • 若2i+1 =< n，则该结点有左孩子，该左孩子结点的编号为2i+1
    • 若2i+2 < n，则该结点有右孩子，该右孩子的编号为2i+2

二叉树的实现

以下代码都用C++实现 

1
class