java二叉树如何遍历?详细讲解

阳光 2021-02-02 21:17:26 java常见问答 4679

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。

java二叉树如何遍历?详细讲解.png

宽度优先遍历:先访问树的第一层结点,再访问树的第二层结点……一直到访问到最下面一层结点。在同一层结点中,以从左到右的顺序依次访问。我们可以对包括二叉树在内的所有树进行宽度

优先遍历。图中的二叉树的宽度优先遍历的顺序是10、6、14、4、8、12、16。

构造一颗如下图所示的二叉树,用java实现其前序,中序,后序遍历

1.png

注意二叉树节点的定义如下:

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;
            }
        }
    }
}

运行结果如下:

2.png

这些就是java二叉树遍历的实例,我们可以看出,其实java二叉树的知识最重要的就是逻辑思维,只要将思维理清了,java二叉树的知识也就不难了,最后大家如果想要了解更多java常见问题知识,敬请关注奇Q工具网。

推荐阅读:

java有哪些循环语句?java主要循环语句

java编程代码格式有哪些?写代码要注意什么?

ultraedit如何替换回车换行?如何使用正则表达式替换?