一、树形结构
1. 什么是树形结构？
树形结构是一层次的嵌套结构。 一个树形结构的外层和内层有相似的结构，表示的是一对多的关系。它和链表一样，也是一种动态的数据结构。
2. 为什么要有树形结构？
其实很多现实中存在的东西就是树形结构的，最典型的就是计算机中的文件夹。文件夹与文件夹之间有层次关系，一个文件夹下可以有若干个文件或者文件夹，这就是树形结构。
3. 二分搜索树：
3.1. 二叉树：
在说二分搜索树之前先说说二叉树。二叉树是一种特殊的树形结构，特殊在：
- 每个节点最多有两棵子树。
- 子树也有左右之分。
树也是用节点来存储元素，和链表不同的是，二叉树的节点类属性有三个，一个是泛型的e用来存储数据，一个是Node类型的left表示左节点，Node类型的right表示右节点。
class Node{ E e; Node left; Node right; }
二叉树具有天然的递归结构。因为二叉树的每个节点，都可以看成是子树的根节点。
3.2. 二分搜索树：
二分搜索树首先是一棵二叉树，同时具备以下特点：
- 二分搜索树每个节点的值，都大于左子树的所有节点的值。
- 二分搜索树每个节点的值，都小于右子树的所有节点的值。
- 二分搜索树的每一棵子树也都是二分搜索树。
- 这棵就是二分搜索树，每一个节点的值都大于左子树所有节点的值且小于右子树的所有节点的值。所以，二分搜索树存储的元素必须有可比较性。如果存储的是引用类型的数据，那么就应该用比较器指定某个属性进行比较。
3.2.1 实现二分搜索树：
public class BST<E extends Comparable<E>> { private class Node{//节点类 public E e;//用来存储元素 public Node left,right;//左孩子，右孩子 public Node(E e){ this.e = e; left = null; right = null; } } private Node root;//根节点 private int size;//元素的个数 public BST(){ root = null; size = 0; } }
根据上面的分析，可得上述代码。一棵二分搜索树用一个内部节点类来存储元素，同时有三个属性，左孩子、右孩子以及表示存储的元素个数的size。
3.2.2 二分搜索树的操作：
- 基本操作：获取存储的元素个数以及判断是否为空
/** 获取二分搜索树中元素的个数 */ public int size(){ return size; } /** 判断二分搜索树是否为空 */ public boolean isEmpty(){ return size == 0; }
这两个方法比较简单，就不多说了。
- 添加元素：
根据二分搜索树的性质，向其中添加元素，就需要从根节点开始判断添加的元素应该是在左边还是右边。假如比根节点元素更小，那就再与根节点的左孩子为根节点，再次进行判断。所以可以用递归来实现。
/** 向二分搜索树中添加元素(改进版) */ public void add(E e){ root = add(root,e); } //向二分搜索树中添加元素，返回根节点 private Node add(Node node,E e){ if (node == null){ //递归 size ++; //终止 return new Node(e); //条件 } if (e.compareTo(node.e) < 0){ node.left = add(node.left,e); }else if (e.compareTo(node.e) > 0){ node.right = add(node.right,e); } return node; }
给用户提供的是public的add方法，真正执行递归添加操作的是private的这个方法。从宏观上来讲，首先把root根节点传给这个方法，如果根节点为空，直接将元素添加到根节点；如果根节点不为空，且要添加的元素比该节点元素小，那么就在左边执行添加操作，更大就在右边执行添加操作，相等的话就不添加。那么从微观角度来讲，代码具体是怎么运行的呢？比如现有如下二分搜索树：
现要把“16”这个元素添加到该树中。看看代码的运行过程：
首先看上图红色文字以及红色连线。在给用户提供的add方法中，传入root(14)，e(16)，16大于14，所以再次调用add方法，传入的当前node的右节点，14的右节点就是20；传入节点20，再次判断，发现16比20小，再次调用add并且传入20的左节点；到了图三，发现传入的20的左节点是null，所以new一个节点存储16(开始看紫色文字和紫色连线)，并且把这个节点返回给图二的add方法处，并用节点20的left接收，这样新添加的节点16就成了节点20的左孩子；同时把节点20 return给图一的add方法处，并用节点14(root)的right接收，同时返回root，这样就完成了添加操作。添加完成后二分搜索树就变成：
- 遍历二分搜索树(深度优先）：
/** 二分搜索树的前序遍历 */ public void preOrder(){ preOrder(root); } private void preOrder(Node node){ if (node == null) return; System.out.println(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.println(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.println(node.e); }
遍历也是使用递归实现的，相对简单，就不画图解释了。
- 层序遍历：
上面三种遍历方式叫深度优先遍历，还有一种广度优先的遍历，叫层序遍历。就是先遍历第一层，再遍历第二层……。
/** 二分搜索树层序遍历 */ public void levelOrder(){ Queue<Node> queue = new LinkedList<>(); queue.add(root); while (!queue.isEmpty()){ Node cur = queue.remove(); System.out.println(cur.e); if (cur.left != null) queue.add(cur.left); if (cur.right != null) queue.add(cur.right); } }
这里层序遍历借助了队列来实现，相对也比较好理解。
- 删除操作：
首先来看两个简单的删除操作，即删除最小值和最大值。根据二分搜索树的性值，最小值一定是往左走的最后一个元素，最大值一定是往右走的最后一个元素。
/** 寻找二分搜索树的最小值 */ public E minele(){ if (size == 0) throw new IllegalArgumentException("二分搜索树为空"); return minele(root).e; } private Node minele(Node node){ if (node.left == null) return node; return minele(node.left); } /** 寻找二分搜索树的最大值 */ public E maxele(){ if (size == 0) throw new IllegalArgumentException("二分搜索树为空"); return maxele(root).e; } private Node maxele(Node node){ if (node.right == null) return node; return maxele(node.right); } /** 从二分搜索树中删除最小元素，并返回该元素 */ public E removeMin(){ E temp = minele();//最小元素 root = removeMin(root);//删除最小元素 return temp;//返回最小元素 } private Node removeMin(Node node){ if (node.left == null){ Node rightNode = node.right;//保留右边的 node.right = null; size --; return rightNode; } node.left = removeMin(node.left); return node; } /** 从二分搜索树中删除最大元素，并返回该元素 */ public E removeMax(){ E temp = minele();//最小元素 root = removeMax(root);//删除最小元素 return temp;//返回最小元素 } private Node removeMax(Node node){ if (node.right == null){ Node leftNode = node.left;//保留右边的 node.left = null; size --; return leftNode; } node.right = removeMax(node.right); return node; }
这就是删除最小值和最大值的代码，逻辑还是比较简单的。接下来看看删除任意一个元素。删除任意一个元素的话，如果这个元素有左子树和右子树，首先找到这个元素右子树中的最小值，用这个值取待被删除的元素，然后用这个元素左侧和右侧都连接上原来的子树就可以了。比如现在有如下二分搜索树，要删除元素58。
那么首先找到58的右子树中的最小值，即59，找到59后就把59从这个右子树中删除，同时用59取待58。就变成了这样：
这样就删除完成了。下面用代码来实现一下。
/** 删除二分搜索树中的元素e */ public void remove(E e){ root = remove(root,e); } private Node remove(Node node,E e){ if (node == null) return null; if (e.compareTo(node.e) < 0){ node.left = remove(node.left,e); return node; }else if (e.compareTo(node.e) > 0){ node.right = remove(node.right,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; } Node successor = minele(node.right); successor.right = removeMin(node.right); successor.left = node.left; node.left = node.right = null; return successor; } }
这段代码就对应了上面所分析的逻辑。
