[C언어] Binary Tree (2) - maxHeight 함수 구현하기

Binary Tree (2) - maxHeight 함수 구현하기

루트 노드부터 가장 깊은 리프 노드(자식이 없는 노드)까지의 최대 링크 수(높이)를 반환하는 함수

주어진 요소 확인하기

구조체

• BTNode: (struct) 이진 트리 노드 구조체
  • item: (int field) 노드의 값
  • *left: (pointer field) 왼쪽 자식 노드 주소
  • *right: (pointer field) 오른쪽 자식 노드 주소

• StackNode: (struct) 트리 생성을 위한 스택 노드 구조체
  • *btnode: (pointer field) 이진 트리 노드 주소
  • *next: (pointer field) 다음(스택 아래쪽) 노드 주소

• Stack: (struct) 트리 생성을 위한 스택 구조체
  • *top: (pointer field) 스택 최상단 노드의 주소

maxHeight 함수의 매개 변수

• *node: (pointer) 이진 트리 루트 노드 주소

 

핵심 아이디어

• 재귀적으로 좌우 서브트리 중 더 깊은 쪽의 높이에 +1을 해서 반환
  • 노드가 NULL이면 높이는 -1로 간주
  • 왼쪽과 오른쪽 서브트리의 높이를 비교해 더 큰 값에 +1을 해서 반환

 

구현하기

int maxHeight(BTNode *node) {
    // 노드가 없으면 (즉, 트리가 비었으면) 높이는 -1
    if (node == NULL) return -1;

    // 왼쪽 서브트리의 최대 높이를 재귀적으로 계산
    int left = maxHeight(node->left);
    // 오른쪽 서브트리의 최대 높이를 재귀적으로 계산
    int right = maxHeight(node->right);

    // 왼쪽과 오른쪽 중 더 큰 쪽의 높이에 +1(현재 노드 포함)을 해서 반환
    if (left >= right) {
        return left + 1;
    } else {
        return right + 1;
    }
}