Computer >> Máy Tính >  >> Lập trình >> C ++

Xóa các nút lá có giá trị k trong chương trình C ++

Trong hướng dẫn này, chúng ta sẽ tìm hiểu cách xóa các nút lá khỏi cây với giá trị đã cho.

Hãy xem các bước để giải quyết vấn đề.

  • Viết một nút cấu trúc cho cây nhị phân.

  • Viết một hàm để duyệt (đặt hàng trước, đặt hàng trước, đặt hàng sau) qua cây và in tất cả dữ liệu.

  • Khởi tạo cây bằng cách tạo các nút với cấu trúc.

  • Khởi tạo giá trị x.

  • Viết hàm xóa các nút lá có giá trị cho trước. Nó chấp nhận hai đối số là nút gốc và giá trị k.

    • Nếu gốc là trả về null.

    • Thay thế nút bên trái của nút gốc bằng nút gốc mới sau khi xóa.

    • Tương tự với nút bên phải của gốc.

    • Nếu dữ liệu nút gốc hiện tại bằng k và nó là nút lá, thì trả về một con trỏ null.

    • Trả lại nút gốc

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

Đầu ra

Nếu bạn thực thi đoạn mã trên, bạn sẽ nhận được kết quả sau.

Tree: 3 2 1 3 5

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.