問題タブ [binary-search-tree]

が赤黒木std::mapとして実装されるのはなぜですか?

バランスの取れた二分探索木(BST)がいくつかあります。赤黒木を選択する際の設計上のトレードオフは何でしたか?

BST を使用してデータベース インターフェイスを実装しようとしています。変数キー、値、および左右のノードを持つノードを表す内部クラス BTSEntry があります。左の各ノードは親より (アルファベット順で) 小さく、右の各ノードは親より大きくなっています。

最初の問題は、Entry 内部クラスの "nextNode()" が何であるかがわからないことです。それは単に正しいノードですか？それとも私が下でやったことですか？

2 つ目の問題は、"Int value get(Str key)" メソッドの実装方法がよくわからないことです。編集: get(key) メソッドを実行しようとしました。それが正しいか？これで再帰は機能しますか？

これが私がこれまでに行ったことです。どんな助けでも大歓迎です！:)

学校の課題では、ノード要素の配列を昇順で返すメソッドを完了することになっています。ノードは二分探索木で組み立てられているので、それらを正しくソートするために、ジョブを実行するための再帰的なメソッドを作成するためのヒントを得ました。

問題は、これがテスト出力に従ってコレクション内のすべての要素を生成しないことです（java.lang.AssertionError：toArray（）はコレクション内のすべての要素を返しません）。

配列を処理する他の方法を思い付くことができず、再帰が機能するかどうかもよくわかりません。どんな助けでも大歓迎です。以下は私のコードです：

テスト出力：

java.lang.AssertionError：toArray（）は、コレクション内のすべての要素を返しません。：TestPerson（ "Bender"）。compareTo（TestPerson（ "Fry"））== 0 expected：trueが、inf1010.assignmentでwas：false .IfiCollectionTest.assertCompareToEquals（IfiCollectionTest.java:74）at inf1010.assignment.IfiCollectionTest.assertCompareToEquals（IfiCollectionTest.java:83）at inf1010.assignment.IfiCollectionTest.assertCompareToEqualsNoOrder（IfiCollectionTest.java:100）at inf1010. IfiCollectionTest.java:202）

テストコードをもっと投稿する必要があるかどうかわかりません。非常に広範で、1つの投稿には少なすぎるかもしれません。

プレオーダー、インオーダー、ポストオーダーのトラバーサルを知っています。BST を再構築するアルゴリズムは何ですか?

BST 用にいくつかのメソッドをコーディングする必要があり、いくつか問題があります。説明させてください。

私は次の構造を持っています:

と

次の機能とともに：

と

そして、私のメインでは、これを呼び出す必要があります（たとえば）：

私がしなければならないことは、再帰を使用して関数 insertKey(int i, struct tree *T) を作成することです。

私は何かをしたかった

再帰を使用すると、insertKey を再度呼び出すことができますが、ノードとツリーを同じように使用することはできないようです。

指定された構造を変更せずにそれを行う方法を知っている人はいますか?

どうもありがとうございました。

次のようなエラーが発生しました：

mybst.cpp：262：エラー：'*'トークンの前にコンストラクタ、デストラクタ、または型変換が必要です

主な理由はこの関数にあります：

leaf *＆tree :: createBST（int preOrder、int inOrder、int len）

{pre、in、post}順序トラバーサル結果を使用してBSTを再構築する方法によって提供されるこのアルゴリズム

なぜこのエラーが発生するのですか？

****************編集:****************************

コンパイルフリーエラー。しかし、実行後にセグメンテーション違反が発生しました。

gcc で実行します。

主な問題は機能にあります

注：これについて2つの質問を投稿しました。コードをたくさん変更したので、新しい投稿を始めました。

これはヘッダーファイルです。関数について理解していませんがsearch、なぜ戻り型なのnode**ですか？

編集：ここに検索機能を追加：

私は 1 からキーを挿入する BST を持っています... n ランダムに (すべての順列は 1/n! の確率で行われます)。私の質問は、順列が均一であっても、結果のツリーが均一でないのはなぜですか?