数据结构——常见二叉树的分类（完全二叉树 满二叉树 平衡二叉树 二叉搜索树 红黑树）

一、树的基本概念

二、二叉树

二叉树的定义：二叉树是每个结点最多只能有两个分支的树，左边的分支称为左子树，右边的分支称为右子树。

二叉树的特点：

在非空二叉树中，第层结点总数不超过，深度为的二叉树最多有个个结点（），最少有个结点对于任意一颗二叉树，如果叶结点数为，而度数为2的结点总数为，则=

三、二叉树的分类

（1）完全二叉树

若设二叉树的高度为，除第层外，其他各层的节点数都达到最大个数，第层有叶子节点，并且叶子节点都是从左到右依次排布。（堆为完全二叉树）

（2）满二叉树

除叶子节点外每一个节点都有左右子叶且叶子节点都处在最底层的二叉树。

（3）平衡二叉树（AVL树）

空树或者左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一颗平衡二叉树。

（4）二叉搜索树（二叉查找树、二叉排序树）

若左子树不空，则左树上所有节点的值均小于或等于它的根节点的值。若右子树不空，则右树上所有节点的值君大于或等于它的根节点的值。左右子树也分别为二叉搜索树。

（5）红黑树

节点是红色或黑色。根节点是黑色。所有的叶子节点都是黑色。每个红色节点必须有两个黑色的子节点。（不能出现两个连续的红色节点）从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。