Trong hướng dẫn này, chúng ta sẽ tìm hiểu cách xóa một nút trong cây nhị phân.
Các nút trong cây nhị phân không tuân theo bất kỳ thứ tự nào như cây tìm kiếm nhị phân. Vậy, làm thế nào để sắp xếp các nút sau khi xóa một nút trong cây nhị phân?
Chúng ta sẽ thay thế nút sâu nhất của cây bằng nút xóa. Và sau đó chúng tôi sẽ xóa nút sâu nhất khỏi nút.
Hãy xem các bước để giải quyết vấn đề.
-
Khởi tạo cây với cấu trúc nút nhị phân.
-
Viết một hàm (đặt hàng trước, theo thứ tự và đặt hàng sau) để in các nút của cây.
-
Viết một hàm để xóa nút.
-
Khởi tạo hàng đợi để lặp qua cây.
-
Lặp lại cho đến khi hàng đợi trống.
-
Tìm nút có khóa đã cho và lưu trữ nó trong một biến.
-
Và nút cuối cùng từ hàng đợi là nút sâu nhất.
-
-
Xóa nút sâu nhất bằng một chức năng khác.
-
Sử dụng hàng đợi để đi qua cây.
-
Khi chúng tôi tìm thấy nút, hãy xóa nó và trả lại.
-
-
In cây để xem liệu nút có bị xóa hay không.
Ví dụ
Hãy xem mã.
#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;
} Đầu ra
Nếu bạn chạy đoạn mã trên, thì bạn sẽ nhận được kết quả sau.
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
Kết luận
Nếu bạn có bất kỳ câu hỏi nào trong hướng dẫn, hãy đề cập đến chúng trong phần bình luận.