二叉树的遍历-前序、中序、后序、层次 Java

二叉树的遍历-前序、中序、后序、层次 Java

二叉树结构：

    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int val) {
            this.val = val;
        }
    }

前序遍历：

 递归：
 static void traverseTreeNodePreRecursion(TreeNode root) {
        if (root == null) {
            return;
        }
        System.out.println(root.val);
        traverseTreeNodePreRecursion(root.left);
        traverseTreeNodePreRecursion(root.right);
    }

非递归：
    static void traverseTreeNodePreNORecursion(TreeNode root) {
        if (root == null) {
            return;
        }
        Stack stack = new Stack<>();
        while (root != null || !stack.empty()) {
            while (root != null) {
                System.out.println(root.val);
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            root = root.right;
        }
    }

中序遍历：

    递归：
     static void traverseTreeNodeMiddleRecursion(TreeNode root) {
        if (root == null) {
            return;
        }
        traverseTreeNodeMiddleRecursion(root.left);
        System.out.println(root.val);
        traverseTreeNodeMiddleRecursion(root.right);
    }

        
    非递归：
    static void traverseTreeNodeMiddleNORecursion(TreeNode root) {
        if (root == null) {
            return;
        }
        Stack stack = new Stack<>();
        while (root != null || !stack.empty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            System.out.println(root.val);
            root = root.right;
        }
    }

后序遍历：

    递归：
    static void traverseTreeNodeSufRecursion(TreeNode root) {
        if (root == null) {
            return;
        }
        traverseTreeNodeSufRecursion(root.left);
        traverseTreeNodeSufRecursion(root.right);
        System.out.println(root.val);
    }


    非递归：
    static void traverseTreeNodeSufNORecursion(TreeNode root) {
        if (root == null) {
            return;
        }
        Stack stack = new Stack<>();
        TreeNode last = null;
        while (root != null || !stack.empty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            TreeNode currNode = stack.pop();
            if (currNode.right == null || currNode.right == last) {
                System.out.println(currNode.val);
                last = currNode;
            } else {
                stack.push(currNode);
                root = currNode.right;
            }
        }
    }

层次遍历：

    static void traverseTreeNodeLayer(TreeNode root) {
        if (root == null) {
            return;
        }
        linkedList list = new linkedList<>();
        list.offer(root);
        TreeNode currentNode;
        while (!list.isEmpty()) {
            currentNode = list.poll();
            System.out.println(currentNode.val);
            if (currentNode.left != null) {
                list.offer(currentNode.left);
            }
            if (currentNode.right != null) {
                list.offer(currentNode.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);
        TreeNode node7 = new TreeNode(7);

        node1.left = node2;
        node1.right = node3;

        node2.left = node4;
        node2.right = node5;

        node3.left = node6;
        node3.right = node7;

        //前序遍历  1 2 4 5 3 6 7
        System.out.println("前序遍历");
        System.out.println("递归");
        traverseTreeNodePreRecursion(node1);
        System.out.println("非递归");
        traverseTreeNodePreNORecursion(node1);
        //中序遍历  4 2 5 1 6 3 7
        System.out.println("中序遍历");
        System.out.println("递归");
        traverseTreeNodeMiddleRecursion(node1);
        System.out.println("非递归");
        traverseTreeNodeMiddleNORecursion(node1);
        //后序遍历  4 5 2 6 7 3 1
        System.out.println("后序遍历");
        System.out.println("递归");
        traverseTreeNodeSufRecursion(node1);
        System.out.println("非递归");
        traverseTreeNodeSufNORecursion(node1);
        //层次遍历  1 2 3 4 5 6 7
        System.out.println("层次遍历");
        traverseTreeNodeLayer(node1);
    }

个人才疏学浅、信手涂鸦，更多内容持续更新中，感兴趣的朋友请移步至个人公众号，谢谢支持......

公众号：wenyixicodedog