Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 재귀 없이 이진 트리의 루트–리프 경로 출력하기

이 글에서는 주어진 이진 트리에서 루트 노드부터 모든 리프 노드까지의 경로를 재귀 호출 없이 출력하는 C++ 프로그램을 소개합니다.

문제 이해하기

예를 들어 다음과 같은 이진 트리가 있다고 가정해 보겠습니다.

C++로 재귀 없이 이진 트리의 루트–리프 경로 출력하기

이 이진 트리에는 4개의 리프 노드가 있습니다. 따라서 루트 노드에서 리프 노드까지 총 4개의 경로가 존재합니다. 일반적으로 이진 트리에서 루트–리프 경로의 개수는 리프 노드의 개수와 같습니다.

접근 방식: 반복적 전위 순회 + 부모 포인터

재귀 대신 반복(iterative) 방식으로 문제를 해결합니다. 핵심 아이디어는 다음과 같습니다.

  • 스택을 이용해 이진 트리를 전위 순회(preorder traversal)합니다.
  • 순회하면서 각 노드의 부모 포인터를 맵(map)에 저장합니다.
  • 순회 중 왼쪽·오른쪽 자식이 모두 없는 리프 노드를 만나면, 부모 포인터를 따라 루트까지 거슬러 올라가 경로를 출력합니다.

알고리즘 단계

  1. 루트를 스택에 push하고, 부모 맵에서 루트의 부모를 NULL로 설정합니다.
  2. 스택이 빌 때까지 다음 과정을 반복합니다.
    • 스택에서 노드를 pop합니다.
    • 해당 노드가 리프 노드라면 부모 맵을 이용해 루트 → 리프 경로를 출력합니다.
    • 오른쪽 자식이 있으면 부모 정보를 저장한 뒤 스택에 push합니다.
    • 왼쪽 자식이 있으면 부모 정보를 저장한 뒤 스택에 push합니다. (오른쪽을 먼저 넣으므로 왼쪽이 먼저 처리되어 전위 순회 순서가 유지됩니다.)

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int data;
    struct Node *left, *right;
};

// 새 노드 생성
Node* create_node(int data) {
    Node* node = new Node;
    node->data = data;
    node->left = node->right = NULL;
    return node;
}

// 루트에서 리프까지 경로 출력
void print_cpath(Node* curr, map<Node*, Node*> parent) {
    stack<Node*> nodes_stack;
    while (curr) {
        nodes_stack.push(curr);
        curr = parent[curr];
    }
    while (!nodes_stack.empty()) {
        curr = nodes_stack.top();
        nodes_stack.pop();
        cout << curr->data << " ";
    }
    cout << endl;
}

// 전위 순회 수행
void preorder_traversal(Node* root) {
    if (root == NULL)
        return;
    stack<Node*> nodeStack;
    nodeStack.push(root);
    map<Node*, Node*> parent;
    parent[root] = NULL;
    while (!nodeStack.empty()) {
        Node* current = nodeStack.top();
        nodeStack.pop();
        // 리프 노드를 만나면 경로 출력
        if (!(current->left) && !(current->right))
            print_cpath(current, parent);
        if (current->right) {
            parent[current->right] = current;
            nodeStack.push(current->right);
        }
        if (current->left) {
            parent[current->left] = current;
            nodeStack.push(current->left);
        }
    }
}

int main() {
    Node* root = create_node(101);
    root->left = create_node(82);
    root->right = create_node(23);
    root->left->left = create_node(34);
    root->left->right = create_node(55);
    root->right->left = create_node(29);
    preorder_traversal(root);
    return 0;
}

실행 결과

101 82 34
101 82 55
101 23 29

복잡도 분석

  • 시간 복잡도: O(n log n) — 각 노드마다 맵(map) 연산이 O(log n)의 비용을 가지므로
  • 공간 복잡도: O(n) — 스택과 부모 맵에 최대 n개의 노드 정보가 저장되므로

참고: std::map 대신 std::unordered_map을 사용하면 평균적으로 시간 복잡도를 O(n)까지 개선할 수 있습니다.