二叉树的非递归遍历模板

二叉树的非递归遍历

• 非递归遍历模板
• 前序遍历
• 中序遍历
• 后序遍历
• 测试

非递归遍历模板

这个模板只适用于前序遍历和中序遍历

private static void travers(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while (cur!=null || !stack.isEmpty()) {
            if (cur != null) {
                //这里写前序遍历代码
                //在进入左子树前访问根节点
                stack.push(cur);
                cur = cur.left;
            }else{
                cur = stack.pop();
                //这里中序遍历代码写这里
                //在进入右子树前访问根节点
                cur = cur.right;
            }
        }
    }

前序遍历

/**
     * 迭代前序遍历
     * @param root
     */
    private static void pre_travers_iterator(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while (cur!=null || !stack.isEmpty()) {
            if (cur != null) {
                //前序遍历代码
                System.out.print(cur.val + " ");
                //在进入左子树前访问根节点
                stack.push(cur);
                cur = cur.left;
            }else{
                cur = stack.pop();
                //中序遍历代码写这里
                cur = cur.right;
            }
        }

    }

中序遍历

/**
     * 迭代中序遍历
     * @param root
     */
    private static void in_travers_itrator(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while (cur!=null || !stack.isEmpty()) {
            if(cur != null) {
                stack.push(cur);
                cur = cur.left;
            }else{
                cur = stack.pop();
                //中序遍历代码
                System.out.print(cur.val + " ");
                //在进入右子树前访问根节点
                cur = cur.right;
            }
        }
    }

后序遍历

后序遍历比较特殊，它是先访问左节点、再访问右节点，最后再访问根节点。从比较好理解的角度来说的话，采用双栈是最好的。

后序遍历：左右根

从栈的特性的来说，先进后出，所以根节点先进去，然后右节点，最后才是左节点

/**
     * 迭代后序遍历
     * @param root
     */
    private static void post_travers_iterator(TreeNode root) {
    	//记录结点栈
        Stack<TreeNode> stack_main = new Stack<>();
        //辅助栈
        Stack<TreeNode> stack_help = new Stack<>();
        stack_help.push(root);
        while (!stack_help.isEmpty()) {
        	
            TreeNode cur = stack_help.pop();
            stack_main.push(cur);
            
            if (cur.left != null) {
                stack_help.push(cur.left);
            }
            if (cur.right != null) {
                stack_help.push(cur.right);
            }
        }

        while (!stack_main.isEmpty()) {
            TreeNode node = stack_main.pop();
            System.out.print(node.val + " ");
        }
    }

测试

迭代和递归一起测试

代码

package com.BinaryTree;

import java.util.Stack;

/**
 * 前中后遍历树
 * 递归
 * 迭代
 * @author: 小LeetCode~
 **/
public class TraversTree {


    public static void main(String[] args) {
        //构造一个棵二叉树
        TreeNode root = createTree();

        //递归前序遍历[0,1,3,7,4,2,5,8,6]
        System.out.println("递归前序遍历：");
        pre_travers(root);

        System.out.println();
        //递归中序遍历[3,7,1,4,0,8,5,2,6]
        System.out.println("递归中序遍历：");
        in_travers(root);

        System.out.println();
        //递归后序遍历[7,3,4,1,8,5,6,2,0]
        System.out.println("递归后序遍历：");
        post_travers(root);

        System.out.println();
        //迭代前序遍历
        System.out.println("迭代前序遍历：");
        pre_travers_iterator(root);

        System.out.println();
        //迭代中序遍历
        System.out.println("迭代中序遍历：");
        in_travers_itrator(root);

        System.out.println();
        //迭代后序遍历
        System.out.println("迭代后序遍历：");
        post_travers_iterator(root);

    }




    /**
     * 构造一个棵二叉树
     * @return
     */
    private static TreeNode createTree() {
        TreeNode root = new TreeNode(0);
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        TreeNode node6 = new TreeNode(6);
        TreeNode node7 = new TreeNode(7);
        TreeNode node8 = new TreeNode(8);

        root.left = node1;
        root.right = node2;
        node1.left = node3;
        node1.right = node4;
        node2.left = node5;
        node2.right = node6;
        node3.right = node7;
        node5.left = node8;

        return root;
    }

    /**
     * 递归前序遍历
     * @param root
     */
    private static void pre_travers(TreeNode root) {
        if (root == null) {
            return;
        }
        System.out.print(root.val + " ");
        pre_travers(root.left);
        pre_travers(root.right);
    }

    /**
     * 递归中序遍历
     * @param root
     */
    private static void in_travers(TreeNode root) {
        if (root == null) {
            return;
        }
        in_travers(root.left);
        System.out.print(root.val + " ");
        in_travers(root.right);
    }

    /**
     * 递归后序遍历
     * @param root
     */
    private static void post_travers(TreeNode root) {
        if (root == null) {
            return;
        }
        post_travers(root.left);
        post_travers(root.right);
        System.out.print(root.val + " ");
    }

    /**
     * 迭代前序遍历
     * @param root
     */
    private static void pre_travers_iterator(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while (cur!=null || !stack.isEmpty()) {
            if (cur != null) {
                //前序遍历代码
                System.out.print(cur.val + " ");
                stack.push(cur);
                cur = cur.left;
            }else{
                cur = stack.pop();
                //中序遍历代码写这里
                cur = cur.right;
            }
        }

    }


    /**
     * 迭代中序遍历
     * @param root
     */
    private static void in_travers_itrator(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while (cur!=null || !stack.isEmpty()) {
            if(cur != null) {
                stack.push(cur);
                cur = cur.left;
            }else{
                cur = stack.pop();
                System.out.print(cur.val + " ");
                cur = cur.right;
            }
        }
    }



    /**
     * 迭代后序遍历
     * @param root
     */
    private static void post_travers_iterator(TreeNode root) {
        Stack<TreeNode> stack_main = new Stack<>();
        Stack<TreeNode> stack_help = new Stack<>();
        stack_help.push(root);
        while (!stack_help.isEmpty()) {
            TreeNode cur = stack_help.pop();
            stack_main.push(cur);
            if (cur.left != null) {
                stack_help.push(cur.left);
            }
            if (cur.right != null) {
                stack_help.push(cur.right);
            }
        }

        while (!stack_main.isEmpty()) {
            TreeNode node = stack_main.pop();
            System.out.print(node.val + " ");
        }
    }
    

}

结果