ลบโหนดปลายสุดที่มีค่า k ใน C ++ หรือไม่

ให้เรากำหนดโครงสร้างที่จะเป็นตัวแทนของโหนดต้นไม้ที่มีข้อมูลและโหนดลูกของโหนดซ้ายและขวา หากนี่เป็นโหนดแรกที่สร้างขึ้น แสดงว่าเป็นโหนดรูท มิฉะนั้นจะเป็นโหนดย่อย

struct Node {
   int data;
   struct Node *leftChild, *rightChild;
};

ต่อไป เราสร้างฟังก์ชัน newNode(int data) ที่ใช้ค่า int และกำหนดให้กับสมาชิกข้อมูลของโหนด ฟังก์ชันจะส่งกลับตัวชี้ไปยังโหนดโครงสร้างที่สร้างขึ้น นอกจากนี้ ลูกซ้ายและขวาของโหนดที่สร้างขึ้นใหม่จะถูกตั้งค่าเป็นโมฆะ

struct Node* newNode(int data) {
   struct Node* newNode = new Node;
   newNode->data = data;
   newNode->leftChild = newNode->rightChild = NULL;
   return (newNode);
}

ตอนนี้ เราสร้างฟังก์ชัน deleteNode(Node* root, int k) ซึ่งรับโหนดรูทและค่าข้อมูลของโหนดที่จะลบ หากโหนดที่กำหนดเป็นโหนดหลัก ก็จะลบโหนดย่อยด้านซ้ายและขวาออกด้วย ฟังก์ชันส่งคืนโหนดรูทที่แก้ไขหลังจากลบโหนดที่กำหนด

Node* deleteLeafNode(Node* root, int k) {
   if (root == NULL)
      return nullptr;
   root->leftChild = deleteLeafNode(root->leftChild, k);
   root->rightChild = deleteLeafNode(root->rightChild, k);
   if (root->data == k && root->leftChild == NULL &&
      root->rightChild == NULL)
      return nullptr;
   return root;
}

สุดท้ายสำหรับการจ่ายต้นไม้หลังจากการลบ เรามีฟังก์ชัน inorder(Node* root) ซึ่งลัดเลาะต้นไม้ในฟังก์ชัน inorder

void inorder(Node* root){
   if (root != NULL){
      inorder(root->leftChild);
      inorder(root->rightChild);
      cout << root->data << " ";
   }
}

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้ของการลบโหนดปลายสุดที่มีค่า k.

#include <iostream>
using namespace std;
struct Node {
   int data;
   struct Node *leftChild, *rightChild;
};
struct Node* newNode(int data){
   struct Node* newNode = new Node;
   newNode->data = data;
   newNode->leftChild = newNode->rightChild = NULL;
   return (newNode);
}
Node* deleteLeafNode(Node* root, int k){
   if (root == NULL)
      return nullptr;
   root->leftChild = deleteLeafNode(root->leftChild, k);
   root->rightChild = deleteLeafNode(root->rightChild, k);
   if (root->data == k && root->leftChild == NULL &&
   root->rightChild == NULL)
      return nullptr;
   return root;
}
void inorder(Node* root){
   if (root != NULL){
      inorder(root->leftChild);
      inorder(root->rightChild);
      cout << root->data << " ";
   }
}
int main(void){
   struct Node* root = newNode(6);
   root->leftChild = newNode(7);
   root->rightChild = newNode(7);
   root->leftChild->leftChild = newNode(5);
   root->leftChild->rightChild = newNode(3);
   root->rightChild->rightChild = newNode(7);
   deleteLeafNode(root, 7);
   cout << "Inorder traversal after deleting given leaf node: ";
   inorder(root);
   return 0;
}

ผลลัพธ์

รหัสข้างต้นจะสร้างผลลัพธ์ต่อไปนี้ -

Inorder traversal after deleting given leaf node: 5 3 7 6