二叉树

二叉树就是度不超过2的树(每个结点最多有两个子结点)。

1. 满二叉树

一个二叉树，如果每一个层的结点树都达到最大值，则这个二叉树就是满二叉树。

2. 完全二叉树

叶节点只能出现在最下层和次下层，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树。

3. 二叉排序树（搜索二叉树）

二叉排序树（Binary Sort Tree）或者是一颗空树；或者是具有如下性质的二叉树：

(1) 若它的左子树不空，则 左子树 上所有结点的值 均小于 它的根结点的值； (2) 若它的右子树不空，则 右子树 上所有结点的值 均大于 它的根结点的值； (3) 它的 左、右子树又分别为二叉排序树 。

4. 二叉树的遍历

1.前序遍历：先访问根结点，然后再访问左子树，最后访问右子树。
2.中序遍历：先访问左子树，中间访问根节点，最后访问右子树。
3.后序遍历：先访问左子树，再访问右子树，最后访问根节点。
可以根据（前序遍历+中序遍历）或（中序遍历+后序遍历）结果反推二叉树（必须要有中序遍历）

5. 平衡二叉树

二叉搜索树一定程度上可以提高搜索效率，但是当原序列有序，例如序列A = {1，2，3，4，5，6}，构造二叉搜索树如图。依据此序列构造的二叉搜索树为右斜树，同时二叉树退化成单链表，搜索效率降低为O(n)。

在此二叉搜索树中查找元素6需要查找6次。二叉搜索树的查找效率取决于树的高度，因此保持树的高度最小，即可保证树的查找效率。同样的序列A，改为下图方式存储，查找元素6时只需比较3次，查找效率提升一倍。

可以看出当节点数目一定，保持树的左右两端保持平衡，树的查找效率最高。这种左右子树的高度相差不超过1的树为平衡二叉树。