java - Javaを使用してバイナリツリーの最大深度に含まれるノードのリンクリストを作成する方法

Question

バイナリツリークラスとリンクリストクラスはすでに作成しましたが、最大のパスのノードのみを出力するアルゴリズムが必要です。二分木の高さとサイズはすでにルートノードに保存されていますが、私の問題は、各ノードをリンクリストに追加するときに最大のパスのみをトラバースすることです。

Answer 1

私はあなたの二分木ノードがそれらの親への参照を持っていると思います、そうですか？次に、幅優先探索または深さ優先探索のいずれかを使用して、深さが最大深度に等しいルートノードを見つけることができます。そのようなノードを1つ見つけたら、そこから親ノードの軌跡をたどり、途中で各ノードをリンクリストに追加します。一番上に到達すると、リンクリストには最大パスのすべてのノードが含まれます。

このアルゴリズムは次のようになります。

1. 二分木のルートから開始します
2. 幅優先または深さ優先検索を使用して、リーフノード（子ノードを持たないノード）に到達します。
   1. リーフノードに到達したら、その深さを確認します。
      1. 最大深度と等しくない場合は、無視して検索を続行します
      2. 最大深度に等しい場合は、最大のパスのエンドノードが見つかりました（複数存在する可能性がありますが、この時点でそれらを区別することは重要ではないようです）。次のステップに進みます
3. このリーフノードをリンクリストに追加してから、その親に移動します
4. ルートノードに到達し、親がなくなるまで、この最後の手順を繰り返します。その場合、リンクリストには最長パスのすべてのノードが含まれます。

ノードの順序はリーフノードからルートまでであることに注意してください。逆にする必要がある場合は、最後の手順の後で行うことができます。

Answer 2

バイナリツリーデータ構造を作成し、ダミーデータで埋め、深さまたは幅優先探索でツリーをトラバースし、最長パスのノードのリンクリストを作成します。

オンラインにはたくさんの擬似コードと詳細情報があります。

http://en.wikipedia.org/wiki/Binary_tree

http://en.wikipedia.org/wiki/Linked_list

http://en.wikipedia.org/wiki/Breadth-first_search

http://en.wikipedia.org/wiki/Depth-first_search

あなたはすでにJavaを理解していて、完全にゼロから始めているわけではないと思いますか？

Javaに苦労しているなら、Objects First with Javaは素晴らしい本であり、アルゴリズム入門はアルゴリズムに関する標準的な本のようであり、一見の価値があるかもしれません。