6-8 두 갈래 나무 높이(20분) 귀속과 비귀속 방법 구하기

6831 단어
이 문제는 두 갈래 나무의 높이를 정할 것을 요구한다.
함수 인터페이스 정의: int GetHeight(BinTree BT);
여기서 BinTree 구조는 다음과 같이 정의됩니다.
typedef struct TNode *Position; typedef Position BinTree; struct TNode{ ElementType Data; BinTree Left; BinTree Right; };
함수에 지정된 두 갈래 트리 BT의 높이 값을 되돌려 달라고 합니다.
심판 테스트 프로그램 예: #include #include
typedef char ElementType; typedef struct TNode *Position; typedef Position BinTree; struct TNode{ ElementType Data; BinTree Left; BinTree Right; };
BinTree CreatBinTree();/* 세부 정보 무시 */int GetHeight(BinTree BT);
int main() { BinTree BT = CreatBinTree(); printf("%d", GetHeight(BT)); return 0; }/* 당신의 코드는 여기에 박혀 있을 것입니다 */
샘플 내보내기(그림에 표시된 트리의 경우):

먼저 비귀속 코드를 말하자면 비귀속 코드는 두 갈래 나무의 차원을 바탕으로 하기 때문에 두 갈래 나무의 차원 역행 비귀속 코드는 매우 익숙해야 많은 문제를 유연하게 해결할 수 있다!
int GetHeight( BinTree BT ){
    if(BT==NULL){
        return 0;
    }
    int height = 0;
    int count = 0; //   
    int nextCount = 1;// 
    BinTree a[100];
    int front =0;
    int rear = 0;
    a[rear++] = BT;
    while(front<rear){
                count++;
        BinTree p = a[front++];
        if(p->Left){
            a[rear++] = p->Left;
        }
        if(p->Right){
            a[rear++] = p->Right;
        }
        if(count==nextCount){  // 。
            height++;
            nextCount = rear-front;// 
            count = 0;
        }
        
    }
    return height;
}

귀속적 방법
int GetHeight( BinTree BT ){
 if(BT==NULL) return 0;
  int l,r;
  l = GetHeight(BT->Left);
  r = GetHeight(BT->Right);
  return (l>=r?l:r)+1;
} 


좋은 웹페이지 즐겨찾기