树的定义：树是由结点或顶点和边组成的(可能是非线性的)且不存在着任何环的一种数据结构。没有结点的树称为空(null或empty)树。一棵非空的树包括一个根结点，还(很可能)有多个附加结点，所有结点构成一个多级分层结构。
二叉树的定义：每个结点至多拥有两棵子树(即二叉树中不存在度大于2的结点)，并且，二叉树的子树有左右之分，其次序不能任意颠倒。
二叉树的性质：
（1）若二叉树的层次从0开始，则在二叉树的第i层至多有2^i个结点(i>=0)。
（2）高度为k的二叉树最多有2^(k+1) - 1个结点(k>=-1)。 (空树的高度为-1)
（3）对任何一棵二叉树，如果其叶子结点(度为0)数为m, 度为2的结点数为n, 则m = n + 1。
完美二叉树：一个深度为k(>=-1)且有2^(k+1) - 1个结点的二叉树称为完美二叉树。（又叫满二叉树）
完全二叉树：完全二叉树从根结点到倒数第二层满足完美二叉树，最后一层可以不完全填充，其叶子结点都靠左对齐。
完满二叉树：所有非叶子结点的度都是2。
二叉查找树的性质：
（1）若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
（2） 若任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
（3） 任意节点的左、右子树也分别为二叉查找树；
（4） 没有键值相等的节点。
二叉查找树的删除：
（1）如果删除的是叶节点，可以直接删除；
（2）如果被删除的元素有一个子节点，可以将子节点直接移到被删除元素的位置；
（3）如果有两个子节点，这时候就采用中序遍历，找到待删除的节点的后继节点，将其与待删除的节点互换，此时待删除节点的位置已经是叶子节点，可以直接删除。
后继节点：根据不同的遍历排序后，将待删除的节点与他后面一个节点进行互换。
前序遍历：a、访问根节点；b、前序遍历左子树；c、前序遍历右子树。
中序遍历：a、中序遍历左子树；b、访问根节点；c、中序遍历右子树。
后序遍历：a、后序遍历左子树；b、后序遍历右子树；c、访问根节点。
已知前序和中序或者后序和中序，可以唯一确定一颗二叉树。
平衡二叉树的定义：平衡二叉查找树，又被称为AVL树，在具备二叉查找树的性质下还具有以下性质：
它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
左旋：新节点替换旧节点的位置，且新节点的左子树变为旧节点的右子树
X
/ \
a Y
/ \
b c
左旋伪代码：
LEFT-ROTATE(T, x)
01 y ← right[x] // 前提：这里假设x的右孩子为y。下面开始正式操作
02 right[x] ← left[y] // 将 “y的左孩子” 设为 “x的右孩子”，即 将β设为x的右孩子
03 p[left[y]] ← x // 将 “x” 设为 “y的左孩子的父亲”，即 将β的父亲设为x
04 p[y] ← p[x] // 将 “x的父亲” 设为 “y的父亲”
05 if p[x] = nil[T]
06 then root[T] ← y // 情况1：如果 “x的父亲” 是空节点，则将y设为根节点
07 else if x = left[p[x]]
08 then left[p[x]] ← y // 情况2：如果 x是它父节点的左孩子，则将y设为“x的父节点的左孩子”
09 else right[p[x]] ← y // 情况3：(x是它父节点的右孩子) 将y设为“x的父节点的右孩子”
10 left[y] ← x // 将 “x” 设为 “y的左孩子”
11 p[x]
