二叉树的特点：
（1）非空二叉树只有一个根结点；
（2）每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。

二叉树的基本性质：

（1）在二叉树的第k层上，最多有2k-1(k≥1)个结点；

（2）深度为m的二叉树最多有2m-1个结点；

（3）度为0的结点（即叶子结点）总是比度为2的结点多一个；

（4）具有n个结点的二叉树，其深度至少为[log2n]+1,其中[log2n]表示取log2n的整数部分；

（5）具有n个结点的完全二叉树的深度为[log2n]+1；

（6）设完全二叉树共有n个结点。如果从根结点开始，按层序（每一层从左到右）用自然数1，2，….n给结点进行编号（k=1,2….n），有以下结论：

①若k=1，则该结点为根结点，它没有父结点；若k>1，则该结点的父结点编号为int(k/2)；

②若2k≤n，则编号为k的结点的左子结点编号为2k；否则该结点无左子结点（也无右子结点）；

③若2k+1≤n，则编号为k的结点的右子结点编号为2k+1；否则该结点无右子结点。
满二叉树是指除最后一层外，每一层上的所有结点有两个子结点，则k层上有2k-1个结点深度为m的满二叉树有2m-1个结点。

完全二叉树是指除最后一层外，每一层上的结点数均达到最大值，在最后一层上只缺少右边的若干结点。

二叉树存储结构采用链式存储结构，对于满二叉树与完全二叉树可以按层序进行顺序存储。

二叉树的遍历：

（1）前序遍历（dlr），首先访问根结点，然后遍历左子树，最后遍历右子树；

（2）中序遍历（ldr），首先遍历左子树，然后访问根结点，最后遍历右子树；

（3）后序遍历（lrd）首先遍历左子树，然后访问遍历右子树，最后访问根结点。

---------------------------

平衡二叉树又叫ALV 树
平衡二叉树的特点是左右字数的高度相差不超过1
判断「平衡二叉树」的 2 个条件：
① 是「二叉排序树」
② 任何一个节点的左子树或者右子树都是平衡二叉树（左右高度差小于等于 1）
4 种旋转类型：
LL 型：插入左孩子的左子树，右旋
RR 型：插入右孩子的右子树，左旋
LR 型：插入左孩子的右子树，先左旋，再右旋
RL 型：插入右孩子的左子树，先右旋，再左旋
在平衡二叉树里，所有的叶子节点都包含相同的深度

----------------------------

红黑树是内存最优的结构树；

红黑树是一种特定类型的二叉树，它是在计算机科学中用来组织数据比如数字的块的一种结构。

红黑树的特点：
①每个节点不是黑色就是红色；
②根节点都是黑色的；
③每个叶子节点都是NULL，是黑色的；
④如果一个节点是红色的，那么他的子节点必须也是黑色的；
⑤从一个节点到该节点的所有子孙节点上包含相同的黑色节点；