2

再帰を使用しているときに、バイナリ ツリーのレベル順トラバーサルに問題があります。次の値を入力しています: 50,60,70,30,20,10 使用しているコードは次のとおりです。

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

スタックを使わずに再帰は可能ですか? 現在、この関数は私をずっと左に連れて行ってから右に行くからです。私は何を別の方法で行うことができますか？

このコードの私の出力は: 50, 30, 60, 20, 70 で、10 を出力しません。

4

3 に答える 3

0

キューでトリックを行うことができます：

private Queue<Key> getLevelOrderKeys(Node root){

    if (root == null) {
        return null;
    }

    Queue<Key> keyQueue = new ArrayDeque<Key>(); //return value. Queue with the level order keys
    Queue<Node> nodeQueue = new ArrayDeque<Node>();

    nodeQueue.add(root);

    //while there is at least one discovered node
    while(!nodeQueue.isEmpty()) {

        Node current = nodeQueue.poll();
        keyQueue.add(current.key);

        if (current.left != null){
            nodeQueue.add(current.left);
        }

        if (current.right != null){
            nodeQueue.add(current.right);
        }

    }

    return keyQueue;

}
于 2014-12-30T13:46:54.377 に答える