java实现二叉树的前序、中序、后序、层次遍历，递归与非递归

二叉树的前序、中序、后序、层次遍历，递归与非递归实现。在实现时，需要注意递归思想以及在非递归实现时使用了什么数据结构，以及为什么使用这些数据结构！好记性不如烂笔头，坐下笔记！

构建二叉树的数据结构

/**
 * 构建二叉树的数据结构
 *
 * @author wolf
 * @create 2018-07-29    18:09
 */
public class BinaryTree {
    int val;
    BinaryTree left;
    BinaryTree right;

    public BinaryTree(int val) {
        this.val = val;
    }
}

前序遍历的 递归与非递归实现

递归实现

实现思路：先根节点，再左节点，最后右节点。构建递归时有两个要点需要特别注意，一是递归结束的条件，一是递归表达式（即递归如何进行下去）。

 /**
     * 前序遍历递归方式实现
     * 递归适应思想，构建递归时有两个要点需要特别注意，一是递归结束的条件，一是递归表达式（即递归如何进行下去）
     *
     * @param root 二叉树的根节点
     */
    public void preorderBT(BinaryTree root) {
        //结束条件
        if (root == null)
            return;
        //递归主体
        System.out.print(root.val + " ");
        preorderBT(root.left);
        preorderBT(root.right);

    }

 

非递归实现

非递归实现思路：二叉树遍历的递归实现很简单，也很容易理解，在进行非递归实现时，需要用到栈这种数据结构（为什么是栈，不是别的数据结构）。因为递归实现的过程就是程序自己在处理圧栈和弹栈，改用非递归实现时，用栈模拟系统的圧栈与弹栈，就可以了。具体代码如下，结合注释看， 可以很容易理解。

/**
     * 前序遍历非递归方式实现
     * 非递归实现思路：二叉树遍历的递归实现很简单，也很容易理解，在进行非递归实现时，需要用到栈这种数据结构（为什么是栈，不是别的数据结构）。
     * 因为递归实现的过程就是程序自己在处理圧栈和弹栈，改用非递归实现时，用栈模拟系统的圧栈与弹栈，就可以了。
     */
    public List<Integer> preorderBT1(BinaryTree root) {
        List<Integer> preorderResult = new ArrayList<>();
        Stack<BinaryTree> stack = new Stack<>();
        BinaryTree currentNode = root;
        while (currentNode != null || !stack.isEmpty()) {
            //对于前序遍历，需要一直往二叉树的左子树上走，直道左子树走完。在走左子树的过程中需要输出遇到节点的值
            while (currentNode != null) {
                preorderResult.add(currentNode.val);
                stack.push(currentNode);
                currentNode = currentNode.left;
            }
            //左边的节点都走完了，需要改变节点方向
            if (!stack.isEmpty()) {
                currentNode = stack.pop();
                currentNode = currentNode.right;
            }
        }
        return preorderResult;
    }

 

中序遍历的递归与非递归

思想其实和前序遍历大致一致，但是需要注意一前序的不同地方。

/**
     * 中序遍历
     */
    public void inorderBT(BinaryTree root) {
        if (root == null)
            return;
        inorderBT(root.left);
        System.out.print(root.val + " ");
        inorderBT(root.right);
    }

    /**
     * 中序遍历的非递归实现,与上述前序遍历类似，只有稍许不同，注意
     */
    public List<Integer> inorderBT1(BinaryTree root) {
        List<Integer> inorderResult = new ArrayList<>();
        Stack<BinaryTree> stack = new Stack<>();
        BinaryTree currentNode = root;
        while (currentNode != null || !stack.isEmpty()) {
            //一直向左，但是先不打印经历的节点的值
            while (currentNode != null) {
                stack.push(currentNode);
                currentNode = currentNode.left;
            }
            //到达最左边，打印并改变方向
            if (!stack.isEmpty()) {
                currentNode = stack.pop();
                inorderResult.add(currentNode.val);
                currentNode = currentNode.right;
            }

        }
        return inorderResult;

    }

 

后序遍历

递归实现：

/**
     * 后序遍历的递归实现
     *
     * @param root
     */
    public void postorderBT(BinaryTree root) {
        if (root == null)
            return;
        postorderBT(root.left);
        postorderBT(root.right);
        System.out.print(root.val+" ");
    }

 

非递归实现

妙用前序遍历的非递归可以实现后序遍历的非递归实现，这里需要注意几点改变：后序时，先遍历右，再遍历左，最后将得到的结果反向就好了。至于为什么，可以首先自己操作观察验证。

/**
     * 后序遍历的非递归实现
     * 技巧：妙用前序遍历的非递归可以实现后序遍历的非递归实现，这里需要注意几点改变：后序时，先遍历右，再遍历左，最后将得到的结果反向就好了
     */
    public List<Integer> postorderBT1(BinaryTree root) {
        List<Integer> postorderResult = new ArrayList<>();
        Stack<BinaryTree> stack = new Stack<>();
        BinaryTree currentNode = root;
        while (currentNode != null || !stack.isEmpty()) {
            while (currentNode != null) {
                postorderResult.add(currentNode.val);
                stack.push(currentNode);
                currentNode = currentNode.right;
            }
            if (!stack.isEmpty()) {
                currentNode = stack.pop();
                currentNode = currentNode.left;
            }
        }
        Collections.reverse(postorderResult);
        return postorderResult;
    }

 

层次遍历

层次遍历，需要用到队列这种数据结构

/**
     * 层次遍历，需要用到队列这种数据结构
     */
    public List<Integer> levelOrderBT(BinaryTree root) {
        List<Integer> levelResult = new ArrayList<>();
        Deque<BinaryTree> deque = new ArrayDeque<>();
        if (root==null)
            return levelResult;
        deque.addLast(root);
        BinaryTree currentNode = root;
        while (!deque.isEmpty()){
            currentNode = deque.pollFirst();
            if (currentNode.left!=null)
                deque.addLast(currentNode.left);
            if (currentNode.right!=null)
                deque.addLast(currentNode.right);
            levelResult.add(currentNode.val);
        }
        return levelResult;

    }

 

对上述类的方法进行单元测试

 测试用的二叉树，如下图

package com.wolf.BinaryTree;

import org.junit.Test;

import java.util.List;

import static org.junit.Assert.*;

public class BinaryTreeTraversalTest {
//构架测试用的二叉树
    public static BinaryTree createBT() {
        BinaryTree node0 = new BinaryTree(6);
        BinaryTree node1 = new BinaryTree(8);
        BinaryTree node2 = new BinaryTree(5);
        BinaryTree node3 = new BinaryTree(4);
        BinaryTree node4 = new BinaryTree(3);
        BinaryTree node5 = new BinaryTree(9);
        BinaryTree node6 = new BinaryTree(1);
        BinaryTree node7 = new BinaryTree(2);
        node0.left = node1;
        node0.right = node2;
        node1.left = node3;
        node1.right = node4;
        node2.right = node5;
        node4.left = node6;
        node4.right = node7;
        return node0;

    }

    static BinaryTreeTraversal binaryTreeTraversal = new BinaryTreeTraversal();

    @Test
    public void preorderBT() {
        BinaryTree root = BinaryTreeTraversalTest.createBT();
        binaryTreeTraversal.preorderBT(root);

    }

    @Test
    public void preorderBT1() {
        BinaryTree root = BinaryTreeTraversalTest.createBT();
        List<Integer> list = binaryTreeTraversal.preorderBT1(root);
        System.out.println(list.toString());
    }

    @Test
    public void inorderBT(){
        BinaryTree root = BinaryTreeTraversalTest.createBT();
        binaryTreeTraversal.inorderBT(root);
    }
    @Test
    public void inorderBT1(){
        BinaryTree root = BinaryTreeTraversalTest.createBT();
        List<Integer> list = binaryTreeTraversal.inorderBT1(root);
        System.out.println(list.toString());
    }

    @Test
    public void postorderBT(){
        BinaryTree root = BinaryTreeTraversalTest.createBT();
        binaryTreeTraversal.postorderBT(root);
    }

    @Test
    public void postorderBT1(){
        BinaryTree root = BinaryTreeTraversalTest.createBT();
        List<Integer> list = binaryTreeTraversal.postorderBT1(root);
        System.out.println(list.toString());
    }

    @Test
    public void levelOrderBT(){
        BinaryTree root = BinaryTreeTraversalTest.createBT();
        List<Integer> list = binaryTreeTraversal.levelOrderBT(root);
        System.out.println(list.toString());
    }
}