二叉树前序中序遍历

     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. 前序遍历根左右,递归访问跟二叉树的定义有关：null也是节点，所以叶子节点，被认为是一种特殊子树（两边null）的根节点。

          4
         / \
      null  null  

2. 然后只是打印每个子树的根节点，就实现了前序遍历。

递归思路如下：

1. 递归的出口被设计成： 如果子树的根节点是null，那么就不用遍历,什么都不做返回
2. .每次打印根节点

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

从递归方法找非递归的方法：

1. 如果把递归拆开，每一层都用隐式栈记录了这一层的右子树的根节点，如本树：第一层3进栈，第二层5进栈

2. 前序遍历会优先打印左边的一树枝，右边都是进栈的货，最初进栈的是紧挨着左边树枝的平行左树枝

             1
            / 
          2   
         /   
        4 

3. 非递归完全由递归幻化而来，每次循环都是面向一个小子树，打印他的根节点，然后先入右再如左，让左做栈顶，下次循环就是左做根的小子树

    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. 跟前序一样还是打印根节点，最左边的叶子其实也可以看成是特殊子树的根节点

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

非递归的思路

1. if中是递归子树，每次入参都是一个小子树的根节点，然后一直扎到最左边的叶子节点的null，

2. else中起到的是转换方向的作用，相当于给上边的if传入下一个小树的根节点

3. 可以看到，中序遍历是顺序，最左边的小子树，它紧挨着的右边的小子树，然后向上返

4. 每次打印的也是根节点

              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{//打印根节点，递归右子树，每次递归其实都是先找左到叶子的左null节点，
                  //然后栈顶就是最左边的叶子节点了，
                  //也就是最左子树的根节点，其实也是打印根节点           
                Node treeNode = stack.pop();
                System.out.print(treeNode + " ");
                thisNode = treeNode.right;
            }

        }
    }