java二叉树前序中序后序如何实现递归与非递归?

2020-04-21 13:47:21 java常见问答 4238

不知道大家是否了解二叉树呢?今天小编所讲的则是Java二叉树的前序,中序,后序来实现递归以及非递归的方式,接下来就让我们一起来了解下吧。

首先来说说构建二叉树的数据结构

/**
 * 构建二叉树的数据结构
 *
 */
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());
    }
}

以上就是今天所讲的有关二叉树的Java常见问答,想要了解跟多关于二叉树的内容,可以继续关注本网站。