트리 순회(Tree Traversal)는 그래프 순회의 한 형태로, 트리에 속한 모든 노드를 정확히 한 번씩 방문하거나 출력하는 과정을 말합니다. 그중에서도 이진 탐색 트리(Binary Search Tree)의 후위 순회(Postorder Traversal)는 왼쪽 → 오른쪽 → 루트 순서로 각 노드를 방문하는 방식입니다.
후위 순회의 동작 방식
후위 순회에서는 먼저 왼쪽 서브트리 전체를 방문한 후, 오른쪽 서브트리를 방문하고, 마지막으로 루트 노드를 방문합니다. 예를 들어 아래와 같은 이진 트리가 주어졌다고 가정해 보겠습니다.
이 트리의 후위 순회 결과는 다음과 같습니다.
1 5 4 8 6
C++ 후위 순회 프로그램
다음은 이진 탐색 트리를 후위 순회하는 재귀 프로그램의 전체 코드입니다.
예제
#include<iostream>
using namespace std;
struct node {
int data;
struct node *left;
struct node *right;
};
struct node *createNode(int val) {
struct node *temp = (struct node *)malloc(sizeof(struct node));
temp->data = val;
temp->left = temp->right = NULL;
return temp;
}
void postorder(struct node *root) {
if (root != NULL) {
postorder(root->left);
postorder(root->right);
cout<<root->data<<" ";
}
}
struct node* insertNode(struct node* node, int val) {
if (node == NULL) return createNode(val);
if (val < node->data)
node->left = insertNode(node->left, val);
else if (val > node->data)
node->right = insertNode(node->right, val);
return node;
}
int main() {
struct node *root = NULL;
root = insertNode(root, 4);
insertNode(root, 5);
insertNode(root, 2);
insertNode(root, 9);
insertNode(root, 1);
insertNode(root, 3);
cout<<"Post-Order traversal of the Binary Search Tree is: ";
postorder(root);
return 0;
}출력 결과
Post-Order traversal of the Binary Search Tree is: 1 3 2 9 5 4
코드 상세 설명
1. node 구조체 정의
위 프로그램에서 구조체 node는 트리의 노드를 생성하는 역할을 합니다. 이 구조체는 자기 자신과 같은 타입인 struct node 포인터를 멤버로 포함하고 있으므로, 자기 참조 구조체(self-referential structure)라고 부릅니다.
struct node {
int data;
struct node *left;
struct node *right;
};2. createNode() 함수
createNode() 함수는 새로운 노드 temp를 만들고 malloc을 사용해 메모리를 할당합니다. 매개변수로 전달받은 값 val은 temp의 data 멤버에 저장되며, left와 right 포인터에는 NULL이 저장됩니다.
struct node *createNode(int val) {
struct node *temp = (struct node *)malloc(sizeof(struct node));
temp->data = val;
temp->left = temp->right = NULL;
return temp;
}3. postorder() 함수
postorder() 함수는 이진 트리의 루트 노드를 인자로 받아 트리의 모든 요소를 후위 순회 순서대로 출력하는 재귀 함수입니다. 왼쪽 서브트리와 오른쪽 서브트리를 먼저 순회한 뒤, 마지막에 현재 노드의 데이터를 출력합니다.
void postorder(struct node *root) {
if (root != NULL) {
postorder(root->left);
postorder(root->right);
cout<<root->data<<" ";
}
}4. insertNode() 함수
insertNode() 함수는 새로운 값을 이진 탐색 트리의 올바른 위치에 삽입합니다. 현재 노드가 NULL이라면 createNode()를 호출해 새 노드를 생성하고, 그렇지 않으면 삽입할 값과 노드의 데이터 값을 비교하며 적절한 위치를 찾아 내려갑니다.
struct node* insertNode(struct node* node, int val) {
if (node == NULL) return createNode(val);
if (val < node->data)
node->left = insertNode(node->left, val);
else if (val > node->data)
node->right = insertNode(node->right, val);
return node;
}5. main() 함수
main() 함수에서는 먼저 루트 노드를 NULL로 초기화한 뒤, 값이 담긴 여러 노드를 이진 탐색 트리에 차례대로 삽입합니다.
struct node *root = NULL; root = insertNode(root, 4); insertNode(root, 5); insertNode(root, 2); insertNode(root, 9); insertNode(root, 1); insertNode(root, 3);
마지막으로 트리의 루트 노드를 인자로 postorder() 함수를 호출하면, 트리의 모든 값이 후위 순회 순서대로 화면에 출력됩니다.
cout<<"Post-Order traversal of the Binary Search Tree is: "; postorder(root);