树
树这种数据结构跟现实中的树很像，里面的每个元素叫做结点，用连线把相邻的结点连接起来，相邻结点之间的关系叫父子关系。
比如下图中，A结点是B的父节点，B是A的子结点，B,C,D是兄弟结点，E没有父节点称为根节点，没有子节点的结点是叶子结点，G,H,I,H,K,L都是叶子结点。
树一般用三个概念可以描述，高度，深度，层
- 高度：结点到叶子结点的最长路径（边数）
- 深度：根结点到这个结点所经历的边的个数
- 层数：结点的深度加1
- 树的高度：根结点的高度
高度是从下往上度量，就像数楼层。深度从上往下度量，就像往水下看，层数是跟深度类似，不过是以1为起点。
二叉树
顾名思义，就是每个结点最多有两个叉，也就是两个叶子结点，左子节点和右子节点，左右子节点只要存在一个就行。
如果除了叶子结点外的每个结点都有左右两个子节点，这种二叉树叫“满二叉树”
如果叶子结点都在最底下两层，最后一层的叶子结点都靠左排列，并且除了最后一层，其他的结点个数都要达到最大，这种二叉树叫做“完全二叉树”
如何存储一个二叉树？
可以使用基于指针的或者引用的二叉链式存储法，或者基于数组的顺序存储法。
- 链式存储法：
每个结点有三个字段，其中一个缓存数据，剩下的两个分别是指向左右子节点的指针。我们只要找到根节点就能通过左右指针找到所有数据。 - 顺序存储法：
把根节点存储在下标为i=1的位置，左子节点存储在下标为2i=2的位置，右子节点存储在2i+1=3的位置，以此类推。
对于顺序存储法来说，完全二叉树更能节省内存。
二叉树的遍历
经典的方法有三种：前序遍历，中序遍历，后序遍历。前中后表示的是结点本身打印的顺序。
- 前序遍历是对于树种的任意结点来说，先打印这个结点，然后在打印它的左子树，最后打印它的右子树
- 中序遍历是对于树种任意结点来说，先打印它的左子树，在打印它本身，最后打印它的右子树
- 后序遍历是先对于树种任意结点来说，先打印左子树，在打印右子树，最后打印结点本身。
其实二叉树的前中后遍历就是一个递归的过程。比如前序遍历，就是先打印跟结点，然后递归打印左子树，在递归打印右子树。
遍历方法：
void preOrder(Node* root) {if (root == null) return;
System.out.print(root.data);
preOrder(root->left);
preOrder(root->right);
}
void inOrder(Node* root) {
if (root == null) return;
inOrder(root->left);
System.out.print(root.data);
inOrder(root->right);
}
void postOrder(Node* root) {
if (root == null) return;
postOrder(root->left);
postOrder(root->right);
System.out.print(root.data);
}
还有一种按层遍历，这个需要用到队列
public void levelOrder(BinaryTree tree) {// 利用队列先入先出的特点来实现按层遍历
LinkedList<BinaryTree> linkedList = new LinkedList<>();
// 记录当前遍历到哪个结点
BinaryTree currentNode = tree;
// 根节点入队
linkedList.add(currentNode);
// 从队列中弹出各结点数据，直到队列为空，遍历完毕
while (linkedList.size()>0){
// 弹出队首元素(当前结点)，打印其数据，并依次将其左右子节点入队
currentNode = linkedList.poll();
System.out.print(currentNode.data+" -> ");
if (currentNode.left!=null) {
linkedList.add(currentNode.left);
}
if (currentNode.right!=null) {
linkedList.add(currentNode.right);
}
}
}
二叉树最大的特点就是支持动态数据集合的快速插入、删除、查找操作。
二叉查找树（Binary Search Tree）
二叉查找树也叫二叉搜索树，是为了实现快速查找而生的，不过它不仅支持快速查找还支持快速插入删除。
二叉查找树规定：在树中的任意一个节点，其左子树的每个值都小于这个节点的值，右子树的每个值都大于这个节点的值。
1. 二叉查找树的查找
先取根节点，如果它等于我们要查找的数据，那就返回，如果要查找的数据小于根节点的值，那就在左子树中查找，反之就在右子树中查找。
代码：
public class BinarySearchTree {private Node tree;
public Node find(int data) {
Node p = tree;
while (p != null) {
if (data < p.data) p = p.left;
else if (data > p.data) p = p.right;
else return p;
}
return null;
}
public static class Node {
private int data;
private Node left;
private Node right;
public Node(int data) {
this.data = data;
}
}
}
2. 二叉查找树的插入
新插入的数据一般都是在叶子节点，我们需要从根节点开始依次比较要插入的数据和节点的大小关系。如果要插入的数据比节点的数据大，并且节点的右子树为空，就把数据插到右子节点的位置，如果不为空就在递归遍历右子树，直到找到插入的位置。如果要插入的数据比节点数值小并且节点的左子树为空，就插入，不为空，递归遍历左子树直到找到插入位置。
代码：
public void insert(int data) {if (tree == null) {
tree = new Node(data);
return;
}
Node p = tree;
while (p != null) {
if (data > p.data) {
if (p.right == null) {
p.right = new Node(data);
return;
}
p = p.right;
} else { // data < p.data
if (p.left == null) {
p.left = new Node(data);
return;
}
p = p.left;
}
}
}
3. 二叉查找树的删除
删除操作比插入和查找操作麻烦一点
- 如果要删除的节点是叶子节点，我们只需更新父节点指向删除节点的指针为null
- 如果要删除的节点只有一个子节点，我们只需要更新其父节点中指向要删除节点的指针，让它指向要删除的节点的子节点就好了
- 如果要删除的节点有两个子节点，我们需要找到这个节点的右子树中的最小节点，或者这个节点的左子树的最大节点，把它替换到要删除的节点上。因为父节点的指针一定比所有左子树的节点值大，比右子树的节点的值
代码：
public void delete(int data) {Node p = tree; // p 指向要删除的节点，初始化指向根节点
Node pp = null; // pp 记录的是 p 的父节点
while (p != null && p.data != data) {
pp = p;
if (data > p.data) p = p.right;
else p = p.left;
}
if (p == null) return; // 没有找到
// 要删除的节点有两个子节点
if (p.left != null && p.right != null) { // 查找右子树中最小节点
Node minP = p.right;
Node minPP = p; // minPP 表示 minP 的父节点
while (minP.left != null) {
minPP = minP;
minP = minP.left;
}
p.data = minP.data; // 将 minP 的数据替换到 p 中
p = minP; // 下面就变成了删除 minP 了
pp = minPP;
}
// 删除节点是叶子节点或者仅有一个子节点
Node child; // p 的子节点
if (p.left != null) child = p.left;
else if (p.right != null) child = p.right;
else child = null;
if (pp == null) tree = child; // 删除的是根节点
else if (pp.left == p) pp.left = child;
else pp.right = child;
}
中序遍历二叉树可以输出有序的数据序列，并且非常高效。因此二叉查找树也叫做二叉排序树。
如果数据中有重复的数据怎么办？
（1）二叉查找树中不仅会存储一个数据，我们可以通过链表和支持动态扩容的数组，把相同的值存储在同一个节点上。
（2）插入数据的时候，如果碰到一个节点的值与要插入的数据的值相同，就将这个要插入的数据放到这个节点的右子树，也就是把它当成大于这个节点的值来处理。
当要查找数据的时候，遇到值相同的节点，不停止查找操作，而是继续在右子树中查找，直到遇到叶子节点停止。
删除数据的时候，先找到每个要删除的节点，然后按照前面的删除方法依次删除。