0

BST のビジュアライゼーションを作成したいのですが、オンラインで見つけたすべての例は、7 つ以下の値を挿入しただけで停止します。次のシーケンスを実行しているとします。

挿入 (5)、挿入 (7)、挿入 (9)、挿入 (8)、挿入 (3)、挿入 (2)、挿入 (4)、挿入 (6)、挿入 (10)。

insert(6) までは、次のようになります。

http://i.imgur.com/sFn8bSU.png

私の主な質問は、ここからどこへ行くのですか? 一番左のリーフに追加しますか、それとも「一番下」のリーフに追加しますか?

また、ウィキペディアによると、挿入のコードは次のとおりです。

void insert(Node* node, int value) {
    if (value < node->key) {
        if (node->leftChild == NULL)
            node->leftChild = new Node(value);
        else
            insert(node->leftChild, value);
    } else {
        if(node->rightChild == NULL)
            node->rightChild = new Node(value);
        else
            insert(node->rightChild, value);
    }
}

しかし、これによれば、私が 8 で insert(3) を取得すると、3 をノード 9 と比較するため、8 の左側に 3 が追加されます。次に、8 を比較対象のノードとして挿入を再実行し、3 を 8 の左側の子として配置します。しかし、これは一種のリストを作成するだけです。

ありがとう。

4

1 に答える 1

0

あなたを誤解させているように見えるのは、すべての挿入でルート（あなたの場合は5）から始めなければならないということです。それでは、上のグラフを見て、貼り付けたアルゴリズムに従って 3 を挿入してみましょう。

3 < 5, we go left and we meet 3
3 == 3, we go right (here it's the same, the code above says "go right") and we meet 4
3 < 4, we go left. Since 4 has no left child, 3 becomes its left child.

上記のアルゴリズムを使用してゼロからツリーを構築してみてください。ちなみに、n > 10 ノードの例は多くありません。これは、ノードが非常に長くなりすぎて、読者にとって何のメリットもないためです。

于 2013-10-08T22:39:03.253 に答える