이번 글에서 다룰 문제는 이진 트리의 리프 노드를 왼쪽에서 오른쪽 순서대로 출력하는 것입니다. 여기서 핵심 과제는 오직 하나의 스택만 사용해야 한다는 제약 조건입니다.
push() 함수를 통해 이진 트리의 노드들을 스택에 삽입하고, pop() 연산을 통해 리프 노드를 화면에 출력합니다.
리프 노드란 왼쪽과 오른쪽 포인터가 모두 NULL인 말단 노드를 의미합니다. 즉, 해당 노드는 자식 노드를 가지지 않는, 부모 노드가 아닌 노드입니다.
예시
입력 : 12 21 32 41 59 33 70 출력 : 41 59 33 70
스택(stack)은 LIFO(Last In, First Out, 후입선출) 방식으로 동작하는 자료구조로, top 포인터는 가장 마지막에 삽입된 요소를 가리킵니다. 이러한 구조적 특성 때문에 스택에 나중에 들어간 노드일수록 다른 노드보다 먼저 꺼내지게 되며, 이 원리를 활용하면 추가 자료구조 없이 리프 노드를 순서대로 출력할 수 있습니다.
아래 코드는 설명한 알고리즘을 C++ STL을 사용해 구현한 예제입니다.
알고리즘
시작
1단계 -> 구조체 타입의 노드 변수 생성
int형 data 선언
node 타입의 포인터 *left, *right 선언
2단계 -> val을 매개변수로 받는 노드 생성 함수 작성
new(malloc)으로 node 변수 할당
node->data = val 설정
node->left = node->right = NULL 설정
node 반환
3단계 -> void leaf(Node *ptr) 함수 선언
stack<Node*> stck 생성
While 1 (무한 반복)
IF ptr이 NULL이 아니면
stck.push(ptr)
ptr = ptr->left
ELSE
IF 스택이 비어 있으면(stck.empty())
Break
ELSE
IF stck.top()->right == NULL이면
ptr = stck.top()
stck.pop()
IF ptr->left == NULL이면
ptr->data 출력 // 리프 노드
END
END
WHILE ptr == stck.top()->right인 동안 반복
ptr = stck.top()
stck.pop()
IF 스택이 비어 있으면
Break
END
END
IF !stck.empty()이면
ptr = stck.top()->right
ELSE
ptr = NULL
ENDIF
END
END
4단계 -> main() 함수에서
삽입할 값을 인자로 New 호출 (예: Node* root = New(12))
leaf(root) 호출
종료
C++ 구현 코드
#include <bits/stdc++.h>
using namespace std;
// 노드 구조체 정의
struct Node {
Node* left;
Node* right;
int data;
};
// 새 노드를 생성하는 함수
Node* New(int val) {
Node* node = new Node();
node->left = node->right = NULL;
node->data = val;
return node;
}
// 스택을 이용해 리프 노드 출력
void leaf(Node* ptr) {
// 노드를 저장할 스택
stack<Node*> stck;
while (1) {
if (ptr) {
stck.push(ptr);
ptr = ptr->left;
} else {
if (stck.empty())
break;
else {
if (stck.top()->right == NULL) {
ptr = stck.top();
stck.pop();
// 리프 노드 출력
if (ptr->left == NULL)
printf("%d ", ptr->data);
}
while (ptr == stck.top()->right) {
ptr = stck.top();
stck.pop();
if (stck.empty())
break;
}
if (!stck.empty())
ptr = stck.top()->right;
else
ptr = NULL;
}
}
}
}
int main() {
printf("leaf nodes at end level are : ");
Node* root = New(12);
root->left = New(21);
root->right = New(32);
root->left->left = New(41);
root->left->right = New(59);
root->right->left = New(33);
root->right->right = New(70);
leaf(root);
return 0;
}
출력 결과
위 프로그램을 실행하면 다음과 같은 결과가 출력됩니다.
leaf nodes at end level are : 41 59 33 70
작동 원리 요약
이 알고리즘은 반복문 기반의 중위 순회(inorder traversal)와 유사한 방식으로 동작합니다.
- 현재 노드가 존재하면 스택에 push하고 왼쪽 자식으로 이동합니다.
- 현재 노드가 NULL이 되면 스택의 top을 살펴봅니다.
- top 노드의 오른쪽 자식이 없다면 해당 노드를 pop하고, 왼쪽 자식까지 없다면 리프 노드이므로 값을 출력합니다.
- 방금 꺼낸 노드가 부모 노드의 오른쪽 자식이라면 오른쪽 서브트리 처리가 끝난 것이므로 부모 노드도 연속해서 pop합니다.
- 스택이 비어 있지 않다면 top 노드의 오른쪽 자식으로 이동해 같은 과정을 반복하고, 스택이 비면 종료합니다.