[정글 WEEK05_C언어, 자료구조] Binary Tree 5번_mirrorTree

TODO

1. 이진 트리를 좌우 반전시키기(mirrorTree)

 

제약사항

1. 중위순회(in-order traversal) 사용

---

📦 구조체 분석

1. BTNode

: 이진 트리를 구성하는 노드

   - item: 노드가 가지고 있는 int 타입 데이터

   - left: 왼쪽 자식 노드를 가리키는 포인터(자기 참조 구조)

   - right: 오른쪽 자식 노드를 가리키는 포인터(자기 참조 구조)

typedef struct _btnode {
    int item;
    struct _btnode *left;
    struct _btnode *right;
} BTNode;

 

2. StackNode

: 트리의 노드를 임시 저장하는 스택의 요소. BTNode가 스택에 들어간 순서를 표현하기 위해 필요

   - btnode: 이진트리의 한 노드(BTNode)를 가리키는 포인터

   - next: 스택에서 다음 StackNode를 가리키는 포인터

typedef struct _stackNode {
    BTNode *btnode;
    struct _stackNode *next;
} StackNode;

 

3. Stack

: 스택 노드들의 출입구

   - top: 스택에 저장된 가장 위 StackNode를 가리키는 포인터

typedef struct _stack {
    StackNode *top;
} Stack;

 

 

🪄 기존 함수 분석

createBTNode(int item): item을 값으로 가지는 BTNode를 만든다.

 

createTree(): 스택에 BTNode를 담아서 이진 트리를 만든다.

push(Stack *stack, BTNode *node): 스택에 BTNode를 담는다.

pop(Stack stack): 스택에 저장되어있는 맨 위 BTNode를 삭제한다.

 

printTree(BTNode *node): 중위 순회로 트리 전체 노드를 출력한다.

removeAll(BTNode **node): 이진 트리의 노드를 하나씩 삭제해서 이진 트리를 전체를 삭제한다.

 

 

⚡️ 이진 트리를 좌우 반전시키기 (mirrorTree)

pseudocode

1. 왼쪽 서브트리 mirror

2. 오른쪽 서브트리 mirror

3. 현재 노드의 왼쪽/오른쪽 자식 swap

 

⌨️ 구현

void mirrorTree(BTNode *node)
{
	if (node == NULL)
        return;

    mirrorTree(node->left);
    mirrorTree(node->right);

    BTNode *temp = node->left;
    node->left = node->right;
    node->right = temp;
}