트리(tree)를 삭제하려면 트리에 포함된 모든 노드를 순회하면서 각 노드를 하나씩 제거해야 합니다. 이 과정을 거치면 트리의 노드가 차례대로 해제되고 트리는 완전히 비게 됩니다.
여기서 중요한 점은 자식 노드를 반드시 부모 노드보다 먼저 삭제해야 한다는 것입니다. 부모를 먼저 해제하면 자식 노드의 주소를 잃어버려 메모리 누수(memory leak)가 발생할 수 있기 때문입니다. 따라서 트리를 아래에서 위로(bottom-up) 순회하는 방식이 필요하며, 이러한 조건에 가장 잘 맞는 것이 바로 후위 순회(postorder traversal)입니다. 후위 순회를 사용하면 불필요한 복잡성 없이 효율적으로 트리 전체를 삭제할 수 있어 프로그램의 최적화에도 유리합니다.
후위 순회(Postorder Traversal)란?
후위 순회는 다음과 같은 순서로 트리를 탐색하는 기법입니다.
왼쪽 자식 노드 → 오른쪽 자식 노드 → 루트 노드
즉, 가장 아래 레벨의 자식 노드부터 먼저 방문하고 마지막에 루트 노드를 방문하기 때문에, 트리 삭제 작업에 가장 적합한 순회 방식입니다.
예를 들어 다음과 같은 이진 트리가 있을 때,
9
/ \
4 15
/ \ / \
2 6 12 17후위 순회 결과는 다음과 같습니다.
2 - 6 - 4 - 12 - 17 - 15 - 9
C 언어 구현 예제
아래는 후위 순회를 재귀적으로 활용하여 이진 트리 전체를 삭제하는 C 프로그램입니다.
#include<stdio.h>
#include<stdlib.h>
struct node {
int data;
struct node* left;
struct node* right;
};
struct node* addnode(int data) {
struct node* node = (struct node*)
malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;
return(node);
}
void nodedel(struct node* node) {
if (node == NULL) return;
nodedel(node->left);
nodedel(node->right);
printf("\n Node deleted, value is %d", node->data);
free(node);
}
int main() {
struct node *root = addnode(9);
root->left = addnode(4);
root->right = addnode(15);
root->left->left = addnode(2);
root->left->right = addnode(6);
root->right->left = addnode(12);
root->right->right = addnode(17);
nodedel(root);
root = NULL;
printf("\n Tree deleted ");
return 0;
}코드 설명
nodedel() 함수는 재귀 호출을 통해 먼저 왼쪽 서브트리를 삭제하고, 그다음 오른쪽 서브트리를 삭제한 뒤, 마지막으로 현재 노드를 free()로 해제합니다. 이것이 바로 후위 순회 방식입니다. 모든 노드가 삭제된 후에는 루트 포인터를 NULL로 설정하여 댕글링 포인터(dangling pointer) 문제를 예방합니다.
실행 결과
Node deleted, value is 2 Node deleted, value is 6 Node deleted, value is 4 Node deleted, value is 12 Node deleted, value is 17 Node deleted, value is 15 Node deleted, value is 9 Tree deleted
실행 결과를 보면 가장 깊은 곳에 있는 리프 노드(2, 6, 12, 17)부터 삭제되고, 부모 노드(4, 15)와 루트 노드(9)가 마지막에 삭제되는 것을 확인할 수 있습니다. 이처럼 후위 순회를 활용하면 트리의 모든 노드를 안전하고 효율적으로 메모리에서 해제할 수 있습니다.