数据结构Java版：二叉树（基础篇）

相关简介一、递归遍历

先序遍历中顺遍历后续遍历 二、非递归遍历

先序遍历中序遍历后续遍历层次遍历 三、结果调试

数据结构Java版：二叉树（题目篇）

前序遍历：访问根节点 左子树 右子树

中序遍历：访问左子树 根节点 右子树

后序遍历：访问左子树 右子树 根节点

1.二叉树示例

2.TreeNode结构

 public class TreeNode {
     public int val;
     public TreeNode left;
     public TreeNode right;
 
     public TreeNode() {
     }
 
     public TreeNode(int val) {
         this.val = val;
     }
 
     public TreeNode(int val, TreeNode left, TreeNode right) {
         this.val = val;
         this.left = left;
         this.right = right;
     }
 }

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

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

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

	// 先序遍历非递归
    public static void perOrderNonRecur(TreeNode root) {
        if (root == null) {
            return;
        }
        Stack stack = new Stack<>();
        TreeNode curNode = root;
        stack.push(curNode);
        while (!stack.empty()) {
            // 先处理当前元素
            curNode = stack.pop();
            System.out.print(curNode.val + " ");
            // 右孩子先进栈，左孩子后进栈 左孩子先出栈被处理
            if (curNode.right != null) {
                stack.push(curNode.right);
            }
            if (curNode.left != null) {
                stack.push(curNode.left);
            }
        }
    }

    
    // 先序遍历非递归
    public static void perOrderNonRecur02(TreeNode root) {
        if (root == null) {
            return;
        }
        Stack stack = new Stack<>();
        TreeNode curNode = root;
        while (curNode != null || !stack.empty()) {
            while (curNode != null) {
                System.out.print(curNode.val + " ");
                stack.push(curNode);
                curNode = curNode.left;
            }
            curNode = stack.pop();
            curNode = curNode.right;
        }
    }

 	// 中序遍历非递归
    public static void inOrderNonRecur(TreeNode root) {
        if (root == null) {
            return;
        }
        Stack stack = new Stack<>();
        TreeNode curNode = root;
        // 先处理左孩子
        while (curNode != null || !stack.empty()) {
            while (curNode != null) {
                stack.push(curNode);
                curNode = curNode.left;
            }
            curNode = stack.pop();
            System.out.print(curNode.val + " ");
            curNode = curNode.right;
        }
    }

	// 后续遍历非递归
    
    public static void postOrderNonRecur(TreeNode root) {
        if (root == null) {
            return;
        }
        Stack stack = new Stack<>();
        TreeNode curNode = root;
        // 记录前置节点 为空 || 栈顶元素的右孩子
        TreeNode preNode = null;
        while (curNode != null || !stack.empty()) {
            while (curNode != null) {
                stack.push(curNode);
                curNode = curNode.left;
            }
            curNode = stack.peek();
            
            if (curNode.right == null || curNode.right == preNode) { // 右孩子为空或者已被处理(避免重复处理)
                curNode = stack.pop();
                System.out.print(curNode.val + " ");
                preNode = curNode;
                curNode = null; // 避免重复处理当前节点
            } else { // 右孩子非空且未被处理
                curNode = curNode.right;
            }
        }
    } 

 	// bfs 层次遍历
    public static void levelOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        Queue queue = new linkedList<>();
        TreeNode curNode = root;
        queue.add(curNode);
        int size; // 记录每一层的元素个数
        while (!queue.isEmpty()) {
            size = queue.size();
            while (size-- > 0) { // 遍历一层的元素
                curNode = queue.poll();
                System.out.print(curNode.val + " ");
                if (curNode.left != null) {
                    queue.add(curNode.left);
                }
                if (curNode.right != null) {
                    queue.add(curNode.right);
                }
            }
            System.out.println();
        }
    }

程序入口

 public static void main(String[] args) {
     TreeNode root = mockTree();

     System.out.println("===> 递归遍历 ===>");
     System.out.print("先序遍历: ");
     preOrder(root);
     System.out.println();

     System.out.print("中序遍历: ");
     inOrder(root);
     System.out.println();

     System.out.print("后序遍历: ");
     postOrder(root);
     System.out.println();

     System.out.println("===> 非递归遍历 ===>");
     System.out.print("先序遍历: ");
     perOrderNonRecur(root);
     System.out.println();
     System.out.print("先序遍历: ");
     perOrderNonRecur02(root);
     System.out.println();

     System.out.print("中序遍历: ");
     inOrderNonRecur(root);
     System.out.println();

     System.out.print("后序遍历: ");
     postOrderNonRecur(root);
     System.out.println();

     System.out.println("===> 层次遍历 ===>");
     levelOrder(root);
 }


 public static TreeNode mockTree() {
     TreeNode root = new TreeNode(1);
     TreeNode two = new TreeNode(2);
     TreeNode three = new TreeNode(3);
     TreeNode four = new TreeNode(4);
     TreeNode five = new TreeNode(5);
     TreeNode six = new TreeNode(6);

     
     root.left = two;
     root.right = three;
     two.left = four;
     two.right = five;
     three.left = six;

     return root;
 }

结果预览

 ===> 递归遍历 ===>
 先序遍历: 1 2 4 5 3 6 
 中序遍历: 4 2 5 1 6 3 
 后序遍历: 4 5 2 6 3 1 
 ===> 非递归遍历 ===>
 先序遍历: 1 2 4 5 3 6 
 先序遍历: 1 2 4 5 3 6 
 中序遍历: 4 2 5 1 6 3 
 后序遍历: 4 5 2 6 3 1 
 ===> 层次遍历 ===>
 1 
 2 3 
 4 5 6