二叉树的遍历（递归和非递归）

二叉树是我们常用的一种数据结构，这篇文章介绍二叉树的遍历包括递归方法和非递归方法。先介绍下二叉树：

二叉树基本特点：

结点的度小于等于2
有序树（子树有序，不能颠倒）

二叉树的性质：

在二叉树的第i层上最多有2^{i-1}个结点
深度为K的二叉树最多有2^{k}-1个结点
对于任何一棵二叉树，若2度的结点数有n2个，则叶子结点数n0必定为n2+1
具有n个结点的完全二叉树的深度必为log2n取下整数＋1。

二叉树的遍历

先序遍历：根->左->右
中序遍历：左->根->右
后序遍历：左->右->根

先序遍历递归思想

若二叉树为空，则空操作
否则

访问根结点（D）

前序遍历左子树 (L)

前序遍历右子树 (R)

先序遍历的非递归思想
用栈记录（回溯）节点的位置，p指针指向根节点，输出，同时将p节点进栈，p指向p的左孩子；如果左孩子不为空，则输出该节点，同时再进栈，以此循环下去；当进行到某个节点的左孩子为空了，则出栈，输出该节点，同时p指向出栈节点的右孩子，重复执行第一步判断….即：
若P的左孩子不为空，则将P入栈并将P的左孩子置为当前节点，然后再对当前节点进行相同的处理；
若P的左孩子为空，则输出P节点，而后将P的右孩子置为当前节点，看其是否为空；
若不为空，则重复1）和2）的操作；
若为空，则执行出栈操作，输出栈顶节点，并将出栈的节点的右孩子置为当前节点，看起是否为空，重复3）和4）的操作；

直到当前节点P为NULL并且栈为空，则遍历结束。

先序遍历代码

public class PreOrder{
    static class TreeNode{
            Integer val;
            TreeNode left;
            TreeNode right;
            TreeNode(Integer x){
                this.val=x;
            }
    }
    private static List<Integer> list = new ArrayList<Integer>();
    /**
     * 递归算法先序遍历
     * @param root
     * @return
     */
    public List<Integer> preorderTraversal(TreeNode root) {
            if (root!=null){
                list.add(root.val);
                preorderTraversal(root.left);
                preorderTraversal(root.right);
            }
            return list;
    }
    /**
     * 非递归算法先序遍历
     */
     public List<Integer> preorderTraversa2(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode p =root;
        while(p!=null||!stack.isEmpty()){
            list.add(p.val);
            stack.push(p);
            p=p.left;
            while(p==null&&!stack.isEmpty()){
                p=stack.pop();
                p=p.right;
            }
        }
        return list;
     }
}

中序遍历递归思想

若二叉树为空，则空操作
否则

中序遍历左子树 (L)

访问根结点（D）

中序遍历右子树 (R)

中序遍历的非递归思想

对于任一节点P

若P的左孩子不为空，则将P入栈并将P的左孩子置为当前节点，然后再对当前节点进行相同的处理；
若P的左孩子为空，则输出P节点，而后将P的右孩子置为当前节点，看其是否为空；
若不为空，则重复1）和2）的操作；
若为空，则执行出栈操作，输出栈顶节点，并将出栈的节点的右孩子置为当前节点，看起是否为空，重复3）和4）的操作；
直到当前节点P为NULL并且栈为空，则遍历结束。

中序遍历代码

public class InOrder{
    static class TreeNode{
        Integer val;
        TreeNode left;
        TreeNode right;
        TreeNode(Integer x){
            this.val=x;
        }
    }
    private static List<Integer> list = new ArrayList<Integer>();
    /**
     * 递归算法遍历
     * @param root
     * @return
     */
    public  List<Integer> inorderTraversal(TreeNode root){
        if (root!=null){
            inorderTraversal(root.left);
            list.add(root.val);
            inorderTraversal(root.right);
        }
        return list;
    }
    public List<Integer> inorderTraversal(TreeNode root){
        Stack<TreeNode> stack = new Stack<>();
        TreeNode p =node;
        while(p!=null||!stack.isEmpty()){
            if(p.left!=null){
                stack.push(p);
                p=p.left;
            }else{
                list.add(p.val);
                p=p.right;
                while(p==null&&!stack.isEmpty()){
                    p = stack.pop();
                    list.add(p.val);
                    p=p.right;
                }
            }
        }
        return list;
    }
}

后序遍历递归思想

若二叉树为空，则空操作
否则

后序遍历左子树 (L)

后序遍历右子树 (R)

访问根结点（D）

后序遍历的非递归思想

对于任一节点P

先将节点P入栈；
若P不存在左孩子和右孩子，或者P存在左孩子或右孩子，但左右孩子已经被输出，则可以直接输出节点P，并将其出栈，将出栈节点P标记为上一个输出的节点，再将此时的栈顶结点设为当前节点；
若不满足2）中的条件，则将P的右孩子和左孩子依次入栈，当前节点重新置为栈顶结点，之后重复操作2）；
直到栈空，遍历结束。

后序遍历代码

public class BehindOrder{
    static class TreeNode{
        Integer val;
        TreeNode left;
        TreeNode right;
        TreeNode(Integer x){
            this.val=x;
        }
    } 
    private static List<Integer> list = new ArrayList<Integer>();
    /**
     * 后序遍历递归算法
     * @param root
     * @return
     */
    public List<Integer> behendorderTraversal(TreeNode root){
        if (root!=null){
            behendorderTraversal(root.left);
            behendorderTraversal(root.right);
            list.add(root.val);
        }
       return list;
    }
    public List<Integer> behendorderTraversal(TreeNode root){
        Stack<TreeNode> stack = new Stack<TreeNode>;
        TreeNode cur = root;
        TreeNode pre = null;
        stack.push(cur);
        while(!stack.isEmpty()){
            cur = stack.peek();
            if((cur.left==null&&cur.right==null)||(pre!=null&&(pre==cur.left||pre==cur.right))){
                list.add(cur.val);
                stack.pop();
                pre=cur; 
            }else{
                if(cur.right!=null){
                    stack.push(cur.right);
                }
                if(cur.left!=null){
                    stack.push(cur.left);
                }                
            }
        }
        return list;
    }       

}

二叉树基本特点：

二叉树的性质：

二叉树的遍历

先序遍历递归思想

先序遍历的非递归思想

先序遍历代码

中序遍历递归思想

中序遍历的非递归思想

中序遍历代码

后序遍历递归思想

后序遍历的非递归思想

后序遍历代码