不知道大家是否了解二叉树呢?今天小编所讲的则是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常见问答，想要了解跟多关于二叉树的内容，可以继续关注本网站。