c# - 二分木図の作成

Question

これは二分木図です。ダイアグラムがどのように作成されたかを理解するのに苦労しています。一番上に5つありますが、次に来る番号とその順序をどのように決定しますか？誰かが私にこのステップバイステップを教えてもらえますか？

Answer 1

そのリンクの図について特に混乱しているようです。ダイアグラムにエラーがあるようです。

他の人が言っているように、複数の有効な配置がありますが、ソートされたバイナリツリーの要件は、各ノードの左側のサブツリーには小さな要素のみが含まれ、右側のサブツリーには大きな要素のみが含まれることです。

あなたの質問で提供されたリンクの図では、6> 5であるため、これに違反しています。要素6は5の右側のサブツリーに属しており、作成者による単純な間違いのようです。

Answer 2

もちろん、

これが二分木だとおっしゃいましたね。これがアルゴリズムです。新しい数値を挿入するとき、数値が小さい場合は左に移動し、大きい場合は右に移動します。二分木を生成するためのこのアプレットをチェックして、その仕組みを理解する必要があります

アプレットへのリンク

Answer 3

数値の特定の配置は標準的ではありません (つまり、他の有効な配置が存在します)。唯一の要件は、各ノードの左側のサブツリーには小さなノードのみが含まれ、右側のサブツリーには大きなノードのみが含まれることです。

特定の配置に到達する方法は、それを設定するために使用されるアルゴリズムと、値が挿入される順序によって異なります。これは、「ツリーのバランスをとる」セクションの記事で部分的に説明されています。挿入するときは、ツリーのバランスを保つ必要があります。どのくらいの頻度でリバランスを行うか、またどのようにリバランスを行うかは、何百万ページもの教科書、研究論文、およびコード行の主題です。

要するに、あなたの質問に対する答えは「場合による」です。

バランスの取れたツリーを生成するとは限らないナイーブな実装の場合、各挿入は単純にツリーをたどり、現在訪問しているノードよりも数値が小さい場合は左に移動し、大きい場合は右に移動します (同じ値を無視する必要があります)。発生しないようにするか、それらを処理するためのポリシーを決定します)。行き止まり (つまり、NULL の左ポインタまたは右ポインタ) に到達したら、挿入された値を使用してそこに新しいノードを作成します。

サイドバー: ナイーブ アルゴリズムは、その単純さのおかげで、まれに必要なものになる場合があることに注意してください。挿入する前に入力データをランダムにシャッフルするだけで、不均衡なツリーを回避できます。ただし、ほとんどの場合、バイナリ ツリーを使用しない方がよいでしょう。ほとんどの場合、ハッシュ テーブルが推奨されます。