두 갈래 나무의 최대 너비 계산 (비귀속)
이 문제를 생각하면 어떻게 해야만 두 갈래 나무를 층층이 훑어볼 수 있습니까?
그것은 바로 대열로 한 노드가 대열을 낼 때마다 이 대열을 나가는 노드의 좌우 아이를 대열에 넣으면 층차에 따라 두 갈래 나무 전체를 훑어볼 수 있다.
그러면 어떻게 층층이 두루 돌아다니는 기초 위에서 각 층의 두 갈래 나무의 노드를 분할하면 각 층의 두 갈래 나무 노드 수를 누적하는 작용을 할 수 있습니까?
그러면'수량 표시'를 빌려야 한다. 이른바 수량 표시란 변수를 설정하여 이 층의 노드의 수량을 표시하고 대열이 대열에 들어갈 때와 출대할 때 대열의 머리와 대열의 끝 위치 관계의 변화 관계를 이용하여 두 갈래 트리 층을 구분하는 역할을 한다.
그래서 두 갈래 나무의 폭을 구하는 알고리즘의 사고방식은 다음과 같다.
먼저 하나의 대기열을 만들고 하나의 표시 변수로 맨 처음에 팀 끝의 위치를 표시한 다음에 하나의 순환으로 두 갈래 나무를 조작한다. 순환체 내의 조작과 층차가 반복되는 것과 유사하다. 서로 다른 것은 매 순환이 끝난 후에 이전 층의 완성이 편리한지 판단하는 것이다.
typedef struct TreeNode *BinTree;
struct TreeNode
{
int Key;
BinTree Left;
BinTree Right;
};
int Width( BinTree T )
{
BinTree p;
Queue Q;
int Last, temp_width, max_width;
temp_width = max_width = 0;
Q = CreateQueue(MaxElements);
Last = Queue_rear(Q);//
if ( T == NULL) return 0;
else
{
Enqueue(T, Q);//
while (!IsEmpty(Q))
{
p = Front_Dequeue(Q); //
temp_width++;
if ( p->Left) Enqueue(p->Left, Q);//
if (p->right) Enqueue(p->right, Q);//
if ( Queue_front(Q) > Last ) //
{
Last = Queue_rear(Q);//
if ( temp_width > max_width ) max_width = temp_width;
temp_width = 0;
} /* end-if */
} /* end-while */
return max_width;
} /* end-else */
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.