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

Giới thiệu

Bài toán tương tự xóa node lá giá trị k: xóa tất cả node lá (leaf nodes) có giá trị bằng x trong cây nhị phân.

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 x) {
    if (!root) return nullptr;
    
    root->left = deleteLeafNodes(root->left, x);
    root->right = deleteLeafNodes(root->right, x);
    
    if (root->data == x && !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(root); cout << endl;
    
    deleteLeafNodes(root, 4);
    
    cout << "Sau xoa la=4: ";
    inorder(root); cout << endl;
    
    return 0;
}

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

Cay goc: 3 2 4 1 4 3 4 5 4
Sau xoa la=4: 3 2 1 3 5

Phân tích

Bài này trùng lặp với bài 1003078489 (chỉ khác tên biến k/x). Cùng thuật toán, cùng kết quả.

Kết luận

Xóa node lá theo giá trị dùng đệ quy post-order là mẫu thiết kế (pattern) phổ biến cho các bài toán biến đổi cây nhị phân.