Xóa các nút lá có giá trị k trong C ++?

Đầu tiên chúng ta hãy xác định cấu trúc đại diện cho một nút cây chứa dữ liệu và nút con trái và phải của nó. Nếu đây là nút đầu tiên được tạo thì đó là nút gốc, ngược lại là nút con.

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

Tiếp theo, chúng tôi tạo hàm newNode (int data) của chúng tôi, nhận một giá trị int và gán nó cho thành viên dữ liệu của nút. Hàm trả về con trỏ tới struct Node đã tạo. Ngoài ra, nút con bên trái và bên phải của nút mới tạo được đặt thành null.

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

Bây giờ chúng ta tạo hàm deleteNode (Node * root, int k) để xóa nút gốc và giá trị dữ liệu của nút đó. Nếu nút đã cho là nút cha thì nó cũng xóa nút con bên trái và bên phải của nó. Hàm trả về nút gốc đã sửa đổi sau khi xóa nút đã cho.

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;
}

Cuối cùng, để hủy bỏ cây sau khi xóa, chúng ta có một hàm inorder (Node * root) đi ngang qua cây trong hàm inorder.

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

Ví dụ

Chúng ta hãy xem cách thực hiện xóa các nút lá có giá trị k sau đây.

#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;
}

Đầu ra

Đoạn mã trên sẽ tạo ra kết quả sau -

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