개요
이 튜토리얼에서는 이진 트리에서 주어진 값과 일치하는 리프(leaf) 노드를 삭제하는 방법을 배워보겠습니다.
재귀 호출을 활용하면 간단하고 직관적으로 문제를 해결할 수 있습니다. 핵심 아이디어는 트리를 순회하면서 자식 노드부터 처리한 뒤, 현재 노드가 값 k를 가지는 리프 노드인지 확인하는 것입니다.
문제 해결 단계
이진 트리를 나타내는 Node 구조체를 작성합니다.
트리를 순회(inorder, preorder, postorder)하며 모든 데이터를 출력하는 함수를 작성합니다.
구조체를 이용해 노드를 생성하고 트리를 초기화합니다.
삭제할 대상 값 x(k)를 초기화합니다.
주어진 값에 해당하는 리프 노드를 삭제하는 함수를 작성합니다. 이 함수는 루트 노드와 k 값, 두 개의 인자를 받습니다.
루트가 NULL이면 그대로 반환합니다.
루트의 왼쪽 자식 노드를 삭제 처리한 결과로 교체합니다.
루트의 오른쪽 자식 노드도 동일하게 처리합니다.
현재 루트 노드의 데이터가 k와 같고, 왼쪽·오른쪽 자식이 모두 없는 리프 노드라면 NULL 포인터를 반환하여 해당 노드를 제거합니다.
그 외의 경우에는 루트 노드를 그대로 반환합니다.
예제 코드
위 로직을 실제로 구현한 C++ 코드입니다.
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node *left, *right;
};
struct Node* newNode(int data) {
struct Node* newNode = new Node;
newNode->data = data;
newNode->left = newNode->right = NULL;
return newNode;
}
Node* deleteLeafNodes(Node* root, int k) {
if (root == NULL) {
return nullptr;
}
root->left = deleteLeafNodes(root->left, k);
root->right = deleteLeafNodes(root->right, k);
// 현재 노드의 데이터와 k 비교
if (root->data == k && root->left == NULL && root->right == NULL) {
// 해당 노드 삭제
return nullptr;
}
return root;
}
void inorder(Node* root) {
if (root == NULL) {
return;
}
inorder(root->left);
cout << root->data << " ";
inorder(root->right);
}
int main(void) {
struct Node* root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(3);
root->left->right = newNode(4);
root->right->right = newNode(5);
root->right->left = newNode(4);
root->right->right->left = newNode(4);
root->right->right->right = newNode(4);
deleteLeafNodes(root, 4);
cout << "Tree: ";
inorder(root);
cout << endl;
return 0;
}실행 결과
위 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다.
Tree: 3 2 1 3 5
동작 원리 정리
이 알고리즘은 후위 순회(postorder) 방식으로 동작합니다. 즉, 왼쪽 서브트리와 오른쪽 서브트리를 먼저 처리한 후에 현재 노드를 검사하기 때문에, 자식 노드가 삭제되어 새롭게 리프 노드가 된 경우에도 올바르게 감지할 수 있다는 장점이 있습니다. 시간 복잡도는 트리의 모든 노드를 한 번씩 방문하므로 O(n)입니다.
결론
이번 튜토리얼에서는 재귀 함수를 사용하여 이진 트리에서 특정 값 k를 가지는 리프 노드를 삭제하는 방법을 살펴보았습니다. 궁금한 점이 있다면 댓글로 남겨주세요!