Xóa node lá có giá trị k trong cây nhị phân C++

Giới thiệu

Xóa tất cả node lá (leaf nodes) có giá trị bằng k trong cây nhị phân. Sử dụng đệ quy post-order: xử lý con trước, rồi quyết định xóa node hiện tại.

Thuật toán đệ quy

deleteLeaf(node, k):
    if node == NULL: return NULL
    
    node->left = deleteLeaf(node->left, k)
    node->right = deleteLeaf(node->right, k)
    
    if node->data == k AND node->left == NULL AND node->right == NULL:
        return NULL  // Xóa node này
    
    return node

Ví dụ

Cây gốc (inorder): 3 2 4 1 4 3 4 5 4

Xóa node lá giá trị 4:

Kết quả (inorder): 3 2 1 3 5

Mã nguồn hoàn chỉnh

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int data;
    Node *left, *right;
};

Node* newNode(int data) {
    Node* node = new Node;
    node->data = data;
    node->left = node->right = NULL;
    return node;
}

Node* deleteLeafNodes(Node* root, int k) {
    if (!root) return nullptr;
    
    // Đệ quy xử lý cây con trước (post-order)
    root->left = deleteLeafNodes(root->left, k);
    root->right = deleteLeafNodes(root->right, k);
    
    // Kiểm tra node hiện tại: là lá VÀ giá trị = k
    if (root->data == k && !root->left && !root->right) {
        delete root;
        return nullptr;
    }
    
    return root;
}

void inorder(Node* root) {
    if (!root) return;
    inorder(root->left);
    cout << root->data << " ";
    inorder(root->right);
}

int main() {
    Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(3);
    root->left->right = newNode(4);
    root->right->left = newNode(4);
    root->right->right = newNode(5);
    root->right->right->left = newNode(4);
    root->right->right->right = newNode(4);
    
    cout << "Cay goc (inorder): ";
    inorder(root); cout << endl;
    
    deleteLeafNodes(root, 4);
    
    cout << "Cay sau khi xoa la=4: ";
    inorder(root); cout << endl;
    
    return 0;
}

Kết quả chạy chương trình

Cay goc (inorder): 3 2 4 1 4 3 4 5 4
Cay sau khi xoa la=4: 3 2 1 3 5

Phân tích độ phức tạp

• Thời gian: O(n) - thăm mỗi node 1 lần
• Không gian: O(h) - stack đệ quy

Lưu ý quan trọng

Sau khi xóa node lá, node cha của nó có thể trở thành node lá mới. Nếu node cha cũng có giá trị k, nó sẽ bị xóa ở lần đệ quy quay về (caller). Điều này xử lý tự động nhờ post-order.

Ví dụ xóa dây chuyền

Cây:       4           Xóa lá=4
          / \
         4   5
        /
       4

Bước 1: Xóa lá trái nhất (4)
Bước 2: Node cha (4) thành lá → xóa tiếp
Bước 3: Gốc (4) thành lá → xóa tiếp
Kết quả: chỉ còn 5

Kết luận

Đệ quy post-order tự nhiên xử lý việc xóa node lá có thể tạo ra node lá mới. Code ngắn gọn, đúng đắn, không cần vòng lặp phức tạp.