java二叉树是java知识点中最重要的，每一个java人员都要熟练掌握java二叉树知识，那么java二叉树如何遍历?接下来，我们就来给大家讲解一下这方面的内容。大家可以参考以下内容。
前序遍历:先访问根结点,再访问左子结点,最后访问右子结点。图中的二叉树的前序遍历的顺序是10、6、4、8、14、12、16。
中序遍历:先访问左子结点,再访问根结点,最后访问右子结点。图中的二叉树的中序遍历的顺序是4、6、8、10、12、14、16。
后序遍历:先访问左子结点,再访问右子结点,最后访问根结点。图中的二叉树的后序遍历的顺序是4、8、6、12、16、14、10。
宽度优先遍历:先访问树的第一层结点,再访问树的第二层结点……一直到访问到最下面一层结点。在同一层结点中,以从左到右的顺序依次访问。我们可以对包括二叉树在内的所有树进行宽度
优先遍历。图中的二叉树的宽度优先遍历的顺序是10、6、14、4、8、12、16。
构造一颗如下图所示的二叉树，用java实现其前序，中序，后序遍历
注意二叉树节点的定义如下：
public class TreeNode
{
int val;
TreeNode left;
TreeNode right;
TreeNode(int x)
{
val = x;
}
}递归实现：
// 用递归的方法进行先序遍历
public void qinaxuDigui(TreeNode treeNode)
{
qianxuNumList.add(treeNode.val);
if (treeNode.left != null)
{
qinaxuDigui(treeNode.left);
}
if (treeNode.right != null)
{
qinaxuDigui(treeNode.right);
}
}
// 用递归的方法进行中序遍历
public void zhongxuDigui(TreeNode treeNode)
{
if (treeNode.left != null)
{
zhongxuDigui(treeNode.left);
}
zhongxuNumList.add(treeNode.val);
if (treeNode.right != null)
{
zhongxuDigui(treeNode.right);
}
}
// 用递归的方法进行后序遍历
public void houxuDigui(TreeNode treeNode)
{
if (treeNode.left != null)
{
houxuDigui(treeNode.left);
}
if (treeNode.right != null)
{
houxuDigui(treeNode.right);
}
houxuNumList.add(treeNode.val);
}非递归实现：
// 用非递归的方法进行先序遍历
public void qinaxuFeiDigui(TreeNode treeNode)
{
Stackstack = new Stack();
while (treeNode != null || !stack.isEmpty())
{
while (treeNode != null)
{
qianxuNumList.add(treeNode.val);
stack.push(treeNode);
treeNode = treeNode.left;
}
if (!stack.isEmpty())
{
treeNode = stack.pop();
treeNode = treeNode.right;
}
}
}
// 用非递归的方法进行中序遍历
public void zhongxuFeiDigui(TreeNode treeNode)
{
Stackstack = new Stack();
while (treeNode != null || !stack.isEmpty())
{
while (treeNode != null)
{
stack.push(treeNode);
treeNode = treeNode.left;
}
if (!stack.isEmpty())
{
treeNode = stack.pop();
zhongxuNumList.add(treeNode.val);
treeNode = treeNode.right;
}
}
}
// 用非递归的方法进行后序遍历
public void houxuFeiDigui(TreeNode treeNode)
{
Stackstack = new Stack();
while (treeNode != null || !stack.isEmpty())
{
while (treeNode != null)
{
stack.push(treeNode);
treeNode = treeNode.left;
}
boolean tag = true;
TreeNode preNode = null; // 前驱节点
while (!stack.isEmpty() && tag == true)
{
treeNode = stack.peek();
if (treeNode.right == preNode)
{ // 之前访问的为空节点或是栈顶节点的右子节点
treeNode = stack.pop();
houxuNumList.add(treeNode.val);
if (stack.isEmpty())
{
return;
}
else
{
preNode = treeNode;
}
}
else
{
treeNode = treeNode.right;
tag = false;
}
}
}
}运行结果如下：
这些就是java二叉树遍历的实例，我们可以看出，其实java二叉树的知识最重要的就是逻辑思维，只要将思维理清了，java二叉树的知识也就不难了，最后大家如果想要了解更多java常见问题知识，敬请关注奇Q工具网。
推荐阅读：