0

課題があり、方法について助けが必要です。

だから私はこのような木を持っています:

                A
              /   \
             B     C
           /   \ /   \
          D    E F     G
        /   \
       H      I
     /   \
   J       K

私の方法は次のとおりです。

public BinaryTree preorderNext(BinaryTree t, BinaryTree v, BinaryTree prev) {       

    prev = t;

    if(t.getLeft() != null) {
        preorderNext(t.getLeft(), v, prev);
    }

    if(t.getRight() != null) {
        preorderNext(t.getRight(), v, prev);
    }


    if(prev == v) {
        return t;
    }

    return null;
}

講師はツリーの簡単な実装を行っていました。このクラスは BinaryTree と呼ばれ、それにノードをリンクさせたい場合は、右と左の子 BinaryTree ノードが何であるかを指定します。

ノードには 2 つのリンク (1 つは左の子、もう 1 つは右の子) があり、ヘッドへのリンクはありません。

したがって、現在の方法で事前注文トラバーサルを成功させることができるので、ノードに格納されている要素の印刷ステートメントを記述してテストしました。

しかし、テストを実行すると、A からの次の事前注文ノードは B であり、K からの次の事前注文ノードは null 例外をスローしますが、それは I である必要があります。

私が間違っている場所のアイデアはありますか? 変数 prev は、最後に訪れたノードへの参照を保持する必要があるため、ノード v (v の後にノードを返すために指定したノード) に等しい場合、次のノードを取得するべきではありませんか?

4

3 に答える 3

1

そのタスクを再帰的に行うのがそれほど簡単かどうかはわかりません。

スタックを使用してタスクを反復的に解決することは、はるかに優れたアプローチになる可能性があります。

public BinaryTree preOrderNext(BinaryTree toSearch) {

    Stack<BinaryTree> openList = new Stack<BinaryTree>();

    openList.push(root);

    while (openList.empty() == false) {
        BinaryTree curr = openList.pop();

        if (curr.getRight() != null)
            openList.push(curr.getRight());

        if (curr.getLeft() != null)
            openList.push(curr.getLeft());

        if (curr.equals(toSearch) && openList.empty() == false){
            return openList.pop();
        }
    }
    return null;
}

この方法はテストされていませんが、動作するはずです。

于 2013-03-04T17:54:50.073 に答える
0

preorder traversal以下は、 aが再帰的に行われる方法の実装です。

public void preOrderTraversal(BinaryTree root){
    if(root == null) return;

    System.out.println(root);
    preOrderTraversal(root.getLeft());
    preOrderTraversal(root.getRight());
}

ノート：

  1. あなたのアプローチはよくわかりません。なぜノードを返すのですか？いずれにせよ、rootそのアプローチで が null の場合は、" emptyNode" を返し、if ステートメントで処理できます。
  2. ご覧のとおりroot、どのレベルのroot変更でも、私は のみを扱っています。ランスルーでこれを視覚化してみてください。そうすれば、この概念を理解できます。
  3. 最初に null ノードのチェックがありません (特にt)。

結果をこれに適応させ続けることができます。

最後の注意点は、このアプローチの実行時の複雑さです。再帰関数の実行時の複雑さを理解することを強くお勧めします。それは将来あなたを大いに助けるでしょう。再発関係については、このウィキペディアの記事を確認してください。

于 2013-03-04T17:23:26.397 に答える
0

O(h)実行時間内に実行される回答を提供します。

class Node {
    public int key;
    public Node l;
    public Node r;
    public Node p;

    public Node(int key) {
        this.key = key;
        this.l = null;
        this.r = null;
        this.p = null;
    }
}

public Node preorderNext(Node v) {
    if (v.l != null) {
        return v.l;
    } else if (v.r != null) {
        return v.r;
    } else {
        while (v.p != null) {
            if (v == v.p.l) {
                if (v.p.r != null) {
                    return v.p.r;
                } else {
                    v = v.p;
                }
            } else {
                if (v.p.p == null) {
                    return null;
                } else if (v.p == v.p.p.l) {
                    if (v.p.p.r != null) {
                        return v.p.p.r;
                    } else {
                        v = v.p;
                    }
                } else {
                    v = v.p;
                }
            }
        }
        return null;
    }
}
于 2013-10-10T04:45:53.593 に答える