1
    / \
   2   3
  / \   \
 4   5   6
    / \  
   7   8

• 前序遍歷：1 2 4 5 7 8 3 6 根左右
• 中序遍歷：4 2 7 5 8 1 3 6 左根右
• 后序遍歷：4 7 8 5 2 6 3 1 左右根

建樹代碼

class Node {
    int value;
    Node left;
    Node right;
    public Node(int value) {
        this.value = value;
    }
    public void conect(Node left,Node right) {
        this.left = left;
        this.right = right;
    }
    @Override
    public String toString() {
        return value+"";
    }
}


public class Tree {
    public static Node create() {
        Map<Integer,Node> nodeMap = new HashMap<Integer,Node>();
        for (int i = 1; i < 9; i++) {
            Node node = new Node(i);
            nodeMap.put(i, node);
        }
        nodeMap.get(1).conect(nodeMap.get(2), nodeMap.get(3));
        nodeMap.get(2).conect(nodeMap.get(4), nodeMap.get(5));
        nodeMap.get(3).conect(null, nodeMap.get(6));
        nodeMap.get(4).conect(null, null);
        nodeMap.get(5).conect(nodeMap.get(7), nodeMap.get(8));
        nodeMap.get(6).conect(null,null);
        nodeMap.get(7).conect(null,null);
        nodeMap.get(8).conect(null,null);
        return nodeMap.get(1);
    }
}

前序遞歸遍歷

1. 前序遍歷根左右,遞歸訪問跟二叉樹的定義有關(guān)：null也是節(jié)點，所以葉子節(jié)點，被認為是一種特殊子樹（兩邊null）的根節(jié)點。

          4
         / \
      null  null  

2. 然后只是打印每個子樹的根節(jié)點，就實現(xiàn)了前序遍歷。

遞歸思路如下：

1. 遞歸的出口被設(shè)計成： 如果子樹的根節(jié)點是null，那么就不用遍歷,什么都不做返回
2. .每次打印根節(jié)點

    public static void recursiveDLR(Node root) {
        if(root != null) {
            System.out.print(root.value + " ");
            recursiveDLR(root.left);
            recursiveDLR(root.right);
        }
    }

從遞歸方法找非遞歸的方法：

1. 如果把遞歸拆開，每一層都用隱式棧記錄了這一層的右子樹的根節(jié)點，如本樹：第一層3進棧，第二層5進棧

2. 前序遍歷會優(yōu)先打印左邊的一樹枝，右邊都是進棧的貨，最初進棧的是緊挨著左邊樹枝的平行左樹枝

             1
            / 
          2   
         /   
        4 

3. 非遞歸完全由遞歸幻化而來，每次循環(huán)都是面向一個小子樹，打印他的根節(jié)點，然后先入右再如左，讓左做棧頂，下次循環(huán)就是左做根的小子樹

    public static void notRecursiveDLR(Node root) {
        Stack<Node> stack = new Stack<Node>();
        stack.push(root);
        while(!stack.isEmpty()) {
            Node thisRoot = stack.pop();
            System.out.print(thisRoot + " ");
            if(thisRoot.right != null) {
                stack.push(thisRoot.right);
            }
            if(thisRoot.left != null) {
                stack.push(thisRoot.left);
            }
        }
    }

中序遍歷

遞歸思路

1. 跟前序一樣還是打印根節(jié)點，最左邊的葉子其實也可以看成是特殊子樹的根節(jié)點

    public static void recursiveLDR(Node root) {
        if(root != null) {
            recursiveLDR(root.left);
            System.out.print(root.value + " ");
            recursiveLDR(root.right);
        }
    }

非遞歸的思路

1. if中是遞歸子樹，每次入?yún)⒍际且粋€小子樹的根節(jié)點，然后一直扎到最左邊的葉子節(jié)點的null，

2. else中起到的是轉(zhuǎn)換方向的作用，相當(dāng)于給上邊的if傳入下一個小樹的根節(jié)點

3. 可以看到，中序遍歷是順序，最左邊的小子樹，它緊挨著的右邊的小子樹，然后向上返

4. 每次打印的也是根節(jié)點

              1
             / \
            2   3
           / \   \
          4   5   6
             / \  
            7   8

    public static void notRecursiveLDR(Node root) {
        Stack<Node> stack = new Stack<Node>();
        Node thisNode = root;
        while(!stack.isEmpty() || thisNode != null) {
            //遞歸子樹
            if(thisNode != null) {
                stack.push(thisNode);
                thisNode = thisNode.left;
            }else{//打印根節(jié)點，遞歸右子樹，每次遞歸其實都是先找左到葉子的左null節(jié)點，
                  //然后棧頂就是最左邊的葉子節(jié)點了，
                  //也就是最左子樹的根節(jié)點，其實也是打印根節(jié)點           
                Node treeNode = stack.pop();
                System.out.print(treeNode + " ");
                thisNode = treeNode.right;
            }

        }
    }