Computer >> คอมพิวเตอร์ >  >> การเขียนโปรแกรม >> C++

ลบโหนดปลายสุดที่มีค่าเป็น x ใน C++ Program


ในบทช่วยสอนนี้ เราจะเรียนรู้วิธีลบโหนดปลายสุดจากทรีด้วยค่าที่กำหนด

มาดูขั้นตอนการแก้ปัญหากัน

  • เขียน struct Node สำหรับไบนารีทรี

  • เขียนฟังก์ชันเพื่อสำรวจ (inorder, preorder, postorder) ผ่านแผนผังและพิมพ์ข้อมูลทั้งหมด

  • เริ่มต้นต้นไม้ด้วยการสร้างโหนดด้วยโครงสร้าง

  • เริ่มต้นค่า x

  • เขียนฟังก์ชันเพื่อลบโหนดปลายสุดด้วยค่าที่กำหนด ยอมรับโหนดรากสองอาร์กิวเมนต์และค่า x

    • หากรูทเป็นค่า null return

    • แทนที่โหนดด้านซ้ายของรูทด้วยรูทใหม่หลังจากการลบ

    • เช่นเดียวกับโหนดด้านขวาของรูท

    • หากข้อมูลโหนดรูทปัจจุบันเท่ากับ x และเป็นโหนดปลายสุด ให้ส่งคืนตัวชี้ค่าว่าง

    • ส่งคืนโหนดรูท

ตัวอย่าง

มาดูโค้ดกันเลย

#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 x) {
   if (root == NULL) {
      return nullptr;
   }
   root->left = deleteLeafNodes(root->left, x);
   root->right = deleteLeafNodes(root->right, x);
   // checking the current node data with x
   if (root->data == x && 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

บทสรุป

หากคุณมีข้อสงสัยใดๆ ในบทแนะนำ โปรดระบุในส่วนความคิดเห็น