ツリー内の2つのノード間のパスの長さを調べる方法は？

-3

ツリー内の任意の2つのノード間のパスを計算したい（Javaで実装されている）。文献にはどのような解決策がありますか？ツリー内の2つのノード間のパスの長さを調べる方法は？

2016-10-21 user840718

これは、データ構造、コード内のツリーの表現方法によって異なります。 –

距離（7、9）=

2我々は計算することができ、距離（ルート、7）= 2、及び計算距離（ルート：

はこのようなものであるべき、9）= 2、LCA（7,9）= 8。LCAは「最も低い共通祖先」を表します。したがって、distance(7, 9) = distance(root, 7) + distance(root, 9) - 2*distance(root, LCA) = 2 + 2 - 2*1 = 2

これでメソッドを見ることができます。あなたの本当の問題は、距離（ルート、anyNode）の計算方法です。これは一般的な質問です。私はあなたがすぐに任意のノードへの距離を見つける方法を見つけることができると仮定します。

出典

2016-10-21 01:24:08

入力がdist（11,15）の場合はどうなりますか？私の木は任意でバイナリではないので、結果は1になります。しかし、dist（root、11）= 1 + dist（root、15）= 2 -2 * dist（root、lca）= 0 ... so 3。これはもちろん間違っています。どのようにこの問題に対処するには？あるいは、この場合のlcaは11そのものでしょうか？ – user840718

はい！ dist（root、11）+ dist（root、15） - 2 * LCA（root、LCA）= 1 + 2 - 2 * 1 = 1 LCAは11です。その「最も低い共通祖先」を見つけようとするときは、常にルートから始めます。したがって、node11のパスは10-11であり、node15のパスは10-11-15なので、LCAは11です。 –

共通の祖先を使用して、ツリー内の2つのノード間の距離を計算できます。

Dist(n1, n2) = Dist(root, n1) + Dist(root, n2) - 2*Dist(root, lca)

出典

2016-10-21 00:42:04

そして最も共通の祖先を見つける方法は、ルートからn1とn2のそれぞれのパスを比較することです。共有パス上の最後のノードはLCAです。 –

ツリー内の2つのノード間のパスの長さを調べる方法は？

答えて

関連する問題