二叉树的遍历(递归与非递归版本)-蒲公英云

二叉树的遍历(递归与非递归版本)

梦里梦外; 2022-04-14 04:35 294阅读 0赞

最近在写关于二叉树方面的题目的时候,总是会用到二叉树的各种遍历,所以在这里将自己写的各种遍历,都记录下来.

递归部分:
首先二叉树的递归代码是比较简单的,而且前序,中序和后序遍历代码几乎一样, 只是打印节点值的输出语句的位置不一样.
可以递归部分,对于二叉树中节点的遍历顺序是一样的, 都是先遍历当前节点,然后遍历当前节点的左子树,然后是右子树, 然后在遍历节点的过程, 选择输出的节点值的时机.

非递归部分:
其实思想还是参考递归部分, 只是将递归遍历节点部分, 变成了使用栈来存放遍历的节点, 然后选择打印节点的值的时机

以下是代码部分

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
/**
 * author: zzw5005
 * date: 2018/11/24 9:57
 */
public class TraversalBST {
    //递归版本的二叉树遍历
    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 posOrder(TreeNode root){
        if(root == null){
            return;
        }
        posOrder(root.left);
        posOrder(root.right);
        System.out.print(root.val + " ");
    }
    //非递归版本的二叉树遍历
    public static void preOrder1(TreeNode root){
        Stack<TreeNode> stack = new Stack<>();
        while(!stack.isEmpty() || root != null){
            while(root != null){
                System.out.print(root.val + " ");
                stack.push(root);
                root = root.left;
            }
            if(!stack.isEmpty()){
                root = stack.pop();
                root = root.right;
            }
        }
    }
    public static void inOrder1(TreeNode root){
        Stack<TreeNode> stack = new Stack<>();
        while(!stack.isEmpty() || root != null){
            while(root != null){
                stack.push(root);
                root = root.left;
            }
            if(!stack.isEmpty()){
                root = stack.pop();
                System.out.print(root.val + " ");
                root = root.right;
            }
        }
    }
    public static void posOrder1(TreeNode root){
        Stack<TreeNode> stack1 = new Stack<>();
        Stack<Integer> stack2 = new Stack<>();
        while(!stack1.isEmpty() || root != null){
            while(root != null){
                stack1.push(root);
                stack2.push(0);
                root = root.left;
            }
            while(!stack1.isEmpty() && stack2.peek() == 1){
                stack2.pop();
                System.out.print(stack1.pop().val + " ");
            }
            if(!stack1.isEmpty()){
                stack2.pop();
                stack2.push(1);
                root = stack1.peek();
                root = root.right;
            }
        }
    }
    public static void levOrder(TreeNode root){
        if(root == null){
            return;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()){
            root = queue.poll();
            System.out.print(root.val + " ");
            if(root.left != null){
                queue.add(root.left);
            }
            if(root.right != null){
                queue.add(root.right);
            }
        }
    }
    public static class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;
        public TreeNode(int val) {
            this.val = val;
        }
    }
    public static void main(String[] args) {
        //树
        TreeNode root = new TreeNode(8);
        root.left = new TreeNode(6);
        root.right = new TreeNode(10);
        //root.left = new TreeNode(6);
        root.left.left = new TreeNode(5);
        root.left.right = new TreeNode(7);
        //root.left.right = new TreeNode(10);
        root.right.left = new TreeNode(9);
        root.right.right = new TreeNode(11);
        System.out.println("递归版本的二叉树遍历 : ");
        System.out.print("preOrder : ");
        preOrder(root);
        System.out.println();
        System.out.print("inOrder  : ");
        inOrder(root);
        System.out.println();
        System.out.print("posOrder : ");
        posOrder(root);
        System.out.println("\n");
        System.out.println("非递归版本的二叉树遍历 : ");
        System.out.print("preOrder1 : ");
        preOrder1(root);
        System.out.println();
        System.out.print("inOrder1  : ");
        inOrder1(root);
        System.out.println();
        System.out.print("posOrder1 : ");
        posOrder1(root);
        System.out.println();
        System.out.print("levOrder  : ");
        levOrder(root);
        System.out.println();
    }
}

输出的结果

递归版本的二叉树遍历 : 
preOrder : 8 6 5 7 10 9 11 
inOrder  : 5 6 7 8 9 10 11 
posOrder : 5 7 6 9 11 10 8 
非递归版本的二叉树遍历 : 
preOrder1 : 8 6 5 7 10 9 11 
inOrder1  : 5 6 7 8 9 10 11 
posOrder1 : 5 7 6 9 11 10 8 
levOrder  : 8 6 10 5 7 9 11