java - BST の任意のノードからルートを見つける

Question

特定のノードから二分探索木のルートを見つけるにはどうすればよいですか? より具体的には、特定のノードから祖先を通過しているときに、いつ停止する必要がありますか? Javaにルートを取得する関数はありますか? 私を助けてください。

Answer 1

私はあなたがJavaで独自のBST実装を書いていると仮定していますか？ノードが親ノードへの参照を格納している場合、最終的には、ツリーを上っているときに親が null であるノードに遭遇します。通常、このノードはルートになります。

ノードにそのような参照が保存されていない場合、単一のノードしかない場合、ルートに到達する方法はありません。多くの実装では、親ノードへの参照がありません。これは、メモリを節約し、ツリーの走査中にスタックを使用して処理できるためです (深さ優先走査の場合)。

しかし、あなたが何をしようとしているのか正確にはわかりません。なぜルートノードを見つける必要があるのですか?

Answer 2

独自の BST を実装している場合はNode root;、BST クラスにデータ メンバーが必要です。BST クラスの任意のメソッドからそのデータ メンバーにアクセスするだけで、ルートにアクセス/検索できます。