1. 二叉樹的遍歷

前序遍歷：根钝吮、左、右
中序遍歷：左板辽、根奇瘦、右
后續(xù)遍歷：左、右劲弦、根

2.遞歸以及非遞歸的實(shí)現(xiàn)

因?yàn)槎鏄湓揪褪沁f歸定義的耳标，所以遞歸方式實(shí)現(xiàn)二叉樹的遍歷比較簡(jiǎn)單。非遞歸方式主要是采用Stack來保存數(shù)據(jù)邑跪，并且由一個(gè)current指針指向當(dāng)前訪問的節(jié)點(diǎn)次坡。

import java.util.Stack;

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int data){
        val = data;
    }

    public void visit(TreeNode node){
        if(node != null){
            System.out.println(node.val);
        }
    }

    //前序遞歸遍歷
    public void preOrder(TreeNode root){
        if(root != null){
            visit(root);
            preOrder(root.left);
            preOrder(root.right);
        }
    }

    //非遞歸前序遍歷
    public void preOrder_no(TreeNode root){
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode current = root;
        while(current !=null || ! stack.isEmpty()){
            while(current != null){
                visit(current);
                stack.push(current);
                current = current.left;
            }
            if(!stack.isEmpty()){
                TreeNode temp = stack.pop();
                current = temp.right;
            }
        }
    }

    //中序遞歸遍歷
    public void inOrder(TreeNode root){
        if(root != null){
            inOrder(root.left);
            visit(root);
            inOrder(root.right);
        }
    }

    //中序非遞歸遍歷
    public void inOrder_no(TreeNode root){
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode current = root;
        while (current != null || !stack.isEmpty()){
            while(current != null){
                stack.push(current);
                current = current.left;
            }
            if(!stack.isEmpty()){
                TreeNode temp = stack.pop();
                visit(temp);
                current = temp.right;
            }
        }
    }

    //后序遞歸遍歷
    public void postOrder(TreeNode root){
        if(root != null){
            postOrder(root.left);
            postOrder(root.right);
            visit(root);
        }
    }

    // 后續(xù)非遞歸遍歷，有一個(gè)previsited指針記錄訪問過的前一個(gè)節(jié)點(diǎn)
    public void postOrder_no(TreeNode root){
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode current = root;
        TreeNode privisited = null;
        while(current != null || !stack.isEmpty()){
            while(current != null){
                stack.push(current);
                current = current.left;
            }
            current = stack.peek();
            if(current.right == null ||current.right == privisited){
                visit(current);
                stack.pop();
                privisited = current;
                current = null;

            }else{
                current = current.right;
            }
        }
    }

}