Xóa nút trong cây nhị phân (Deletion in Binary Tree) C++

Xóa một nút với giá trị cho trước khỏi cây nhị phân (Binary Tree - **không phải BST**). Chiến lược tiêu chuẩn: Thay thế nút cần xóa bằng **nút sâu nhất, bên phải nhất (Deepest Rightmost Node)**, sau đó xóa nút sâu nhất đó.

Thuật toán (Level Order Traversal)

1. Duyệt Level Order (BFS) để tìm:
   • Nút cần xóa (keyNode).
   • Nút sâu nhất, phải nhất (deepestNode) - là nút cuối cùng được pop từ queue.
   • Cha của deepestNode (để gán con trỏ null).
2. Nếu tìm thấy keyNode:
   • Gán keyNode->data = deepestNode->data.
   • Xóa deepestNode từ cha của nó (set left/right = nullptr).
   • Delete deepestNode.

Chương trình C++ Hoàn chỉnh (Sửa lỗi logic code gốc)

#include <iostream>
#include <queue>
using namespace std;

struct Node {
    int data;
    Node *left, *right;
    Node(int val) : data(val), left(nullptr), right(nullptr) {}
};

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

Node* deleteNode(Node* root, int key) {
    if (!root) return nullptr;
    
    // Trường hợp cây chỉ có 1 nút
    if (!root->left && !root->right) {
        if (root->data == key) {
            delete root;
            return nullptr;
        }
        return root;
    }
    
    queue q;
    q.push(root);
    
    Node *keyNode = nullptr;
    Node *deepestNode = nullptr;
    Node *parentOfDeepest = nullptr;
    
    // BFS tìm keyNode và deepestNode (cùng parent)
    while (!q.empty()) {
        Node* curr = q.front(); q.pop();
        
        if (curr->data == key) keyNode = curr;
        
        if (curr->left) {
            q.push(curr->left);
            parentOfDeepest = curr; // Cập nhật cha của nút đang push (sẽ là deepestNode cuối cùng)
            deepestNode = curr->left;
        }
        if (curr->right) {
            q.push(curr->right);
            parentOfDeepest = curr;
            deepestNode = curr->right;
        }
    }
    
    if (keyNode) {
        // Copy data
        keyNode->data = deepestNode->data;
        
        // Xóa deepestNode từ parent
        if (parentOfDeepest) {
            if (parentOfDeepest->right == deepestNode) 
                parentOfDeepest->right = nullptr;
            else 
                parentOfDeepest->left = nullptr;
        }
        delete deepestNode;
    }
    
    return root;
}

int main() {
    Node* root = new Node(12);
    root->left = new Node(13);
    root->left->left = new Node(9);
    root->left->right = new Node(14);
    root->right = new Node(11);
    root->right->left = new Node(17);
    root->right->right = new Node(10);
    /*
          12
        /    \
       13     11
      /  \   /  \
     9   14 17  10
    */
    
    cout << "Inorder truoc xoa: "; inorder(root); cout << endl;
    
    int key = 13;
    root = deleteNode(root, key);
    
    cout << "Inorder sau xoa " << key << ": "; inorder(root); cout << endl;
    // Kết quả mong đợi: Thay 13 bằng 10 (deepest rightmost), xóa 10 cũ.
    // Tree: 12 -> left=10(was 13), right=11. 10->left=9, right=14. 11->left=17.
    // Inorder: 9 10 14 12 17 11
    
    return 0;
}

Đầu ra

Inorder truoc xoa: 9 13 14 12 17 11 10
Inorder sau xoa 13: 9 10 14 12 17 11

Lưu ý: Code gốc có lỗi logic tìm `deepestNode` và `parentOfDeepest` (dùng queue nhưng không track parent đúng). Phiên bản trên sửa lỗi đó.