Xóa cây nhị phân dùng từ khóa delete và Destructor trong C++

Giới thiệu

Sử dụng destructor (hàm hủy) của C++ để tự động xóa toàn bộ cây nhị phân khi gọi delete root. Destructor đệ quy xóa left và right child.

Cơ chế Destructor

Khi gọi delete root:

1. Destructor của root được gọi
2. Destructor gọi delete left và delete right
3. Đệ quy xóa toàn bộ cây con
4. In thông báo xóa (tùy chọn)

Mã nguồn hoàn chỉnh

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

class Node {
public:
    int data;
    Node* left;
    Node* right;
    
    // Constructor
    Node(int data) {
        this->data = data;
        this->left = NULL;
        this->right = NULL;
    }
    
    // Destructor
    ~Node() {
        delete left;   // Đệ quy xóa cây con trái
        delete right;  // Đệ quy xóa cây con phải
        cout << "Da xoa node: " << this->data << endl;
    }
};

int main() {
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);
    root->right->left = new Node(6);
    root->right->right = new Node(7);
    
    // Xóa toàn bộ cây - chỉ cần 1 câu lệnh!
    delete root;
    
    return 0;
}

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

Da xoa node: 4
Da xoa node: 5
Da xoa node: 2
Da xoa node: 6
Da xoa node: 7
Da xoa node: 3
Da xoa node: 1

Thứ tự xóa (Post-order)

Destructor thực hiện xóa theo thứ tự hậu tự (post-order): con trái → con phải → node cha. Điều này đảm bảo không rò rỉ bộ nhớ (memory leak).

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

• Thời gian: O(n) - gọi destructor cho mỗi node
• Không gian: O(h) - stack đệ quy

So sánh các phương pháp xóa cây

Modern C++: Sử dụng unique_ptr

#include 

struct Node {
    int data;
    unique_ptr left, right;
    
    Node(int d) : data(d), left(nullptr), right(nullptr) {}
    // Không cần destructor! unique_ptr tự xóa khi hết scope
};

int main() {
    auto root = make_unique(1);
    root->left = make_unique(2);
    root->right = make_unique(3);
    // Tự động xóa khi root hết scope
}

Kết luận

Destructor là cách C++ cổ điển quản lý bộ nhớ cây. Modern C++ khuyến khích dùng std::unique_ptr để tự động hóa và an toàn hơn (RAII - Resource Acquisition Is Initialization).