使用Java和递归的二级树遍历级别顺序遍历 [英] Level Order Traversal w/ Binary Trees using Java and Recursion

问题描述

我在使用递归时遇到二叉树的级别顺序遍历问题。我输入以下值：50,60,70,30,20,10
以下是我使用的代码：

I am having problems with the level order traversal of my binary tree whilst using recursion. I am inputing the following values: 50,60,70,30,20,10 Here is the code I am using:

    public void levelOrder(Node localRoot){
    if(localRoot != null){
        if(localRoot.leftChild != null && localRoot.rightChild != null){
            System.out.print(localRoot.iData + " ");
            System.out.print(localRoot.leftChild.iData + " ");
            System.out.print(localRoot.rightChild.iData + " ");
            levelOrder(localRoot.leftChild);
            levelOrder(localRoot.rightChild);
        }
        else if(localRoot.rightChild == null && localRoot.leftChild == null){
            ;
        }
        else if(localRoot.rightChild == null){
            System.out.print(localRoot.leftChild.iData + " ");
            //levelOrder(localRoot.leftChild);
        }
        else{
            System.out.print(localRoot.rightChild.iData + " ");
            //levelOrder(localRoot.rightChild);
        }
    }
}

无需使用a递归即可堆？因为目前这个功能一直带我到左边然后它正确。我可以采取哪些不同的做法？

Is recursion possible without using a stack? Because currently this function is taking me all the way to the left and then it goes right. What could I be doing differently?

此代码的输出为：50,30,60,20,70，不打印10。

My output for this code is: 50, 30, 60, 20, 70 and it does not print 10.

推荐答案

有趣的是，这是一个相当常见的问题（google递归面包首次遍历，并且有几个类似答案的stackoverflow链接）

Interestingly this is a fairly common question (google "recursive bread first traversal" and there are several links to stackoverflow of similar answers )

到目前为止最好的一个在这里

by far the best one is here

递归执行广度优先搜索

我同意最佳答案的作者，确实没有将迭代算法（广度优先遍历）转换为递归解决方案。如上所述，它易于将迭代转换为尾递归，但到底是什么？你仍然需要一个队列。

and i agree with the author of the top answer, there is really no point in turning an iterative algorithm (breadth first traversal) into a recursive solution. As mentioned yes its easy to turn iteration into tail recursion, but to what end? and you would still need a queue.

这篇关于使用Java和递归的二级树遍历级别顺序遍历的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！