問題タブ [binary-tree]

文字データを格納する 2 つのバイナリ ツリー T1 と T2 があり、重複は許可されます。
T2 が T1 のサブツリーであるかどうかを調べるにはどうすればよいですか? .
T1 には数百万のノードがあり、T2 には数百のノードがあります。

各ノードが値を持つことができる二分木があります。

ツリー内で値がnullで、ルートに最も近いノードを見つけたいと思います。ルートから同じ距離にある2つのノードがある場合は、どちらでもかまいません。二分木への読み取りアクセスの数を最小限に抑える必要があります。作業メモリーがkノードのみに制限されていると想定します。

深さkまでのDFSは網羅的ですが、最初にツリー全体を実行しない限り、最も近いノードは見つかりません。BFSは最も近いものを見つけますが、DFSは同じメモリでより深いヌルを見つけることができるため、失敗する可能性があります。

ツリーへの読み取りアクセスの数を最小限に抑えて、最も近いnullノードを見つけたいと思います。

（最終的にはこれをn-wayツリーにも実装する必要があるため、一般的な解決策が適切です。ツリーへの書き込みアクセスはなく、読み取りのみです。）

BST の葉のすべての値を合計したい。どうやら、ツリー全体を横断しないと葉に到達できないようです。これは本当ですか？O(N) 時間をかけずに葉にたどり着くことができますか?

これはインタビューの質問です

解決策を考えます。キューを使用します。

キューを使用しない、これよりも優れたソリューションを考えられるものはありますか?

二分木で特定の値を検索する反復関数を作成しています。これは、クラスをジェネリック化する方法を説明するまでは、signed int にローカライズされています。

私のクラスが BinarySearchTree で、ツリーのルート ノードへのポインターがあるとします。また、挿入関数によってノードが挿入され、2 つの子へのポインターがあるとします。以下は Node 構造体のかなり省略されたバージョンです:

したがって、ノードの uninit ポインターが NULL になると安全に想定できます。

これが私のコードです：

このコードは、次の 2 つの理由で友人によって拒否されています。

1) next に子がない場合、両方ともゼロと評価され、途中でループを終了します (検索された val を next の値に対してチェックすることはありません)。

2) next に 1 つの子があるが、検索しているデータがツリーの空の側にある必要がある場合、next は 0 に設定され、next (0 である) を左右で比較して再びループします。のようなツリーwhile(0->left())で、未定義の動作が発生します。

両方の問題の解決策はループ状態にあると言われていますが、状況を簡単に修正するために何ができるかわかりません。Stack Overflow のコミュニティは洞察を提供できますか?

再帰アルゴリズムを使用してBSTの最も深いパスを配列に入れようとしていますが、いくつかの問題が発生しています...取得できる唯一のものは最長パスのサイズ(高さに相当)であり、できないためですBSTの高さに関する値を配列に入れます...

何か助けはありますか？

申し訳ありませんが、問題を完全に公開しませんでした。このアルゴリズムを実行するために私が知っている唯一のことは、次の署名です。

(補助メソッドを使用できます)

私の削除がツリーを順番に (左から右へ) バランスを取り直そうとすると仮定します。

私は現在 BinarySearchTree クラスを書いていますが、ほとんどの場合、私の削除機能は現在機能しています (私は <3 を願っています)。私は対処すべきいくつかのフリンジケースを持っています:

• 親ノードがないため、ルート ノードを削除しても機能しません。
• next に 2 つの子がある最後のケースでは、その左端の一番右の子孫が右の子自体である場合、newCurr は next を指します。これは、newCurr (別名 next) が New と交換されるため、問題を引き起こします。

ルート削除の提案された解決策:

1. 私の解決策は、ルートを削除し、BST クラスのメンバー関数を使用して Root を New に設定し (そのノードをルートにする)、New があった場所を 0/NULL に設定することです。

   A: これは機能しますが、ケースワークをあちこちに配置する必要があります。

2. BST クラスにダミーの親ノードを用意します。このノードは単にルート ノードを右側のオブジェクトとして持ちます (billyswong による提案)。

   A: これでうまくいくかもしれませんが、それに対処するには特別なケースの作業が必要だと思います。

2 人の子供を削除するための提案された解決策:

1. 私の解決策は、New の場所を一時的に保存し、親の New の場所を New の右の子に設定してから、一時ポインタを削除することです。

   A: これは機能しますが、私が思っているほどエレガントではありません。

2. 「ノードを回転させます」（Agorが提案した方法がわからない）。

これが私のコードです：

ポスターは、このコードが 1) 機能するかどうか、2) 最適かどうか教えてください。

編集:関数の終わり近くで一貫性のないキャメルキャップの使用について申し訳ありません。変数名のより良い説明は思いつきませんでしたがnew、C++ で定義されたキーワードです。

Edit2: リファクタリングされたコードを投稿しましたが、エラーは解決しません。

VB6を使用してバイナリツリーを描画するためのコントロールを取得できる無料のリソースへのリンクを誰かが持っているかどうかを尋ねる必要があります。VB6 の TreeView コントロールについて言っているわけではないことに注意してください。

次のような二分木を描画するためのコントロールが必要です

1

/\

2 3

/\ /\

4 5 6 7

私はこれを理解しようとすると大変な時間を過ごしています。どこを見ても、リストを非再帰的にトラバースする方法（実際に理解している部分）についての説明に出くわしているだけのようです。誰かが最初にリストを調べて実際の先行/後続ノードを見つけてノードクラスでそれらにフラグを立てることができる方法を正確に理解できますか？単純なバイナリ検索ツリーを作成し、リストを調べて、ヌルリンクを先行/後続に再ルーティングできるようにする必要があります。私は次のような解決策で運が良かった：

私は2つの理由でバイナリ検索ツリーテンプレートを書いています-C++を学ぶことと、最も一般的なアルゴリズムとデータ構造を学ぶことです。
それで、ここに質問があります-私がイテレータを実装したい限り、ツリーがどこで終わるかについての厳密な定義はないように私には思えます。あなたの提案は何ですか？どうすればよいですか？