一. 二叉树
一. 二叉树
1. 二叉树的基本概念
二叉树是每个结点最多有两个子树的树结构。通常子树被称作"左子树"（left subtree）和"右子树"（right subtree）。
一棵深度为k，且有2^k-1个节点的二叉树，称为满二叉树，这种树的特点是每一层上的节点数都是最大节点数。
1.1 二叉树基本形态
二叉树是递归定义的，其结点有左右子树之分，逻辑上二叉树有五种基本形态：
(1)空二叉树——如图(a)；
(2)只有一个根结点的二叉树——如图(b)；
(3)只有左子树——如图(c)；
(4)只有右子树——如图(d)；
(5)完全二叉树——如图(e)。
注意：尽管二叉树与树有许多相似之处，但二叉树不是树的特殊情形。
树和二叉树有两个主要差别：
- 树中结点的最大度数没有限制，而二叉树结点的最大度数为2；
- 树的结点无左、右之分，而二叉树的结点有左、右之分。
1.2 二叉树类型
(1)完全二叉树——若设二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第h层有叶子结点，并且叶子结点都是从左到右依次排布，这就是完全二叉树。
(2)满二叉树——除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树。
(3)平衡二叉树——平衡二叉树又被称为AVL树（区别于AVL算法），它是一棵二叉排序树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
1.3 树的相关术语
- 结点的度：结点子树的个数
- 树的度： 树中最大的结点度。
- 叶子结点：也叫终端结点，是度为 0 的结点；
- 分枝结点：度不为0的结点；
1.4 二叉树性质
(1) 在非空二叉树中，第i层的结点总数不超过 2^(i-1)
(2) 深度为h的二叉树最多有 2^h - 1 个结点,最少有h个结点
(3) 对于任意一棵二叉树，如果其叶子结点数为N0，而度数为2的结点总数为N2，则N0=N2+1；
(4)给定N个节点，能构成h(N)种不同的二叉树。
h(N)为卡特兰数的第N项。h(n)=C(2*n，n)/(n+1)
1.5 二叉树遍历
- 先序遍历
首先访问根，再先序遍历左（右）子树，最后先序遍历右（左）子树 - 中序遍历
首先中序遍历左（右）子树，再访问根，最后中序遍历右（左）子树 - 后序遍历
首先后序遍历左（右）子树，再后序遍历右（左）子树，最后访问根 - 层次遍历
即按照层次访问，通常用队列来做。访问根，访问子女，再访问子女的子女（越往后的层次越低）（两个子女的级别相同）
2. 完全二叉树
2.1 完全二叉树定义
-
若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。
-
完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。
(1)所有的叶结点都出现在第k层或k-l层（层次最大的两层）
(2)对任一结点，如果其右子树的最大层次为L，则其左子树的最大层次为L或L+l。
2.2 完全二叉树性质
假设n0是度为0的结点总数（即叶子结点数），n1是度为1的结点总数， n2是度为2的结点总数， n是结点总数 则 ：
n0=n/2，其中n为奇数时（n1=0）向上取整；n为偶数时（n1=1）。可根据完全二叉树的结点总数计算出叶子结点数。
2.3 完全二叉树特点
完全二叉树的特点是：
(1）只允许最后一层有空缺结点且空缺在右边，即叶子结点只能在层次最大的两层上出现；
(2）对任一结点，如果其右子树的深度为j，则其左子树的深度必为j或j+1。 即度为1的点只有1个或0个
2.4 完全二叉树存储
出于简便起见,完全二叉树通常采用数组而不是链表存储
其存储结构如下:
var tree:array[1..n]of longint;{n:integer;n>=1}
对于tree[i]，有如下特点：
（1）若i为奇数且i>1，那么tree的左兄弟为tree[i-1]；
（2）若i为偶数且i
（4）若2* i<=n，那么tree的左孩子为tree[2* i];若2* i+1<=n,那么tree的右孩子为tree[2* i+1]；
（5）若i>n/2,那么tree[i]为叶子结点（对应于（3））；
（6）若i<(n-1)/2.那么tree[i]必有两个孩子（对应于（4））。
（7）满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。
2.5 完全二叉树判定
判断一棵树是否是完全二叉树的思路
1>如果树为空，则直接返回错
2>如果树不为空：层序遍历二叉树
2.1>如果一个结点左右孩子都不为空，则pop该节点，将其左右孩子入队列；
2.1>如果遇到一个结点，左孩子为空，右孩子不为空，则该树一定不是完全二叉树；
2.2>如果遇到一个结点，左孩子不为空，右孩子为空；或者左右孩子都为空；则该节点之后的队列中的结点都为叶子节点；该树才是完全二叉树，否则就不是完全二叉树；
3. 满二叉树
3.1 满二叉树定义
-
对于国内的满二叉树
- 一个层数为k 的满二叉树总结点数为：2^k - 1,因此满二叉的结点树一定是奇数个。
- 第i层上的结点数为：2^i -1 ;
- 一个层数为k的满二叉树的叶子结点个数（也就是最后一层）:2^(k-1) ;
-
对于国外的满二叉树
满二叉树的任意节点，要么度为0，要么度为2.换个说法即要么为叶子结点，要么同时具有左右孩子。
4. 堆
4.1 堆的概念
堆是具有以下性质的完全二叉树：
- 每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；
- 或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆
在一个堆有序的二叉树中，父节点的位置是K/2,它的两个子节点的位置是2k,2k+1。
4.2 堆的实现
//最大堆
public class MaxPQ {
private List arr; //定义一个数组
private int N; //定义队列中的元素个数
public MaxPQ() {
arr = new ArrayList();
arr.add(1);
N = 0;
}
public boolean isEmpty() { //方法，返回队列是否为空
return N == 0;
}
public int size() { //方法，返回队列中元素的个数
return N;
}
public void inSert(int number) { //添加方法，添加元素到结合末尾，并且使用上浮方法到指定的位置
arr.add(number);
swim(++N);
}
public int deleteMax() { //删除方法，删除最大元素并把最小的元素放到第一个，然后使用下浮方法
int max = arr.get(1);
int min = arr.get(N);
arr.set(1, min);
arr.remove(N--);
sink(1);
return max;
}
//上浮
public void swim(int N) {
while(N > 1 && (arr.get(N/2) < arr.get(N))){
int max = arr.get(N);
int min = arr.get(N/2);
arr.set(N,min );
arr.set(N/2, max);
N = N/2;
}
}
//下沉
public void sink(int number) {
while(number*2 <= N) {
int index = number*2;
if(index < N && (arr.get(index) < arr.get(index + 1))) {
index++;
}
if(!(arr.get(number) < arr.get(index))) {
break;
}
int max = arr.get(index);
int min = arr.get(number);
arr.set(number, max);
arr.set(index, min);
number = index;
}
}
@Override
public String toString() {
return "MaxPQ [arr=" + arr + ", N=" + N + "]";
}
}
5. 二叉查找树(排序树)(Binary Search Tree，BST)
二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：
（1）若左子树不空，则左子树上所有结点的值均小于它的根节点点的值；
（2）若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；
（3）左、右子树也分别为二叉排序树；
（4）没有键值相等的节点。
例子：
二叉树查找树的详细解析
6. 平衡二叉树(AVL树)
6.1 平衡二叉树定义
-
对于一般的二叉搜索树（Binary Search Tree），其期望高度（即为一棵平衡树时）为logN，其各操作的时间复杂度（O(logN)）同时也由此而决定。但是，在某些极端的情况下（如在插入的序列是有序的时），二叉搜索树将退化成近似链或链，此时，其操作的时间复杂度将退化成线性的，即O(n)。
-
为了解决这个问题，要加上一个称为平衡的附加结构条件即：任何结点的深度不得过深
（子树高度相差不超过1），就是平衡二叉树（Balanced Binary Tree），它是G.M. Adelson-Velsky 和 E.M. Landis在1962年在论文中发表的，因此又叫AVL树。 -
AVL树只是实现平衡二叉树的一种方法，它还有很多的其他实现方法如红黑树、替罪羊树、Treap、伸展树等
6.2 平衡二叉树性质
它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。这个差值也称为平衡因子（其取值可以是1，0，-1，平衡因子是某个结点左右子树层数的差值)
6.3 平衡二叉树的设计
-
理解了平衡二叉树的概念后，我们在思考一下，那些操作可能引起平衡发生变化呢？
显然只有那些引起结点数量变化的操作才可能导致平衡被改变，也就是删除和插入操作了。 -
实际上也总是可以通过对树进行简单的修复来让其重新恢复到平衡，而这样的简单操作我们就称之为旋转，当然旋转也有单旋转和双旋转之分。
-
无论是插入还是删除，只有那些从插入点或者删除点到根结点的路径上的结点的平衡才有可能被改变，因为只有这些结点的子树才可能发生变化，所以最终也只需针对这些点进行平衡修复操作即可。
如何通过旋转来修复一棵失衡的二叉树，这里假设结点X是失衡点，它必须重新恢复平衡，由于任意结点的孩子结点最多有两个，而且导致失衡的必要条件是X结点的两棵子树高度差为2(大于1)，因此一般只有以下4种情况可能导致X点失去平衡：
① 在结点X的左孩子结点的左子树中插入元素
② 在结点X的左孩子结点的右子树中插入元素
③ 在结点X的右孩子结点的左子树中插入元素
④ 在结点X的右孩子结点的右子树中插入元素
以上4种情况，其中第①情况和第④情况是对称的，可以通过单旋转来解决，而第②种情况和第③情况是对称的，需要双旋转来解决。
6.3.1 左左单旋转(LL)情景①分析
在结点X的左孩子结点的左子树中插入元素
6.3.2 右右单旋转(RR)情景④分析
在结点X的右孩子结点的右子树中插入元素
6.3.3 左右双旋转(LR)情景②分析
在结点X的左孩子结点的右子树中插入元素
6.3.4 右左双旋转(RL)情景③分析
在结点X的右孩子结点的左子树中插入元素
