두 갈래 나무의 최대 너비 계산 (비귀속)

1533 단어
PTA 숙제를 하다가 이 문제를 접하고 한 시간 동안 그의 원리를 완전히 이해하는데 나는 정말 멍청하다!!!
이 문제를 생각하면 어떻게 해야만 두 갈래 나무를 층층이 훑어볼 수 있습니까?
그것은 바로 대열로 한 노드가 대열을 낼 때마다 이 대열을 나가는 노드의 좌우 아이를 대열에 넣으면 층차에 따라 두 갈래 나무 전체를 훑어볼 수 있다.
그러면 어떻게 층층이 두루 돌아다니는 기초 위에서 각 층의 두 갈래 나무의 노드를 분할하면 각 층의 두 갈래 나무 노드 수를 누적하는 작용을 할 수 있습니까?
그러면'수량 표시'를 빌려야 한다. 이른바 수량 표시란 변수를 설정하여 이 층의 노드의 수량을 표시하고 대열이 대열에 들어갈 때와 출대할 때 대열의 머리와 대열의 끝 위치 관계의 변화 관계를 이용하여 두 갈래 트리 층을 구분하는 역할을 한다.
그래서 두 갈래 나무의 폭을 구하는 알고리즘의 사고방식은 다음과 같다.
먼저 하나의 대기열을 만들고 하나의 표시 변수로 맨 처음에 팀 끝의 위치를 표시한 다음에 하나의 순환으로 두 갈래 나무를 조작한다. 순환체 내의 조작과 층차가 반복되는 것과 유사하다. 서로 다른 것은 매 순환이 끝난 후에 이전 층의 완성이 편리한지 판단하는 것이다.
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 */
}
Maven 프로젝트의 빈틈 수정
jQuery.validate.js

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage