假如现在有一棵树，如图：

树的遍历主要分为前序遍历、中序遍历和后序遍历。上面图的树遍历结果如下：

前序遍历：532468

中序遍历：234568

后序遍历：243865

 

可以简单理解（不严谨）：以根节点为参考点，前序遍历是根节点首先输出，然后左子树输出，最后右子树输出；中序遍历是左子树先输出，根节点在中间输出，右子树最后输出；后续遍历是左子树，右子树，最后根节点最后输出。

这里以中序遍历分析一下：

1、首先遍历根节点，有左子树，所以遍历左子树3

2、3有左子树，所以遍历左子树2

3、2遍历左子树为null，所以返回2，然后输出2

4、接着遍历2的右子树，为null,返回2后，在返回3，接着输出3

5、然后遍历右子树4，4的左子树为null，返回4，接着输出4，然后接着遍历4的右子树，为null，然后返回3，再返回5，输出5.

6、返回5后，再遍历5的右子树，遍历和上面类似。最终输出：234568

代码如下：

import java.util.Stack;public class BST
     
      > {    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;    }    public int size(){        return size;    }    public boolean isEmpty(){        return size == 0;    }    // 向二分搜索树中添加新的元素e    public void add(E e){        root = add(root, e);    }    // 向以node为根的二分搜索树中插入元素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;    }    // 看二分搜索树中是否包含元素e    public boolean contains(E e){        return contains(root, e);    }    // 看以node为根的二分搜索树中是否包含元素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.left, e);        else // e.compareTo(node.e) > 0            return contains(node.right, e);    }    // 二分搜索树的前序遍历    public void preOrder(){        System.out.print("前序遍历：");        preOrder(root);    }    // 前序遍历以node为根的二分搜索树, 递归算法    private void preOrder(Node node){        if(node == null)            return;        System.out.print(node.e + " ");        preOrder(node.left);        preOrder(node.right);    }    // 二分搜索树的中序遍历    public void inOrder(){        System.out.print("中序遍历：");        inOrder(root);    }    // 中序遍历以node为根的二分搜索树, 递归算法    private void inOrder(Node node){        if(node == null)            return;        inOrder(node.left);        System.out.print(node.e + " ");        inOrder(node.right);    }    // 二分搜索树的后序遍历    public void postOrder(){        System.out.print("后序遍历：");        postOrder(root);    }    // 后序遍历以node为根的二分搜索树, 递归算法    private void postOrder(Node node){        if(node == null)            return;        postOrder(node.left);        postOrder(node.right);        System.out.print(node.e + " ");    }    @Override    public String toString(){        StringBuilder res = new StringBuilder();        generateString(root, 0, res);        return res.toString();    }    // 生成以node为根节点，深度为depth的描述二叉树的字符串    private void generateString(Node node, int depth, StringBuilder res){        if(node == null){            res.append(generateDepthString(depth) + "null\n");            return;        }        res.append(generateDepthString(depth) + node.e + "\n");        generateString(node.left, depth + 1, res);        generateString(node.right, depth + 1, res);    }    private String generateDepthString(int depth){        StringBuilder res = new StringBuilder();        for(int i = 0 ; i < depth ; i ++)            res.append("--");        return res.toString();    }}
     

BST
     
       bst = new BST<>();        int[] nums = {5, 3, 6, 8, 4, 2};        for(int num: nums)            bst.add(num);        bst.preOrder();        System.out.println();        bst.inOrder();        System.out.println();        bst.postOrder();        System.out.println();        /*output：        前序遍历：5 3 2 4 6 8         中序遍历：2 3 4 5 6 8         后序遍历：2 4 3 8 6 5 */
     

用递归，进行深度遍历。