树的定义与性质

定义

高度/深度
Alt text

  • 满二叉树
  • 完全二叉树

性质

  • 在n个节点构成的二叉树中，叶结点的个数等于度为二节点的个数+1

  • 对于完全二叉树

  • 对于一颗具有n个节点的完全二叉树，其非叶节点个数为n/2（向下取整），叶结点个数为n/2（向上取整）

  • n个结点的完全二叉树的高度为logn（向下取整）