問題タブ [binary-tree]

このツリーを表す (A (B (CD)) (E (F))) のようなリストがあります。

(ABECDF) として印刷するにはどうすればよいですか?

これは私が管理した限りです：

しかし、それは印刷します：

私は Common LISP にかなり慣れていないので、使用すべき関数があるかもしれません。その場合は、私を啓発します。

ありがとう。

私はこのコードを書きました

これらのエラーがあります

タイプx.Program.TreeNode'を'int'に暗黙的に変換することはできません//findminで

タイプx.Program.TreeNode'を'int'に暗黙的に変換することはできません//findmaxで

そして、私の主なものは正しいですか、それとも何かが欠けていますか？

そして、どのようにノードを数え、葉を残し、高さを取得することができますか（ヒントのみが必要です）

次のコード スニペットに問題があります。

次のエラーが表示されます。

これらのエラーを修正する方法について何か考えはありますか?

こんにちは、Marc Gravell の助けを借りてこのコードを作成しました

BinarySearchTree で _left と _right が見つからないのはなぜですか?
&
BST C# コードの暗黙的な変換エラーを修正するにはどうすればよいですか?

、その Binary search tree ですが、論理エラーが発生し、結果が間違っています。コードの出力は次のとおりです。

最後の 2 つの数字は、挿入された要素の合計を 6 にする必要がありますが、9 を示しています

としかし、どうすれば木の高さを取得できますか?!

事前に感謝し、Marc Gravell に特別な感謝を捧げます。

二分木（BSTではない）の順序通りのトラバーサル（パンケーキとも呼ばれます）について、少し前に受講した学術コースからの次のテキストがあります。

順序付けされたツリー トラバーサル

木の外側に線を引きます。ルートの左側から始めて、ツリーの外側を一周し、ルートの右側で終了します。できるだけ木に近づきますが、木を横切らないでください。(ツリー — その枝とノード — を堅固な障壁と考えてください。) ノードの順序は、この線がその下を通過する順序です。ノードの「下」に移動するタイミングがわからない場合は、常に「左側」のノードが最初に来ることを覚えておいてください。

使用した例を次に示します (以下のツリーとは少し異なります)。

しかし、Google で検索すると、矛盾する定義が表示されます。たとえば、ウィキペディアの例:

順序付けされたトラバーサル シーケンス: A、B、C、D、E、F、G、H、I (leftchild、rootnode、right node)

しかし、定義＃1（の私の理解）によれば、これは

A, B, D, C, E, F, G, I, H

どの定義が正しいか誰でも明確にできますか? どちらも異なるトラバーサル メソッドを記述している可能性がありますが、たまたま同じ名前を使用しています。査読済みの学術論文が間違っているとは信じられませんが、確信は持てません。

ウィキペディアを引用：

従来のバイナリ ツリー データ構造を使用してバイナリ ヒープを実装することはまったく問題ありません。アルゴリズムで解決 できる要素を追加するときに、バイナリ ヒープの最後のレベルで隣接する要素を見つけることに問題があります...

そのようなアルゴリズムがどのように機能するかについてのアイデアはありますか?

ほとんどのバイナリ ヒープは配列を使用して実装されているため、この問題に関する情報は見つかりませんでした。

どんな助けでも感謝します。

最近、OpenID アカウントを登録しましたが、最初の投稿やコメントの回答を編集できません。そのため、この回答で回答しています。申し訳ありません。

ミッチ・ウィートの引用：

@Yse：「バイナリヒープの最後の要素を見つけるにはどうすればよいですか」という質問はありますか？

はい、そうです。または、より正確に言うと、私の質問は、「非配列ベースのバイナリ ヒープの最後の要素を見つけるにはどうすればよいですか?」です。

Suppressingfire の引用:

この質問をしている文脈はありますか？(つまり、解決しようとしている具体的な問題はありますか?)

上記のとおり、ノードの挿入と削除に必要な「非配列ベースのバイナリヒープの最後の要素を見つける」ための良い方法を知りたいです。

ロイの引用：

通常のバイナリ ツリー構造 ([data, pLeftChild, pRightChild] として定義された pRoot と Node を使用) を使用し、2 つの追加ポインター (pInsertionNode と pLastNode) を追加するのが最も理解しやすいようです。pInsertionNode と pLastNode は両方とも、挿入サブルーチンと削除サブルーチン中に更新され、構造内のデータが変更されたときにそれらを最新の状態に保ちます。これにより、構造体の挿入ポイントと最後のノードの両方に O(1) アクセスできます。

はい、これでうまくいくはずです。私が間違っていなければ、削除/挿入のために場所が別のサブツリーに変更されたときに、挿入ノードと最後のノードを見つけるのが少し難しいかもしれません。しかし、私はこれを試してみます。

ザック・スクリヴェナの引用:

深さ優先検索を実行するのはどうですか...

はい、これは良いアプローチです。私もそれを試してみます。

それでも、最後のノードと挿入ポイントの位置を「計算」する方法があるかどうか疑問に思っています。N 個のノードを持つバイナリ ヒープの高さは、N よりも大きい最小の 2 のべき乗の (2 を底とする) 対数を取ることで計算できます。おそらく、最も深いレベルのノード数も計算できます。次に、挿入ポイントまたは削除用のノードに到達するためにヒープをどのようにトラバースする必要があるかを判断することができた可能性があります。

二分探索木の検索時間を計算する方法を知っている人はいますか (つまり、最悪の場合、最良の場合、平均的な場合)?

AVL-treeでノードのバランスを計算する最良の方法を探しています。私はそれが機能していると思っていましたが、いくつかの重い挿入/更新の後、正しく機能していないことがわかりました(まったく)。

これは一種の 2 つの部分からなる質問です。最初の部分は、サブツリーの高さを計算する方法です。「ノードの高さは、そのノードから葉までの最長の下り経路の長さです」という定義を知っています。 ." 私はそれを理解していますが、実装に失敗しています。さらに混乱させるために、ツリーの高さに関するウィキペディアでこの引用を見つけることができます。

2番目の部分は、AVLツリーのサブツリーのバランス係数を取得することです。 「あなたLとサブツリーの高さを取得してからR差し引く」RLという概念を理解するのに問題はありません。そして、これは次のように定義されています。BALANCE = NODE[L][HEIGHT] - NODE[R][HEIGT]

ウィキペディアを読むと、AVL ツリーへの挿入を説明する最初の数行で次のように述べられています。

続いて、「バランス ファクターが 2 または -2 になる場合、このノードをルートとするツリーはバランスが取れていないため、ツリーのローテーションが必要です。ツリーのバランスをとるには、せいぜい 1 回または 2 回のローテーションが必要です。」- 問題なく把握できます。

しかし（はい、常にしかしがあります）。

ここで混乱します。テキストには、「R のバランス係数が 1 の場合、そのノードの (外部) 右側で挿入が発生し、左回転が必要であることを意味します」と記載されています。しかし、私が引用したように、バランス係数が範囲内[-1, 1]にある場合、バランスをとる必要はないとテキストが述べていることを理解していますか?

概念の理解に非常に近づいていると感じています。ツリーのローテーションを減らし、通常のバイナリ検索ツリーを実装し、AVL ツリーを把握しようとしていますが、その本質的なひらめきが欠けているようです。

編集：私は常にコードで何かを把握するのが簡単だったので、コード例は学術的な公式よりも好まれていますが、どんな助けも大歓迎です.

編集：すべての回答を「承認済み」としてマークできたらいいのにと思いますが、私にとっては、NIckの回答が最初に「あはは」になったものでした。

商用/フリー ソフトウェア プロジェクトで使用されているツリー構造の例を探しています。ウィキペディアで例を見ることができますが、より具体的な例とその使用方法を探しています。たとえば、データベースの主キーは（私が読んだことから）BST構造またはBSTのバリエーションに保存されています（これについてはお気軽に修正してください）

私の質問は二分探索木 (BST) に限らず、赤黒、AVL などのバリエーションを含めることができます。

ノードをツリーに順番に挿入しようとしています。私の機能は正常に動作します...ノードが3つしかない場合。

私はこのコードを持っています:

これに加えて：

}

ここで何が問題なのかはわかっていますが、それを修正する方法がわかりません。これは、ルート ノードに接続されている 2 つのノードを上書きするだけです。すなわち

ノード 4 を追加できません。入力に応じて、ノード 2 または 3 を上書きするだけです。デバッグと少しの調査の後、ここからどこに行くべきかよくわかりません...

誰かが助けてくれれば、本当に感謝しています。