1. 二叉树性质

• 二叉树最多有两个子树。
• 二叉树第i层最多有$2^{i-1}$个节点
• 深度为k的二叉树至多有$2^k-1$个节点
• 对任一二叉树，叶子节点为n0，度为2的节点为n2，则n0=n2+1
• 包含n个结点的二叉树的高度至少为$log_2(n+1)$。

2. 二叉树分类

• 完全二叉树——叶子节点都在最底下两层，最后一层的叶子节点都靠左排列，并且除了最后一层，其他层的节点个数都要达到最大，这种二叉树叫作完全二叉树。
• 满二叉树——叶子节点全都在最底层，除了叶子节点之外，每个节点都有左右两个子节点，这种二叉树就叫作满二叉树，他是一种特殊的完全二叉树。
• 平衡二叉树——平衡二叉树又被称为AVL树（区别于AVL算法），它是一棵二叉排序树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

3. 二叉树的遍历

• 前序遍历

  graph LR
  结点-->左子树
  左子树-->右子树
  

• 中序遍历

  graph LR
  左子树-->结点
  结点-->右子树
  

• 后序遍历

  graph LR
  左子树-->右子树
  右子树-->结点
  

• 层次遍历

  graph LR
  第一层-->第二层
  第二层-->...
  ... -->第K层