問題タブ [binary-tree]

ポストオーダーのリストのみが提供されている場合、ツリーのプレオーダーのリストを見つけるにはどうすればよいですか。また、ツリーでは、すべての非リーフ ノードに 2 つの子があります (つまり、各ノードには 2 つまたはゼロの子があります)。

EDIT：別の仮定は、各ノードのラベルが一意であり、それを内部ノードまたはリーフとして識別するフィールドがあるということです。単一の事前注文または事後注文でツリーを一意に識別できるという曖昧さを取り除く必要があると思います。

二分木は、ノード n に対して、l(n) が n の左の子を与え、r(n) が n の右の子を与えるように、2 つの関数 l および r を使用してエンコードできます。

木の枝は根から葉への経路であり、特定の葉への枝の長さは、根からその葉への経路上の円弧の数です。

MinBranch(l,r,x) を、関数 l および r によってエンコードされたバイナリ ツリーと、バイナリ ツリーのルート ノード x を取得する単純な再帰アルゴリズムとし、バイナリ ツリーの最短ブランチを返します。

このアルゴリズムの疑似コードを提供してください。

ノードに対して次の定義を持つバイナリ ツリーがあるとします。

二分探索木は、key1 に基づいて作成されます。O(1) 空間の key2 に基づいて二分探索木を再配置できるようになりました。ノードへのポインターの配列を使用して、変数空間でこれを行うことができますが。

私がこれを必要とする実際の問題は、「ファイル内の一意の単語の出現回数を数え、頻度の高い順に結果を表示する」ことです。ここで、BST ノードは

データ構造、つまり BST の選択が間違っていますか?

再帰を使用せずにバイナリツリーのポストオーダートラバーサルを実行するためのアルゴリズムは何ですか？

このコードの小さな部分に関する最初の質問のフォローアップとして、これまでに思いついたものよりもうまくできるかどうかを確認するためにフォローアップを依頼することにしました。

以下のコードは、二分木 (左/右 = 子/次) を反復処理します。downここには、条件式 (ブール値)を 1 つ減らす余地があると思います。最速の答えが勝ちます！

1. ステートメントは複数のcntステートメントになる可能性があるため、これが 1 回だけ表示されるようにします。
2. child()およびnext()メンバー関数は、hasChild() および hasNext() 操作の約 30 倍遅くなります。
3. 反復を維持 <-- 提示された再帰的なソリューションがより高速だったため、この要件を削除しました。
4. これは C++ コードです
5. ノードの訪問順序は、以下の例のように維持する必要があります。(最初に親をヒットし、次に子をヒットし、次に「次の」ノードをヒットします)。
6. BaseNodePtr は boost::shared_ptr であるため、割り当てが遅いため、一時的な BaseNodePtr 変数は避けてください。

現在、このコードはテスト ツリー内の 62200000 ノードにアクセスするのに 5897 ミリ秒かかり、この関数を 200,000 回呼び出しています。

ノードの定義は次のとおりです。

私がやろうとしているのは、祖先ノードを指すすべてのノードをリストすることです。間違った解決策を投稿し、答えからアドバイスを受けた後、私の新しい解決策は次のとおりです。

二分木を再帰的に調べます。現在のノードをノードの配列に追加してから、現在のノードの子が前の祖先ノードのいずれかを指しているかどうかを確認します。

デフォルトのケースは、ノードがNULLの場合です。その場合、関数は戻ります。

それがどのように機能することになっているのか：

ノードを配列に追加します

左の子がNULLかどうかを確認します。

そうでない場合は、子を前の各ノードと比較します。

障害が見つかった場合は、それを報告します。

そうでない場合は、子を引数として関数を呼び出します。

終了するまで繰り返します。（二分木のrhsについても同じです）

質問：

• 配列はノードを格納するのに最適ですか？
• これは機能しますか？for（i = 0; i <sizeof（arrOfNodes）/ sizeof（node）; i ++）
• 関数は再帰的であるため、配列と配列インデックスは関数内で初期化できません（または初期化できますか？）。グローバルにする必要がありますか？
• 2つのアレイがある方が良いでしょうか？（1つはLHS用、もう1つはRHS用）

コード：

これはしばらくの間私を悩ませてきました。二分探索木の形で配置するN個のキーが与えられた場合、作成できるツリーの可能な数は、カタラン数列のN番目の数に対応することを知っています。

私はこれがなぜであるかを決定しようとしてきました。それを直感的に説明しようとするかもしれないものを見つけることができない私はSOの集合的な知識に頼ります。可能な木の数を計算する他の方法を見つけましたが、それらは直感的ではないようで、使用方法以外の説明はありませんでした。さらに、wikiページ（上記のリンク）には、3つのキーを使用して可能な樹木形成の画像も表示されます。これにより、適切でわかりやすい説明が聞こえると思います（言うまでもなく、記事には含まれていません）。 ）。

前もって感謝します！

二分探索木用のSTLライクなコンテナを書いています。Tree 自体のテンプレート クラスとネストされたクラス TreeNode があります。
私の質問は、キーを比較するバイナリ述語関数をツリークラスまたはノードクラスのどこに配置する必要があるかです。Tree クラスに入れることにした場合、すべてのノードはキーを比較する方法を知りません:(
そして、Node クラスの場合、この関数を静的にする必要がありますか?

特定の走査方法 (インオーダー、ポストオーダー、またはプリオーダー) からバイナリ ツリーを見つけるにはどうすればよいですか?