5

これは、BST に関するウィキペディアにあるコードです。 

# 'node' refers to the parent-node in this case
 def search_binary_tree(node, key):
     if node is None:
         return None  # key not found
     if key < node.key:
         return search_binary_tree(node.leftChild, key)
     elif key > node.key:
         return search_binary_tree(node.rightChild, key)
     else:  # key is equal to node key
         return node.value  # found key

ここに二分木があります：

       10
    5        12
  3   8    9   14
     4 11

11 を探していて、そこまでのアルゴリズムに従っているとしたら、10 から始めて、右に 12 に行き、次に左に 9 に行きます。そして、11 を見つけることなく、ツリーの最後に到達します。しかし、11 は私のツリーに存在します。 、それはちょうど反対側にあります。

このアルゴリズムが私のツリーで機能するためのバイナリ ツリーの制限を説明していただけますか?

ありがとう。

4

5 に答える 5

10

それは、ツリーが二分探索ツリーではないためです。順序が正しくありません。BST は、実際のアルゴリズムで説明されているように構築されています。たとえば、ツリーの場合: ノード '9' は正しい位置にありません。これは、9 < 10 であるため、ルート ノード '10' の左の枝の下にある必要があるためです。'14' と '11' も同じで、右の枝にあります。

たとえば、BST は次のようになります。

    10
  5    11
3   8    12
          14
于 2010-09-07T05:37:39.173 に答える
3

二分木と二分探索木を混同しないでください。二分探索木 (略して BST と呼ばれます) は、左側のすべてのノードが親ノード以下であり、右側のすべてのノードが親ノードより大きい特殊なタイプの二分木です。

あなたが与えた例はバイナリツリーであり、バイナリ検索ツリーではありません。値 11 と 14 は、BST プロパティに違反する親ノード 10 に残されていることがわかります。二分探索木については、こちらをご覧ください。

于 2010-09-07T05:34:26.307 に答える
3

あなたが提示したツリーはBSTではありません。11 と 14 が 10 の左側に挿入されることはありません。そのため、アルゴリズムはそこを検索しません。9も場違いです。

ウィキペディアによる挿入:

挿入は、検索が始まるのと同じように始まります。ルートが値と等しくない場合は、以前と同様に左または右のサブツリーを検索します。最終的に、外部ノードに到達し、ノードの値に応じて、値を右または左の子として追加します。つまり、ルートを調べて、新しい値がルートより小さい場合は左側のサブツリーに新しいノードを再帰的に挿入し、新しい値がルート以上の場合は右側のサブツリーに挿入します。

次のプロパティがある場合、Binary Tree は BST であることがわかります (これもウィキペディアから)。

  1. ノードの左側のサブツリーには、ノードのキーより小さいキーを持つノードのみが含まれます。
  2. ノードの右側のサブツリーには、ノードのキーより大きいキーを持つノードのみが含まれます。
  3. 左と右の部分木は両方とも二分探索木でなければなりません。
于 2010-09-07T05:35:22.657 に答える
1

あなたの木は二分探索木ではありません

于 2010-09-07T05:58:51.073 に答える
1

ノード 14 と 11 を間違った場所に配置しました。BSTに関するウィキペディアの記事から：

  • ノードの左側のサブツリーには、ノードのキーより小さいキーを持つノードのみが含まれます。
  • ノードの右側のサブツリーには、ノードのキーより大きいキーを持つノードのみが含まれます。
  • 左と右の部分木は両方とも二分探索木でなければなりません。

ご覧のとおり、14 と 11 はどちらも 8 より大きいです。

于 2010-09-07T05:35:16.510 に答える