트리에서 두 노드 사이의 경로 길이를 찾는 방법은 무엇입니까?

-3

트리에서 임의의 두 노드 사이의 경로를 계산하려고합니다 (Java로 구현 됨). 문학에 해결책이 있습니까?트리에서 두 노드 사이의 경로 길이를 찾는 방법은 무엇입니까?

2016-10-21 user840718

데이터 구조, 코드에서 트리를 나타내는 방법에 따라 다릅니다. –

거리 (7, 9) =

이 우리가 계산할 수있는 거리 (루트, 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)이면 어떻게됩니까? 내 트리는 임의적이고 2 진수가 아니므로 결과는 1이어야합니다. 그러나 dist (root, 11) = 1 + dist (root, 15) = 2 -2 * dist (root, lca) = 0 ... 이것은 물론 잘못된 것입니다. 이 문제를 어떻게 다룰 것인가? 아니면이 경우의 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입니다. –

공통 조상을 사용하여 트리에서 두 노드 사이의 거리를 계산할 수 있습니다.

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

출처

2016-10-21 00:42:04

가장 낮은 공통 조상을 찾는 방법은 루트에서 n1과 n2까지의 경로를 비교하는 것입니다. 공유 경로의 마지막 노드는 LCA입니다. –

트리에서 두 노드 사이의 경로 길이를 찾는 방법은 무엇입니까?

답변

관련 문제