欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

二叉树的先序、中序、后序遍历(递归 and 非递归)

程序员文章站 2022-05-06 21:26:25
...

二叉树的先序、中序、后序遍历(递归 and 非递归)

递归好写,非递归需要用栈就难写了。。

package lianjia;

import java.util.*;


public class Main{

    // 先序遍历(递归)
    public static void preOrder(TreeNode root) {
        if(root != null) {
            System.out.print(root.val + " ");
            preOrder(root.left);
            preOrder(root.right);
        }
    }

    // 中序遍历(递归)
    public static void inOrder(TreeNode root) {
        if(root != null) {
            inOrder(root.left);
            System.out.print(root.val + " ");
            inOrder(root.right);
        }
    }


    // 后序遍历(递归)
    public static void postOrder(TreeNode root) {
        if(root != null) {
            postOrder(root.left);
            postOrder(root.right);
            System.out.print(root.val + " ");
        }
    }


    // 先序遍历(非递归)
    public static void preOrder2(TreeNode root) {
        Stack<TreeNode> stack = new Stack();

        while(root != null || !stack.isEmpty()) {
            while(root != null) {
                System.out.print(root.val + " ");
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            root = root.right;  
        }
    }

    // 中序遍历 (非递归)
    public static void inOrder2(TreeNode root) {
        Stack<TreeNode> stack = new Stack();

        while(root != null || !stack.isEmpty()) {
            while(root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            System.out.print(root.val + " ");
            root = root.right;
        }
    }

    // 后序遍历 (非递归)
    public static void postOrder2(TreeNode root) {
        Stack<TreeNode> stack = new Stack();
        TreeNode preNode = null;

        while(root != null || !stack.isEmpty()) {
            while(root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.peek();
            // 如果右子树为空,或者右孩子访问过了,那么说明左右孩子都访问过了,当前父节点出栈
            if(root.right == null || root.right == preNode) { 
                System.out.print(root.val + " ");
                preNode = stack.pop();
                root = null;
            }else {
                root = root.right;
            }
        } 
    }

    public static void main(String[] args) {

        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);

        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node2.right = node5;
        node5.left = node6;


        preOrder(node1); // 先序遍历(递归)
        System.out.println("先序遍历(递归)");

        preOrder2(node1);// 先序遍历(非递归)
        System.out.println("先序遍历(非递归)");

        inOrder(node1); // 中序遍历(递归)
        System.out.println("中序遍历(递归)");

        inOrder2(node1); // 中序遍历(非递归)
        System.out.println("中序遍历(非递归)");

        postOrder(node1);  // 后序遍历(递归)
        System.out.println("后序遍历(递归)");

        postOrder2(node1);// 后序遍历(非递归)
        System.out.println("后序遍历(非递归)");
    }
}

测试样例如下:

二叉树的先序、中序、后序遍历(递归 and 非递归)

二叉树的先序、中序、后序遍历(递归 and 非递归)

注:学渣心里苦,不要学楼主,平时不努力,考试二百五,哭 ~

二叉树的先序、中序、后序遍历(递归 and 非递归)