問題タブ [preorder]

この本で説明されている二分木を使用して、 アルゴリズムとデータ構造で問題を解決しています

次のように定義された preorder traversal メソッドが既にあります。

訪問したノードのリストの戻り値を追加したいだけです。だから私は次のようなことができます

再帰メソッドからリストを返すのに問題があります。「リターン」に到達するとすぐに再帰が停止します

または

何か案は？

すべての要素の (XElement, Preorder , Postorder) のリストを返す C# のすべての要素の preorder と postorder を返す関数が必要です。これどうやってするの？

たとえば、次の XML を使用します。

この答えが必要です：

このクラスを作成しましたが、要素ごとにすべてのノードを処理するため、大きな XML ファイルでは動作が遅くなります。

最近、私の質問は、そうでなくても、このように重複としてマークされました。それでは、以下から始めましょう。次に、質問について説明します。

この質問が重複していないのはなぜですか?

inorder および preorder トラバーサルが与えられたときにバイナリ ツリーを作成する方法を尋ねているわけではありません。inorder+preorder トラバーサルが一意のバイナリ ツリーを定義するという証拠を求めています。

さて、元の質問に。私は面接に行き、面接官は私にこの質問をしました。行き詰まり、先に進めませんでした。:|

質問: バイナリ ツリーの順不同および順順トラバーサルが与えられました。与えられたデータに対して二分木が 1 つしか存在しないことを証明してください。言い換えれば、2 つの異なる二分木が同じ inorder および preorder トラバーサルを持つことはできないことを証明してください。ツリー内のすべての要素が一意であると仮定します (この仮定を指摘してくれた @envy_intelligence に感謝します)。

例を使ってインタビュアーを説得しようとしましたが、インタビュアーは数学的/直感的な証明を求めていました。誰かがそれを証明するのを手伝ってくれますか?

linkedListに変換するために私が書いた主要なメソッドを次に示しますBalanced BinarySearch Tree。わかりますBSTが、バランスが取れていません。なぜそうなのですか？

主な方法は次のとおりです。

これが私が得る出力です（読みやすいようにフォーマットされています）：

レベルの順序と preOrder が一致しないため、一意のツリーが構築されます。ここにヒントはありますか？

Java でBinary Threadedツリーのpreorderトラバーサルのコードを書こうとしています。私は次のコードを書きました。これはいくつかの例に当てはまりますが、いくつかのエッジ シナリオを見落としているのではないかと心配しています。

詳細情報ノードには、ノードの左右の子をそれぞれ指す左右 の 2 つの参照があります。successorと呼ばれるブール フィールドは、正しいポインターが子または後続のトラバーサルを指しているかどうかを決定します (successor==false の場合:右のポインターが子を指し、そうでない場合は、順序どおりのトラバーサル サクセサーを指します) 。

誰かがここで私の論理の欠陥を指摘できれば幸いです...

どんな助けでも大歓迎です... :)

初めてバイナリ ツリーのポストオーダー トラバーサルの問題を解決するとき、ノードを格納するために 1 つのスタックのみを使用し、結果として 1 つのリストを使用します。したがって、時間計算量は明らかに N^2 です。しかし、2 つのスタックを使用する場合、時間の計算量は N に単純化できます。

プレオーダートラバーサルに関しては、1スタックで十分だと思います。しかし、私のソリューションの実行時間はまだ中間レベルにとどまっています。

それで、それを改善するための解決策はありますか？以下は私のコードです：

ありがとうございました！

私はpythonが初めてで、ツリーの予約注文リストを再帰的に返す関数を作成しようとしています。予約注文リストを取得することはできますが、基本ケースとの再帰的な相互作用から、不要な空のリストが大量に発生します。

コードは次のとおりです。

すべてのノードの値だけのリストの出力を取得するにはどうすればよいですか (空のリストなどはありません)。

本当にありがとう、

そこで、単語を辞書ファイルに保存する試みを実装しています。挿入操作を実装しました。今、私は辞書的に印刷しようとしています。私はそれを手に入れようとしていますが、修正方法がわからないという小さな問題があります。また、プログラムの速度にも注意を払っています。そのため、配列または連結リストよりもトライを選択しました。単一のノードは次のようになります。

"end" は、単語の完成を示します (たとえば、単語帳の文字 'k' の end == 1。これにより、単語が実際にツリーに挿入されたかどうかを確認する際の混乱を防ぐことができます)。

メソッドは次のとおりです。

挿入した単語は、boo、book、booking、john、tex、text です。それらはその順序で印刷され、行が区切られている必要があります。私の出力は次のようになります。

これはおそらく、単語の接頭辞が失われないように格納する「ホールド」配列と関係があることを知っています。接頭辞とそれに関連するすべての単語 (boo、book、booking が良い例) の完了を示すために、どこかでインデックスをゼロに戻す必要がありますが、成功していません。どんな助けでも大歓迎です。私の思考プロセスをさらに明確にすることができれば幸いです.

全準順序 (全前順序とも呼ばれます) は、2 つの異なる要素が「同じサイズ」であると見なされることが許される、一種の弱い順序関係です。たとえば、2 つの異なる文字列が同じ長さを持つ可能性があるため、すべての文字列のセットは長さによって準順序付けされます。

ここで、文字列のリストがあり、それを長さで並べ替えたいとします (短い順)。2 つの文字列が同じ長さの場合、どちらが先かは気にしません。一見すると、書くのは理にかなっているように見えます

残念ながら、これは違法です。Comparator インターフェースの Javadoc では、比較が完全な順序付けを実装する必要があることを明確に要求しています。"a".length() - "b".length() は 0 に等しいが、"a".equals("b") は false であるため、これに違反しています。

では、これをきれいにするにはどうすればよいでしょうか。きれいにとは、たとえばハッシュコードや自然な順序付けによる偽の比較を導入しないことを意味します。