二叉树
一、二叉树的定义
在计算机科学中，树是一种重要的非线性数据结构，直观的看，它是数据元素按分支关系组织起来的结构。二叉树是每个节点最多有两个子树的有序树。通常子树的根被称作“左子树”和“右子树”。二叉树常被用做二叉查找树和二叉堆或是二叉排序树。二叉树的每个节点至多只有两颗子树，二叉树有左右之分，次序不能颠倒。简单来说只要满足下面两个条件就是二叉树：
1.本身是有序树；
2.树中包含的各个节点的度不能超过 2，即只能是 0、1 或者 2；
图1.二叉树示意图
二叉树具有的性质：
1.二叉树中，第 i 层最多有2的i-1次方个结点。
2.如果二叉树的深度为 K，那么此二叉树最多有 2K-1 个结点。
3.二叉树中，终端结点数（叶子结点数）为 n0，度为 2 的结点数为 n2，则 n0=n2+1。
1、满二叉树
二叉树中，除了叶子节点，每个节点的度都为2，及每个节点都有左右两个子节点。这时候的二叉树称之为“满二叉树”。
图2.满二叉树示意图
满二叉树除了具有二叉树的基本心智以外还具有以下性质：
1.满二叉树中第 i 层的节点数为 2的i-1次方个。
2.深度为 K 的满二叉树必有 个节点 ，叶子数为 2的K-1次方。
3.满二叉树中不存在度为 1 的节点，每一个分支点中都两棵深度相同的子树，且叶子节点都在最底层。
4.具有 n 个节点的满二叉树的深度为 。
2、完全二叉树
如果二叉树中除去最后一层节点外，其它层为满二叉树，且最后一层的结点依次从左到右分布，则此二叉树被称为完全二叉树。满二叉树一定是个完全二叉树。
图3.完全二叉树示意图
如图 3a) 所示是一棵完全二叉树，图 3b) 由于最后一层的节点没有按照从左向右分布，因此只能算作是普通的二叉树。
完全二叉树除了具有普通二叉树的性质，它自身也具有一些独特的性质，比如说，n 个结点的完全二叉树的深度为 ⌊log2n⌋+1。
PS：⌊log2n⌋ 表示取小于 log2n 的最大整数。例如，⌊log24⌋ = 2，而 ⌊log25⌋ 结果也是 2。
对于任意一个完全二叉树来说，如果将含有的结点按照层次从左到右依次标号（如图 3a)），对于任意一个结点 i ，完全二叉树还有以下几个结论成立：
1.当 i>1 时，父亲结点为结点 [i/2] 。（i=1 时，表示的是根结点，无父亲结点）
2.如果 2*i>n（总结点的个数） ，则结点 i 肯定没有左孩子（为叶子结点）；否则其左孩子是结点 2*i 。
3.如果 2*i+1>n ，则结点 i 肯定没有右孩子；否则右孩子是结点 2*i+1 。
3、二叉搜索树
从节点出发，左子树节点的数据是小于节点，右子树节点的数据都是大于节点，这样的二叉树称为“二叉搜索树”。
图4.二叉搜索树
4、平衡二叉搜索树
在二叉搜索树的基础上，左子树和右子树高度差的绝对值不能超过1。
图5.非平衡二叉树
如图5所示，左子树的高度为4，右子树的高度为2，高度差为2，所以它不是平衡二叉树。
二、二叉树的存储
1.线性存储：用一个字符数组来保存，将二叉树的节点按照层级从左到右标识下标，如下图所示：
图6.线性存储
按照下标最终排的结果为：abcdefg，那如何找到节点的左右子节点呢？假设 i 为字符数组的下标，则它的左节点的数组下标为2*i+1，右节点的数组下标为2*i+2。
2.链式存储：内部有两个指针分别指向左右两个子节点。常用的存储方式。
三、二叉树的遍历
1、深度遍历
从根节点出发，使用递归的方式遍历。前、中、后序遍历都是属于深度遍历，使用的方法就是递归。除了递归，还可以使用迭代法遍历。大多数情况下，迭代都能通过栈模拟出来递归，只是可能实现的方法要麻烦一些。
前序遍历：中左右
中序遍历：左中右
后序遍历：左右中
简单理解一下，所谓的前、中、后遍历方式，只需要记住中（根）的位置在哪儿，在最前就是前序，在中间就是中序，在最后就是后序，左右是不会变的。所谓的前中后的单位都是树，如下图所示，a的左为b子树，b子树包含了de节点，处理a的左子树的时候，会将bde看作一棵树，然后再在这棵树中使用左来遍历。
图7.二叉树的遍历-深度遍历
2、广度遍历
一层一层的从左到右遍历。
3、使用Java代码实现二叉树的插入和遍历
public class BinarySearchTree{
private int data;
private BinarySearchTreeleft;
private BinarySearchTreeright;
public BinarySearchTree(int data) {
this.data = data;
}
public BinarySearchTree(int data, BinarySearchTree left, BinarySearchTree right) {
this.data = data;
this.left = left;
this.right = right;
}
/**
* 插入二叉搜索树，比节点数据大的数据插入右子树，反之插入左子树
*/
public static BinarySearchTreeinsert(BinarySearchTree root, int val) {
if (null == root) {
return new BinarySearchTree(val);
}
if (root.data < val) {
root.right =insert(root.right, val);
}
if (root.data > val) {
root.left =insert(root.left, val);
}
return root;
}
/**
* 遍历二叉树--递归--前序
*/
public static List<Integer> preTraverse(BinarySearchTree root, List<Integer> rlt) {
if (null == root) {
return rlt;
}
rlt =null == rlt ?new ArrayList<>() : rlt;
rlt.add(root.data);
preTraverse(root.left, rlt);
preTraverse(root.right, rlt);
rlt.add(root.data);
return rlt;
}
/**
* 遍历二叉树--递归--中序
*/
public static List<Integer> midTraverse(BinarySearchTree root, List<Integer> rlt) {
if (null == root) {
return rlt;
}
rlt =null == rlt ?new ArrayList<>() : rlt;
preTraverse(root.left, rlt);
rlt.add(root.data);
preTraverse(root.right, rlt);
return rlt;
}
/**
* 遍历二叉树--递归--后序
*/
public static List<Integer> posTraverse(BinarySearchTree root, List<Integer> rlt) {
if (null == root) {
return rlt;
}
rlt =null == rlt ?new ArrayList<>() : rlt;
preTraverse(root.left, rlt);
preTraverse(root.right, rlt);
rlt.add(root.data);
return rlt;
}
/**
* 遍历二叉树--迭代--前序
*/
public static List<Integer> preIteration(BinarySearchTree root, List<Integer> rlt) {
if (null == root) {
return rlt;
}
rlt =null == rlt ?new ArrayList<>() : rlt;
Stack<BinarySearchTree> stack =new Stack<>();
BinarySearchTree cur = root;
while (cur !=null || !stack.isEmpty()) {
while (cur !=null) {
stack.push(cur);
rlt.add(cur.data);
cur = cur.left;
}
BinarySearchTree top = stack.pop();
cur = top.right;
}
return rlt;
}
/**
* 遍历二叉树--迭代--中序
*/
public static List<Integer> midIteration(BinarySearchTree root, List<Integer> rlt) {
if (null == root) {
return rlt;
}
rlt =null == rlt ?new ArrayList<>() : rlt;
Stack<BinarySearchTree> stack =new Stack<>();
BinarySearchTree cur = root;
while (cur !=null || !stack.isEmpty()) {
while (cur !=null) {
stack.push(cur);
cur = cur.left;
}
BinarySearchTree top = stack.pop();
rlt.add(cur.data);
cur = top.right;
}
return rlt;
}
/**
* 遍历二叉树--迭代--后序
*/
public static List<Integer> posIteration(BinarySearchTree root, List<Integer> rlt) {
if (null == root) {
return rlt;
}
rlt =null == rlt ?new ArrayList<>() : rlt;
Stack<BinarySearchTree> stack =new Stack<>();
BinarySearchTree pre =null;
BinarySearchTree cur = root;
while (cur !=null || !stack.isEmpty()) {
while (cur !=null) {
stack.push(cur);
cur = cur.left;
}
cur = stack.peek();
if (cur.right ==null || pre == cur.right) {
BinarySearchTree top = stack.pop();
rlt.add(top.data);
pre = cur;
cur =null;
} else {
cur = cur.right;
}
}
return rlt;
}
/**
* 广度遍历--迭代--层级
*/
public static List<Integer> levelOderTraversal(BinarySearchTree root) {
Queue<BinarySearchTree> q1 =new LinkedList<>();
if (root ==null) {
return null;
}
q1.offer(root);
List<Integer> rlt =new ArrayList<>();
while (!q1.isEmpty()) {
BinarySearchTree top = q1.poll();
rlt.add(top.data);
if (top.left !=null) {
q1.offer(top.left);
}
if (top.right !=null) {
q1.offer(top.right);
}
}
return rlt;
}
}
