이 문제에서는 N-ary(다진) 트리가 주어지며, 우리의 목표는 이 트리의 전위 순회(preorder traversal) 결과를 출력하는 것입니다. 재귀 호출 없이 스택(stack) 자료구조만을 사용해 해결하는 방법을 단계별로 알아보겠습니다.
기본 개념 정리
N-ary 트리(N-ary Tree)
N-ary 트리는 모든 노드가 최대 N개의 자식 노드를 가질 수 있는 트리입니다. 예를 들어 2-ary 트리(이진 트리)는 각 노드가 최대 2개의 자식 노드를 가질 수 있습니다.
전위 순회(Preorder Traversal)
전위 순회는 트리의 노드를 방문하는 방식 중 하나로, 루트 노드 → 왼쪽 자식 → 오른쪽 자식 순서로 노드를 방문합니다.
문제 예시
다음과 같은 트리가 주어졌을 때 전위 순회 결과는 아래와 같습니다.
전위 순회 결과 :
12 15 14 25 99 4 11 7 19
접근 방법
재귀 함수 대신 스택을 활용하면 다음과 같은 단계로 문제를 해결할 수 있습니다.
- 루트 노드를 스택에 push 합니다.
- 스택에서 노드를 pop 하여 해당 노드의 값을 출력합니다.
- pop 한 노드의 자식들을 오른쪽 자식부터 왼쪽 자식 순서로(역순으로) 스택에 push 합니다. 역순으로 넣어야 다음에 pop 될 때 왼쪽 자식이 먼저 처리됩니다.
- 스택이 빌 때까지 2~3단계를 반복합니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
struct Node {
int key;
vector<Node*> child;
};
Node* insertNode(int key){
Node* temp = new Node;
temp->key = key;
return temp;
}
void preOrderTraversal(struct Node* root){
stack<Node*> tree;
tree.push(root);
while (!tree.empty()) {
Node* curr = tree.top();
tree.pop();
cout << curr->key << "\t";
// 자식 노드를 역순(오른쪽 → 왼쪽)으로 스택에 삽입
vector<Node*>::iterator it = curr->child.end();
while (it != curr->child.begin()) {
it--;
tree.push(*it);
}
}
}
int main(){
Node* root = insertNode(12);
(root->child).push_back(insertNode(15));
(root->child).push_back(insertNode(99));
(root->child).push_back(insertNode(4));
(root->child).push_back(insertNode(7));
(root->child[0]->child).push_back(insertNode(14));
(root->child[0]->child).push_back(insertNode(25));
(root->child[2]->child).push_back(insertNode(11));
(root->child[3]->child).push_back(insertNode(19));
cout << "트리의 전위 순회 결과 :\n";
preOrderTraversal(root);
return 0;
}
실행 결과
트리의 전위 순회 결과 :
12 15 14 25 99 4 11 7 19
복잡도 분석
- 시간 복잡도: O(n) — 각 노드를 정확히 한 번씩 방문하고, 각 자식 노드도 한 번씩만 스택에 push/pop 되기 때문입니다.
- 공간 복잡도: O(n) — 최악의 경우(한쪽으로 치우친 트리) 스택에 트리의 거의 모든 노드가 저장될 수 있습니다.
이처럼 스택을 활용하면 재귀 호출 없이도 N-ary 트리의 전위 순회를 간결하고 효율적으로 구현할 수 있습니다. 재귀 깊이 제한으로 인해 스택 오버플로가 발생할 수 있는 매우 깊은 트리를 다룰 때 특히 유용한 기법입니다.