ในบทช่วยสอนนี้ เราจะเรียนรู้วิธีลบโหนดปลายสุดจากทรีด้วยค่าที่กำหนด
มาดูขั้นตอนการแก้ปัญหากัน
-
เขียน struct Node สำหรับไบนารีทรี
-
เขียนฟังก์ชันเพื่อสำรวจ (inorder, preorder, postorder) ผ่านแผนผังและพิมพ์ข้อมูลทั้งหมด
-
เริ่มต้นต้นไม้ด้วยการสร้างโหนดด้วยโครงสร้าง
-
เริ่มต้นค่า x
-
เขียนฟังก์ชันเพื่อลบโหนดปลายสุดด้วยค่าที่กำหนด ยอมรับโหนดรากสองอาร์กิวเมนต์และค่า k
-
หากรูทเป็นค่า null return
-
แทนที่โหนดด้านซ้ายของรูทด้วยรูทใหม่หลังจากการลบ
-
เช่นเดียวกับโหนดด้านขวาของรูท
-
หากข้อมูลโหนดรูทปัจจุบันเท่ากับ k และเป็นโหนดปลายสุด ให้ส่งคืนตัวชี้ค่าว่าง
-
ส่งคืนโหนดรูท
-
ตัวอย่าง
มาดูโค้ดกันเลย
#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);
// checking the current node data with k
if (root->data == k && root->left == NULL && root->right == NULL) {
// deleting the node
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
บทสรุป
หากคุณมีข้อสงสัยใดๆ ในบทแนะนำ โปรดระบุในส่วนความคิดเห็น
