二叉树的种类

完全二叉树

一颗二叉树，假设其深度为d(d>1)。除第d层外，其他各层的节点数目均已达最大值，且第d层所有节点从左向右连续地紧密排列，这样的树称为完全二叉树。其中满二叉树的定义是所有叶节点都在最底层的完全二叉树。

平衡二叉树(AVL树)

当且仅当任何节点的两棵子树的高度差不大于1的二叉树

平衡二叉树的旋转
红黑树: 一种自平衡的平衡二叉树。

排序二叉树(Binary Search Tree)

也称二叉搜索树、有序二叉树。其要求如下：
- 若左子树不空，则左子树所有节点的值均小于它的根节点的值
- 若右子树不空，则右子树所有节点的值均大于它的根节点的值
- 左、右子树也分别为二叉排序树。