私は二分探索木の背後にある理論を非常に悪い方法で説明している本を持っています。左と右の両方の子の順序について何かがあることは知っていますが、一方が他方の前のレベルよりも大きいという考えはまだ得られません。
たとえば、次の文字列ツリーを考えてみましょう。
（私のペイントで申し訳ありません）この例は私の本から直接取られています:)
誰かが私に注文を説明してもらえますか? この背後にあるロジックは何ですか？
質問する
39569 次
5 に答える
9
BSTでは、すべてのノードに最大で左の子と右の子があります。特定のノードの左側にあるすべてのノードはそれよりも小さく、特定のノードの右側にあるすべてのノードはそれよりも大きくなっています。この結果の1つは、重複する値を設定できないことです。そのため、その例が本の内容とまったく同じであるかどうかはわかりません。
例では、文字列はアルファベット順に並べられています。ルートノードを例にとると、ボブはカレンの前に来るので、ボブはカレンの左側に行きます。トムはカレンの後に来るので、トムはカレンの右に行きます。ツリー全体を見ると、カレンの左側のすべてのノード（ボブ、アラン、エレン）がアルファベット順にカレンの前にあり、カレンの右側のすべてのノード（トム、ウェンディ）がアルファベット順にカレンの後にあることがわかります。このパターンは、どのノードを見ても同じです。
于 2012-12-26T16:01:03.627 に答える
2
任意のノード（たとえば、Karen-ルート-）の場合、左側のサブツリー（Bob、Alan、Ellen）のすべてのノードは辞書式にKarenより小さく、右側のサブツリー（Tom、Wendy）のすべてのノードはKarenより大きくなります。
@mellamokbがコメントで指摘しているように、2番目のカレンはそこにいるべきではありません。
そのため、ソートされた配列と同じように、O（log N）時間でこのツリーを二分探索できます。
于 2012-12-26T16:01:27.497 に答える
0
任意のノードの場合：
- 左側のブランチのすべては、アルファベット順に<現在のノードです。
- 右側のブランチのすべては、現在のノードのアルファベット順に並べられています。
これにより、いくつかの固有のプロパティが提供されます
- 検索しているキーが辞書式順序で現在のノードよりも<または>であるかに基づいて、左または右に移動するだけで、任意のノードを見つけることができます。目的地に到着するか、一致しないリーフノード（この場合はキーが存在しません）に
O(Log n)間に合うように到着します。 - 順序どおりのトラバーサルでは、すべてのキーがアルファベット順に表示されます。
于 2012-12-26T16:02:05.553 に答える
0
あなたの例では、それらは各名前の最初の記号の順序を意味していました。
ご覧のとおり、名前の順序は左から右へ、ABCの最初の文字から最後の文字までです。
また、カレン名が2番目に出現する特殊なケースがあります-このツリーのデフォルトの動作は、同じデータが入力された場合、「右に移動」であり、トムと比較したカレン-> KはTが「小さい」ため、それから取り残されます。
いずれにせよ、ここにもっと良い例があります、それからあなたは二分木で注文番号を見ることができます：http: //www.codeproject.com/Articles/4647/A-simple-binary-tree-implementation-with-VB-NET
于 2012-12-26T16:04:23.523 に答える
-1
次の記事は、バイナリ ツリーの概念を理解するのに非常に役立つと思います。また、C/C++ と Java の一般的なコード サンプルも提供しています。
于 2012-12-26T16:12:05.820 に答える