java二叉树中序遍历递归和非递归实现

KLQ 2020-07-14 10:16:44 java常见问答 5282

之前给大家介绍了java二叉树前序遍历递归和非递归实现的内容,下面就接着给大家介绍java中序遍历递归和非递归实现的内容,一起看看吧。

二叉树

1、中序遍历

看看访问顺序:左子树-根节点-右子树;

上面图片的访问结果是ADEFGHMZ;

(1)递归实现

public void inOrderTraverse(TreeNode root)
{
    if (root != null)
    {
        inOrderTraverse(root.left);
        System.out.print(root.val + "->");
        inOrderTraverse(root.right);
    }
}

(2)非递归实现

public void inOrderTraverse(TreeNode root)
{
    Stack < TreeNode > stack = new Stack < > ();
    TreeNode node = root;
    while (node != null || !stack.isEmpty())
    {
        if (node != null)
        {
            stack.push(node);
            node = node.left;
        }
        else
        {
            TreeNode tem = stack.pop();
            System.out.print(tem.val + "->");
            node = tem.right;
        }
    }
}

以上的实现方式你都清楚了吗?你还想了解更多java程序代码例子吗?请继续来奇Q工具网进行了解吧。

推荐阅读:

求二叉树深度的递归算法java

java二叉树深度不用递归,非递归实现

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