写在前面
树这种数据结构在计算机世界中有广泛的应用，比如操作系统中用到了红黑树，数据库用到了B+树，编译器中的语法树，内存管理用到了堆（本质上也是树），信息论中的哈夫曼编码等等等等。而树的实现和他的操作集也是笔试面试中常见的考核项目。
树的实现
与C语言的结构体+指针的实现方式不同，Java中树的实现当然是基于类。以二叉树为例，树的实现可以用下面这样的形式：
1 public class BinaryTree<T extends Comparable<T>> {
2 private BinaryTree<T> root;
3 //定义存储内容：内容、左子树、右子树
4 public class Node<T extends Comparable<T>>{
5 T data;
6 BinaryTree<T> left;
7 BinaryTree<T> right;
8 //也可以有父节点
9 BinaryTree<T> parent;
10
11 public Node(T data, BinaryTree<T> left, BinaryTree<T> right, BinaryTree<T> parent) {
12 this.data = data;
13 this.left = left;
14 this.right = right;
15 this.parent = parent;
16 }
17 }
18
19 //定义方法：增、删、查、改。
20
21 public boolean insert(int x){
22 ...
23 }
24 public boolean delete(int x){
25 ...
26 }
27 }要注意，为了清晰树中数据的含义，我们一般不直接把树节点当做其成员变量，而是在其中新建内部类将其打包。针对子节点不止2个的多叉树，只需要把上面的left，right等合并成一个BinaryTree<T>类型的数组即可。
树的遍历
树的遍历应当是我们的基本功，里面涉及了后面图论算法中的深度优先搜索（DFS）和广度优先搜索（BFS），因此虽然简单但也很重要。在树的遍历中，往往对应着递归算法和非递归算法（层序遍历除外）。递归算法往往能写出很精简的代码，但是运行过程中会占用大量的系统资源。因此，非递归算法在这一点上还是更有优势。我们也应该更着重记忆他的非递归算法。面试过程中，我们甚至可以和面试官讨论所要求的写法。
先来看看前中后序遍历的递归写法：
1 public void preOrderTraversal(BinaryTree<T> tree){
2 if(tree==null) return;
3 System.out.print(tree.node.data+" ");
4 preOrderTraversal(tree.node.left);
5 preOrderTraversal(tree.node.right);
6 }
1 //中序遍历
2 public void inOrderTraversal(BinaryTree<T> tree){
3 if(tree==null) return;
4 inOrderTraversal(tree.node.left);
5 System.out.print(tree.node.data+" ");
6 inOrderTraversal(tree.node.right);
7 }
1 //后序遍历
2 public void pastOrderTraversal(BinaryTree<T> tree){
3 if(tree==null) return;
4 pastOrderTraversal(tree.node.left);
5 pastOrderTraversal(tree.node.right);
6 System.out.print(tree.node.data+" ");
7 }
看起来相当简单，也相当好记对吧。再来看非递归怎么在Java中实现：
树的前序遍历和中序遍历的非递归算法都是用堆栈来实现，具体实现如下。
1 public void preOrderTraversal(){
2 Stack<BinaryTree<T>> st = new Stack<>();
3 BinaryTree<T> tmp = this;
4 while(tmp!=null || !st.empty()){
5 while(tmp!=null){
6 System.out.print(tmp.node.data+" ");
7 st.push(tmp);
8 tmp=tmp.node.left;//一路向左
9 }
10 if(!st.empty()){
11 tmp=st.pop();
12 tmp=tmp.node.right;//偶尔向右
13 }
14 }
15 System.out.println();
16 }
1 public void inOrderTraversal(){
2 Stack<BinaryTree<T>> st = new Stack<>();
3 BinaryTree<T> tmp = this;
4 while(tmp!=null || !st.empty()){
5 while(tmp!=null){
6 st.push(tmp);
7 tmp=tmp.node.left;
8 }
9 if(!st.empty()){
10 tmp=st.pop();
11 //输出变到这里，仅此而已
12 System.out.println(tmp.node.data);
13 tmp=tmp.node.right;
14 }
15 }
16 }后序遍历思路相似，由于后序遍历是第三次经过才进行输出（见上图），而上面的while循环和if代码块分别表示第一次见和第二次见，因此需要增加一个标志位在每一个节点，用来标明是不是在if代码块中第一次看见它。这么说并不明显，自己实现一遍应该会印象深刻一点。
1 //后续非递归
2 public void PastOrderTraversal(){
3 BinaryTree<T> Tmp = this;
4 Stack<BinaryTree<T>> st = new Stack<>();
5 while(Tmp!=null || !st.empty()){
6 while(Tmp!=null){
7 st.push(Tmp);
8 Tmp=Tmp.node.left;
9 }
10 if(!st.empty()){//if代码块
11 Tmp=st.pop();
12 if(Tmp.node.IsFirstTraversal){//这里判断是不是第一次进if代码块
13 Tmp.node.IsFirstTraversal=false;//进来过了，置位false，下一次就可以输出了
14 st.push(Tmp);
15 Tmp=Tmp.node.right;
16 }
17 else{//不是第一次，输出
18 System.out.print(Tmp.node.data+" ");
19 }
20 }
21 }
22 }
层序遍历只有非递归写法，没有递归的方法。层序遍历利用的数据结构是队列。遍历应该先从根节点开始，首先将根节点入队，然后开始执行循环：节点出队、访问节点（print）、左右儿子入队。
1 //层序遍历
2 public void levelOrderTraversal(){
3 Queue<BinaryTree<T>> tQueue = new ArrayDeque<>();
4 BinaryTree<T> tmp = this;
5 tQueue.add(tmp);
6 while(!tQueue.isEmpty()){
7 tmp = tQueue.remove();
8 System.out.print(tmp.node.data+" ");
9 if(tmp.node.left!=null) tQueue.add(tmp.node.left);
10 if(tmp.node.right!=null) tQueue.add(tmp.node.right);
11 }
12 }操作集
1.插入
1 private BinaryTree<T> insert(BinaryTree<T> t, Node<T> n){
2 if(t==null) {
3 t = new BinaryTree<>();
4 t.node = n;
5 return t;
6 }
7 int cmp = n.data.compareTo(t.node.data);
8 if(cmp==0) return null;//节点存在
9 else if(cmp<0) t.node.left = insert(t.node.left, n);
10 else t.node.right = insert(t.node.right, n);
11 return t;
12 }
13
14 public void insert(T x){
15 Node<T> n = new Node<>(x,null, null, null);
16 if(this.node==null){
17 this.node = n;
18 return;
19 }
20 insert(this,n);
21 }2.查找
普通查找比较好实现，这个就是利用了二分查找的思想。
1 /**
2 * 查找
3 * @param t 树
4 * @param x 查找的值
5 * @return 值所在树
6 */
7 private BinaryTree<T> find(BinaryTree<T> t, T x){
8 int cmp = x.compareTo(t.node.data);
9 if(cmp==0){//找到了
10 return t;
11 }
12 else if(cmp<0) return find(t.node.left,x);
13 else return find(t.node.right,x);
14 }
15
16 public BinaryTree<T> find(T x){
17 return find(this, x);
18 }
