두 갈래 나무 중 가장 먼 두 잎 노드의 거리를 구하다
두 갈래 나무 한 그루(비두 갈래 검색 나무)를 정해서 두 갈래 나무 중 가장 먼 두 잎 노드 사이의 거리를 구합니까?그 중에서 두 잎 사이의 거리는 다음과 같이 정의된다. F(X, Y) = 노드 X에서 루트 노드 경로까지의 모든 노드 데이터의 합 + 노드 Y에서 루트 노드 경로까지의 모든 노드 데이터의 합 - X와 Y의 첫 번째 조상 노드에서 루트 노드 경로까지의 모든 노드 데이터의 합이다.
생각:
1. 모든 노드를 뒤따라 이 노드에서 가장 오른쪽까지의 거리와 가장 왼쪽까지의 거리를 찾아낸다.
2, 가장 큰 것을 찾으면 된다.
struct TNode
{
int data;
TNode * left_child;
TNode * right_child;
}
void FindMax( TNode *pNode, int &max_distance, int &tot_distance )
{
if( pNode == NULL )
{ max_distance = 0;
tot_distance = 0;
return;
}
else
{
int left_max_distance;
int left_tot_distance;
int right_max_distance;
int right_tot_distance;
FindMax( pNode->left_child, left_max_distance, left_tot_distance);
FindMax( pNode->right_child, right_max_distance, right_tot_distance);
tot_distance = left_max_distance + right_max_distance + pNode->data;
max_distance = left_max_distance>right_max_distance?(left_max_distance+pNode->data):(right_max_distance+pNode->data);
tot_distance = tot_distance>left_tot_distance?tot_distance:left_tot_distance;
tot_distance = tot_distance>right_tot_distance?tot_distance:right_tot_distance;
}
}
main()
{
FindMax( pNode, max_distance, result);
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
