0

二分探索木のノード数を数えようとしていますが、最も効率的な手段は何だろうと考えていました。これらは私が見つけたオプションです：

  1. int カウントを BST クラスに格納する

  2. その下の子の数を格納するツリーの各ノードに int の子を格納します

  3. BST のノード数をカウントするメソッドを作成する

オプション 3 を使用する場合は、次のように書きました。

int InOrder {
    Node *cur = root;
    int count = 0;
    Stack *s = null;
    bool done = false;

    while(!done) {
        if(cur != NULL) {
            s.push(cur);
            cur = cur->left;
        }
        else {
            if(!s.IsEmpty()) {
                cur = s.pop();
                count++;
                cur = cur->right;
            }
            else {
                done = true;
            }
        }
    }
    return count;

}

cur = cur->left;しかし、それを見ると、との間の無限ループに陥りそうです。cur = cur->right;

では、どのオプションが最も効率的で、それがオプション 3 である場合、この方法は機能しますか?

4

1 に答える 1

0

最初のオプションが最も速く、これを達成するために必要なのは O(1) スペースだけです。ただし、アイテムを挿入/削除するたびに、この値を更新し続ける必要があります。すべてのノードの数を取得するには、O(1) 時間かかります。

2 番目のオプションでは、ノードをどこかで削除/挿入すると、そのすべての祖先を更新する必要があるため、このプログラムは非常に複雑になります。祖先のそれぞれを適切に更新できるように親ポインターを追加するか、ツリー内のすべてのノードを調べて番号を再度更新する必要があります。いずれにせよ、これは 3 つすべての選択肢の中で最悪の選択肢になると思います。

最初のオプション O(1) はこのオプションよりもはるかに高速であるため、これを何度も呼び出さない場合は、3 番目のオプションが適しています。カウントを確認するにはすべてのノードを通過する必要があるため、これには O(n) がかかります。

あなたのコードに関しては、以下のような再帰的な方法で書く方が簡単だと思います:

int getCount(Node* n)
{
 if (!n)
  return 0;
 return 1 + getCount(n->left) + getCount(n->right);
}

お役に立てれば！

于 2013-06-25T05:32:33.770 に答える