C++로 트리의 모든 노드에 중위 순회 후속자(Inorder Successor) 채우기

문제 개요

이 문제에서는 next 포인터를 포함하는 트리 구조가 주어집니다. 우리의 과제는 각 노드의 next 포인터를 해당 노드의 중위 순회 후속자(inorder successor)로 채우는 것입니다.

struct node {
    int value;
    struct node* left;
    struct node* right;
    struct node* next;
}

모든 next 포인터는 처음에 NULL로 초기화되어 있으며, 이를 각 노드의 중위 순회 후속자를 가리키도록 설정해야 합니다.

중위 순회(Inorder Traversal)란?

중위 순회는 다음과 같은 순서로 트리를 탐색하는 방식입니다.

왼쪽 노드 -> 루트 노드 -> 오른쪽 노드

중위 순회 후속자(Inorder Successor)란 중위 순회 과정에서 현재 노드 바로 뒤에 등장하는 노드를 의미합니다.

예제로 이해하기

예시를 통해 문제를 자세히 살펴보겠습니다.

위 트리의 중위 순회 결과는 7 8 3 5 9 1 입니다.

각 노드의 next 포인터를 채우면 다음과 같습니다.

5의 next는 9
8의 next는 3
7의 next는 8
3의 next는 5
9의 next는 1

해결 접근 방법

이 문제를 해결하려면 트리를 역방향 중위 순회(reverse inorder) 방식으로 탐색해야 합니다. 즉, 오른쪽 서브트리부터 먼저 방문하고, 직전에 방문했던 노드를 현재 노드의 next 포인터에 저장하는 것입니다. 이렇게 하면 각 노드가 자신의 중위 후속자를 정확하게 가리키게 됩니다.

구현 예제

다음은 위에서 설명한 해결 방법을 구현한 C++ 프로그램입니다.

#include<iostream>
using namespace std;
struct node {
    int data;
    node *left;
    node *right;
    node *next;
};
node* insertNode(int data){
    node* Node = new node();
    Node->data = data;
    Node->left = NULL;
    Node->right = NULL;
    Node->next = NULL;
    return(Node);
}
void populateTree(node* pop){
    static node *next = NULL;
    if (pop){
        populateTree(pop->right);
        pop->next = next;
        next = pop;
        populateTree(pop->left);
    }
}
void printNext(node * root) {
    node *ptr = root->left->left;
    while(ptr){
        cout<<"Next of "<<ptr->data<<" is ";
        cout<<(ptr->next? ptr->next->data: -1)<<endl;
        ptr = ptr->next;
    }
}
int main() {
    node *root = insertNode(15);
    root->left = insertNode(99);
    root->right = insertNode(1);
    root->left->left = insertNode(76);
    root->left->right = insertNode(31);
    cout<<"Populating the Tree by adding inorder successor to the next\n";
    populateTree(root);
    printNext(root);
    return 0;
}

실행 결과

Populating the Tree by adding inorder successor to the next

Next of 76 is 99
Next of 99 is 31
Next of 31 is 15
Next of 15 is 1
Next of 1 is -1

코드 동작 원리

populateTree 함수는 역방향 중위 순회를 수행합니다. 먼저 오른쪽 서브트리를 재귀적으로 탐색한 뒤, 현재 노드의 next에 정적 변수 next에 저장된 이전 방문 노드를 할당합니다. 그리고 현재 노드를 새로운 '직전 방문 노드'로 갱신한 후 왼쪽 서브트리를 탐색합니다. 이 과정을 반복하면 모든 노드의 next 포인터가 자신의 중위 후속자를 가리키게 되며, 중위 순회상 마지막 노드의 next는 NULL(-1)로 남게 됩니다.