5. Tree (2) - Binary Tree

Binary Tree (이어서)

 

이진 트리에서 수행하는 주요 연산은

• 순회 (Traversal)
• 복사 (Copy)
• 동등성 검사 (Equality Test)
• 만족 가능성(Satisfiability) 문제 해결

이렇게 네가지가 있음.

---

1.  Binary Tree Traversals (이진 트리 순회)

트리 순회란 트리의 모든 노드를 특정한 규칙에 따라 한 번씩 방문하는 과정임.
이진 트리에서는 다음 세 가지 기본 순회 방법이 있음.

 

1) 전위 순회 (Preorder Traversal)

방문 순서: Root → Left Subtree → Right Subtree (V L R)

즉, 현재 노드를 먼저 처리하고 나서 왼쪽, 오른쪽으로 내려감.

void preorder(TreeNode* root) {
    if (root != NULL) {
        printf("%d ", root->data);  // root
        preorder(root->left);       // left
        preorder(root->right);      // right
    }
}

 

예를 들면,

        A
       / \
      B   C
     / \   \
    D   E   F

 

단계	방문 노드	동작	그림
1	A	루트부터 시작
2	B	왼쪽 서브트리로 이동
3	D	B의 왼쪽 방문 (리프 노드)
4	E	B의 오른쪽 방문
5	C	루트 A의 오른쪽 이동
6	F	C의 오른쪽 방문

순서: A B D E C F

==  트리 구조를 복사하거나 저장할 때 자주 사용함.

 

 2) 중위 순회 (Inorder Traversal)

방문 순서: Left Subtree → Root → Right Subtree (L V R)

void inorder(TreeNode* root) {
    if (root != NULL) {
        inorder(root->left);
        printf("%d ", root->data);
        inorder(root->right);
    }
}

 

예를 들면,

        A
       / \
      B   C
     / \   \
    D   E   F

단계	방문 노드	동작	그림
1	D	왼쪽 끝까지 이동
2	B	D의 부모 방문
3	E	B의 오른쪽 자식 방문
4	A	루트 방문
5	C	루트 A의 오른쪽 이동
6	F	C의 오른쪽 방문

순서: D B E A C F

==  이진 탐색 트리(BST) 에서 중위 순회 결과는 오름차순 정렬이 됨.

 

 3) 후위 순회 (Postorder Traversal)

방문 순서: Left Subtree → Right Subtree → Root (L R V)

void postorder(TreeNode* root) {
    if (root != NULL) {
        postorder(root->left);
        postorder(root->right);
        printf("%d ", root->data);
    }
}

 

예를 들면,

        A
       / \
      B   C
     / \   \
    D   E   F

단계	방문 노드	동작	그림
1	D	왼쪽 끝까지 이동
2	E	B의 오른쪽 방문
3	B	B의 모든 자식 방문 후 B 방문
4	F	C의 오른쪽 방문
5	C	C의 모든 자식 방문 후 C 방문
6	A	전체 트리의 루트 마지막 방문

순서: D E B F C A

 

== 하위 노드를 먼저 처리하고 루트를 나중에 처리해야 할 때 사용함.
  트리 삭제, 수식 계산(Expression Tree) 등에 활용됨.

 4) Level-order Traversal (레벨 순회)

레벨(층) 단위로 탐색하는 순회 방식.
Queue를 이용해서 구현함.

void levelorder(TreeNode* root) {
    if (root == NULL) return;
    Queue q;
    enqueue(&q, root);
    while (!isEmpty(&q)) {
        TreeNode* n = dequeue(&q);
        printf("%d ", n->data);
        if (n->left) enqueue(&q, n->left);
        if (n->right) enqueue(&q, n->right);
    }
}

 

예를 들면,

        A
       / \
      B   C
     / \   \
    D   E   F

단계	방문 노드	동작
1	A	루트 (맨위)
2	B, C	2층 (왼쪽 → 오른쪽)
3	D, E, F	3층 (왼쪽 → 오른쪽)

순서: A B C D E F

==  트리의 층별 구조를 파악할 때 유용함.

---

2.  Copying Binary Trees (이진 트리 복사)

트리를 복사하려면 각 노드를 새로 생성하면서
왼쪽, 오른쪽 서브트리까지 재귀적으로 복사해야 함.

TreeNode* copy(TreeNode* root) {
    if (root == NULL) return NULL;
    TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
    newNode->data = root->data;
    newNode->left = copy(root->left);
    newNode->right = copy(root->right);
    return newNode;
}

•  구조와 데이터 모두 동일한 완전 복사(deep copy) 를 수행함.
• 전위 순회(preorder) 방식과 유사하게 구현됨.

---

3.  Testing Equality (트리 동등성 검사)

두 개의 이진 트리가 같은 구조와 같은 데이터를 가지고 있는지 비교함.

int equal(TreeNode* t1, TreeNode* t2) {
    if (t1 == NULL && t2 == NULL) return 1;
    if (t1 == NULL || t2 == NULL) return 0;
    return (t1->data == t2->data)
        && equal(t1->left, t2->left)
        && equal(t1->right, t2->right);
}

 

비교 로직:

1. 두 노드 모두 NULL → 같음
2. 하나만 NULL → 다름
3. 값 비교 후 왼쪽, 오른쪽 서브트리 재귀 비교

• 완전 동일한 구조인지 판단할 때 사용함.

---

4.  The Satisfiability Problem (만족 가능성 문제)

논리식(불 표현식, Boolean Expression)이 주어졌을 때
참이 되도록 변수에 값을 할당할 수 있는지 판별하는 문제.
즉, “이 논리식이 만족될 수 있는가?”를 묻는 문제임.

 

예:

(A ∨ B) ∧ (¬A ∨ C)

• A = False, B = True, C = True → 식은 참
• 따라서 satisfiable (만족 가능) 함.

 

트리로 표현하기

논리식을 트리 형태로 표현하면 논리 연산 트리 (Logical Expression Tree) 가 됨.

           ∧
         /    \
       ∨      ∨
      /  \    /  \
     A    B  ¬A   C

각 노드는 연산자(∧, ∨, ¬) 또는 피연산자(A, B, C)임.
이 트리를 후위 순회(postorder) 하면서 값을 계산하면 논리식의 결과를 얻을 수 있음.

== 논리식 판별, 디지털 회로 시뮬레이션, AI 규칙 시스템 등에서 사용됨.