이 튜토리얼에서는 바이너리 트리에서 노드를 삭제하는 방법을 배울 것입니다.
이진 트리의 노드는 이진 탐색 트리와 같은 순서를 따르지 않습니다. 그렇다면 이진 트리에서 노드를 삭제한 후 노드를 정렬하는 방법은 무엇입니까?
글쎄, 우리는 트리의 가장 깊은 노드를 삭제 노드로 바꿀 것입니다. 그런 다음 노드에서 가장 깊은 노드를 삭제합니다.
문제를 해결하는 단계를 살펴보겠습니다.
-
바이너리 노드 구조체로 트리를 초기화합니다.
-
트리의 노드를 출력하는 함수(preorder, in order, postorder)를 작성하세요.
-
노드를 삭제하는 함수를 작성하십시오.
-
트리를 반복하도록 대기열을 초기화합니다.
-
대기열이 비어 있을 때까지 반복합니다.
-
주어진 키가 있는 노드를 찾아 변수에 저장합니다.
-
그리고 큐의 마지막 노드가 가장 깊은 노드입니다.
-
-
다른 함수를 사용하여 가장 깊은 노드를 삭제합니다.
-
큐를 사용하여 트리를 통과합니다.
-
노드를 찾으면 삭제하고 반환합니다.
-
-
노드가 삭제되었는지 확인하려면 트리를 인쇄하십시오.
예시
코드를 봅시다.
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node *left, *right;
};
struct Node* newNode(int data) {
struct Node* temp = new Node;
temp->data = data;
temp->left = temp->right = NULL;
return temp;
};
void inorder(struct Node* node) {
if (node == NULL) {
return;
}
inorder(node->left);
cout << node->data << " ";
inorder(node->right);
}
void deleteDeepestNode(struct Node* root, struct Node* deleting_node){
queue<struct Node*> nodes;
nodes.push(root);
struct Node* temp;
while (!nodes.empty()) {
temp = nodes.front();
nodes.pop();
if (temp == deleting_node) {
temp = NULL;
delete (deleting_node);
return;
}
if (temp->right) {
if (temp->right == deleting_node) {
temp->right = NULL;
delete deleting_node;
return;
}
else {
nodes.push(temp->right);
}
}
if (temp->left) {
if (temp->left == deleting_node) {
temp->left = NULL;
delete deleting_node;
return;
}
else {
nodes.push(temp->left);
}
}
}
}
Node* deleteNode(struct Node* root, int key) {
if (root == NULL){
return NULL;
}
if (root->left == NULL && root->right == NULL) {
if (root->data == key) {
return NULL;
}
else {
return root;
}
}
queue<struct Node*> nodes;
nodes.push(root);
struct Node* temp;
struct Node* key_node = NULL;
while (!nodes.empty()) {
temp = nodes.front();
nodes.pop();
if (temp->data == key) {
key_node = temp;
}
if (temp->left) {
nodes.push(temp->left);
}
if (temp->right) {
nodes.push(temp->right);
}
}
if (key_node != NULL) {
int deepest_node_data = temp->data;
deleteDeepestNode(root, temp);
key_node->data = deepest_node_data;
}
return root;
}
int main() {
struct Node* root = newNode(1);
root->left = newNode(2);
root->left->left = newNode(3);
root->left->right = newNode(4);
root->right = newNode(5);
root->right->left = newNode(6);
root->right->right = newNode(7);
root->right->left->left = newNode(8);
root->right->left->right = newNode(9);
cout << "Tree before deleting key: ";
inorder(root);
int key = 5;
root = deleteNode(root, key);
cout << "\nTree after deleting key: ";
inorder(root);
cout << endl;
return 0;
} 출력
위의 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다.
Tree before deleting key: 3 2 4 1 8 6 9 5 7 Tree after deleting key: 3 2 4 1 8 6 9 7
결론
튜토리얼에서 질문이 있는 경우 댓글 섹션에 언급하세요.