二叉树的基本概念
1 二叉树的基本概念
二叉树是一个每个结点最多只能有两个分支的树，左边的分支称之为左子树，右边的分支称之为右子树。
二叉树具有如下特性：
- 在非空二叉树中，第 i层的结点总数不超过 , i>=0；
- 深度为 h 的二叉树最多有2^h - 1个结点(h>=1)，最少有 h 个结点；
- 对于任意一棵二叉树，如果其叶结点数为 N0，而度数为 2 的结点总数为 N2，则 N0=N2+1；
2 二叉树的分类
2.1 完全二叉树
若设二叉树的高度为 h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层有叶子节点，并且叶子结点都是从左到右依次排布，这就是完全二叉树（堆就是完全二叉树）。
2.2 满二叉树
除了叶结点外每一个结点都有左右子节点且叶子结点都处在最底层的二叉树。
2.3 平衡二叉树
平衡二叉树又被称为 AVL 树，它是一颗空树或左右两个子树的高度差的绝对值不超过 1，并且左右两个子树都是一棵平衡二叉树。
2.4 二叉搜索树
二叉搜索树又称二叉查找树、二叉排序树（Binary Sort Tree）。它是一颗空树或是满足下列性质的二叉树：
- 若左子树不空，则左子树上所有节点的值均小于或等于它的根节点的值；
- 若右子树不空，则右子树上所有节点的值均大于或等于它的根节点的值；
- 左、右子树也分别为二叉排序树。
2.5 红黑树
每个节点都带有颜色属性（颜色为红色或黑色）的自平衡二叉查找树，满足下列性质：
- 节点是红色或黑色；
- 根节点是黑色；
- 所有叶子节点都是黑色；
- 每个红色节点必须有两个黑色的子节点。(从每个叶子到根的所有路径上不能有两个连续的红色节点。)
- 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。
参考资料：