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

Binary Tree (5) - mirrorTree 함수 구현하기

트리의 구조를 좌우 반전하는 함수. 임시 트리 생성 없이 현재 트리 내에서 구조를 반전해야 한다.

주어진 요소 확인하기

구조체

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

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

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

mirrorTree 함수의 매개 변수

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

 

핵심 아이디어

• 각 노드마다 재귀적으로 좌우 서브트리를 바꾸기
  • 노드가 NULL인 경우 return 
  • 왼쪽과 오른쪽 자식 노드를 스왑
  • 스왑된 자식들을 다시 재귀적으로 처리

 

구현하기

void mirrorTree(BTNode *node) {
    // 현재 노드가 NULL이면 return
    if (node == NULL) return;

    // 현재 노드의 왼쪽과 오른쪽 자식 노드를 서로 바꿔줌 (스왑)
    BTNode *temp = node->left;
    node->left = node->right;
    node->right = temp;

    // 바뀐 왼쪽 서브트리에 대해 재귀 호출
    mirrorTree(node->left);
    // 바뀐 오른쪽 서브트리에 대해 재귀 호출
    mirrorTree(node->right);
}