什么是树
树这种数据结构在生活中非常常见，比如去图书馆找一本书，书是按照不同的分类来摆放的。比如电脑中的磁盘文件夹等等。使用树结构存储数据后，会出奇的高效。见名知意，树这种数据结构就像一个倒着的树一样，也会有树根，树的枝杈，还有树叶。
二叉树名词解释
- 根节点：最上面节点叫根节点，根节点没有父节点，一个二叉树只存在一个根节点
- 子节点：每个父节点下面的节点叫做子节点，分为左和右，可以有一个，也可以有两个，最多也只能有两个
- 叶子节点：如果一个节点没有任何的子节点了，那么就称作叶子节点
- 左右子树：二叉树具有天然的递归结构性值，根节点下每个子节点也可以组成自己的一颗二叉树。
二分搜索树
- 二分搜索树是一个二叉树
- 二分搜索树的每一个节点的值，都大于左子树所有节点的值，小于右子树所有节点的值
- 存储的元素必须是有可比较性，不一定是数字，也可以实现 Compable 接口比较细节
以下都属于二叉树。首先二叉树不是平衡二叉树，多个节点少个节点都无所谓，深度不一样也无所谓。
元素的插入操作
先用 28 跟 41 比大小，比 41 小，根据二叉树特性，比当前节点小的节点都会在左面，所以 28 往左走，跟 22 比，28 比 22 大，大的就往右走和 33 比，28 比 33 小，小的往左边走，一看正好 33 左面为空，有个地方能放进去，最后将 28 存储到 33 节点左孩子节点的位置。
public class BinarySearchTree<E extends Comparable>{
private class Node {
public E e;
public Node left,right;
public Node(E e) {
this.e = e;
this.left = null;
this.right = null;
}
}
private Node root; // 根节点
private int size;
public boolean isEmpty() {return size == 0;}
public int getSize() {return size;}
public BinarySearchTree() {
root = null;
size = 0;
}
public void add(E e) {
// 如果此时没有根节点
if(root == null) {
// 添加元素到根节点
root = new Node(e);
size++;
}
else {add(root, e);// 代表有根节点
}
}
private void add(Node root,E e)
{
//1. 最根本的问题。和当前节点比较，看往那边放，前提是子节点为空的情况下
if(e.equals(root.e)) {return;}
else if(e.compareTo(root.e) < 0 && root.left == null) {root.left = new Node(e);
size++;
return;
}
else if(e.compareTo(root.e) > 0 && root.right == null) {root.right = new Node(e);
size++;
return;
}
//2. 把问题转换为更小的问题过程。这个 add 方法解决的就是根据当前节点比较，把元素插入合适的位置
if(e.compareTo(root.e) < 0) {// 往左放
add(root.left,e);
}
else{ // 相等一开始已经判断过了，这里只需要写 else 就可以了
add(root.right,e);
}
}
}是否包含某个元素
private boolean contains(Node node,E e)
{if(node == null)
return false;
if(e.compareTo(node.e) == 0) { // 找到了对应的节点
return true;
}
else if (e.compareTo(node.e) > 0) { // 大于当前节点就向右继续递归，否则向左递归继续找
return contains(node.right,e);
}
else{return contains(node.left,e);
}
}二分搜索树的遍历
每个元素都有三次遍历机会，分别是在调用两侧递归函数之前，在两侧递归函数中间，和在两侧递归函数之后。
前序遍历
public void preOrder()
{preOrder(root);
}
private void preOrder(Node node) {if(node == null)
return;
System.out.print(node.e + "---");
preOrder(node.left);
preOrder(node.right);
}
中序遍历
public void inOrder() {inOrder(root);
}
private void inOrder(Node node) {if(node == null)
return;
inOrder(node.left);
System.out.print(node.e + "---");
inOrder(node.right);
}
后序遍历
public void postOrder() {postOrder(root);
}
private void postOrder(Node node) {if(node == null)
return;
postOrder(node.left);
postOrder(node.right);
System.out.print(node.e + "---");
}
如下添加了这些元素之后，树的结构应该是这样的
int[] arr = {12,23,45,6,8,3,21};
for(int x = 0; x < arr.length; x++)
{tree.add(arr\[x\]);
}
tree.preOrder();
//--------------------------------
12
/ \
6 23
/ \ / \
3 8 21 45
前序遍历：12 - 6 -3 - 8 - 23 - 21 - 45
中序遍历：3 - 6 - 8 - 12 - 21 - 23 - 45
后序遍历：3 - 8 - 6 - 21 - 45 - 23 -12查找最小值和最大值
因为二分查找树的特性，最小值一定在最左侧，如果一个节点的左子节点为 null 了，那么这个节点就是最小值。相反最大值在右侧。
// 找到最大值和最小值
public E getMin()
{Node min = getMin(root);
return min.e;
}
private Node getMin(Node node)
{if(node.left == null)
return node;
return getMin(node.left);
}
// 找到最大值和最小值
public E getMax()
{Node min = getMax(root);
return min.e;
}
private Node getMax(Node node)
{if(node.right == null)
return node;
return getMax(node.right);
}删除最大和最小值
和查找最大值最小值思想差不多，只不过要注意下面这种情况。16 的左子节点为空，所以这个最小值是 16，删除 16 之后，要把 16 的右子节点和 28 关联上。也就是递归的时候，要把当前节点的左孩子节点和删除最值后返回的节点关联上。
// 删除最小元素
public E removeMin()
{E min = getMin();
root = removeMin(root);
return min;
}
private Node removeMin(Node node)
{if(node.left == null) { // 这里如果 node 的右子节点为空，逻辑也是成立的
Node rightNode = node.right;
node.right = null;
size--;
return rightNode;
}
node.left = removeMin(node.left);
return node;
}
// 删除最大元素
public E removeMax()
{E max = getMax();
root = removeMax(root);
return max;
}
private Node removeMax(Node node)
{if(node.right == null) { // 这里如果 node 的右子节点为空，逻辑也是成立的
Node leftNode = node.left;
node.left = null;
size--;
return leftNode;
}
node.right = removeMax(node.right);
return node;
}删除任意节点
比如要删除 58 这个节点，如果 58 没有左孩子或者右孩子其中一个节点，那么逻辑是和删除最大最小值是一样的，假设没有 50 这个左孩子节点，那么删除了 58 之后，将他的右侧节点 60 返回就好了。但如果 58 两侧都有节点，删除了 58 之后就面临着谁来当这个 ” 老大 ” 的问题，这个老大有两个人可以当，一个是 59，一个是 53。也就是右子树的最小值或者左子树的最大值。
知道这个节点以后，就可以维护这个节点的关系，最后给上层返回这个节点即可。那么维护关系其实就是让 59 的左孩子节点变成当前 58 的左孩子节点，让 59 的右孩子节点变成除了 59 以外的新节点。最后把 58 的关联关系干掉即可。
public void deleteNode(E e)
{root = deleteNode(root,e);
}
private Node deleteNode(Node node, E e) {if(node == null)
return null;
if(e.compareTo(node.e) > 0) {node.right = deleteNode(node.right,e);
return node;
}
else if(e.compareTo(node.e) < 0) {node.left = deleteNode(node.left,e);
return node;
}
else{ // 此时节点相等
// 左子树为空
if(node.left == null) {
Node rightNode = node.right;
node.right = null;
size--;
return rightNode;
}
// 左子树为空
if(node.right == null) {
Node leftNode = node.left;
node.left = null;
size--;
return leftNode;
}
//1. 找到待删除节点的接班人，接班人就是当前右子节点中最小的那个
//2. 用接班人顶替待删除节点
Node successor = getMin(node.right);
successor.right = removeMin(node.right);
successor.left = node.left;
node.left = node.right = null;
return successor;
}
}