การลบโหนดในต้นไม้แบบทวิภาค (Deletion in Binary Tree) ใน C++

แนวคิด

การลบโหนดใน Binary Tree (ไม่ใช่ BST) ทำโดยการแทนที่โหนดที่จะลบด้วย โหนดล่างสุดและขวาสุด (Deepest Rightmost Node) แล้วลบโหนดล่างสุดนั้นออก

ขั้นตอน

1. Level Order Traversal (BFS) หาโหนดที่จะลบ (data_node) และโหนดล่างสุด (temp)
2. คัดลอกค่าของ temp ไป data_node
3. ลบ temp (ต้องหา parent ของ temp เพื่อตั้งค่า left/right = NULL)

โปรแกรมตัวอย่าง

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

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

void deleteDeepest(Node* root, Node* deepest) {
    queue<Node*> q;
    q.push(root);
    while (!q.empty()) {
        Node* temp = q.front(); q.pop();
        if (temp == deepest) { delete deepest; return; }
        if (temp->right) {
            if (temp->right == deepest) { temp->right = nullptr; delete deepest; return; }
            q.push(temp->right);
        }
        if (temp->left) {
            if (temp->left == deepest) { temp->left = nullptr; delete deepest; return; }
            q.push(temp->left);
        }
    }
}

Node* deletion(Node* root, int key) {
    if (!root) return nullptr;
    if (!root->left && !root->right) {
        if (root->data == key) return nullptr;
        return root;
    }
    
    queue<Node*> q;
    q.push(root);
    Node *temp = nullptr, *data_node = nullptr;
    
    while (!q.empty()) {
        temp = q.front(); q.pop();
        if (temp->data == key) data_node = temp;
        if (temp->left) q.push(temp->left);
        if (temp->right) q.push(temp->right);
    }
    
    if (data_node) {
        int x = temp->data;
        deleteDeepest(root, temp);
        data_node->data = x;
    }
    return root;
}

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

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);
    
    cout << "Inorder before deletion: ";
    inorder(root);
    
    root = deletion(root, 13);
    
    cout << "\nInorder after deletion: ";
    inorder(root);
    return 0;
}

ผลลัพธ์

Inorder before deletion: 9 13 14 12 17 11 10
Inorder after deletion: 9 10 14 12 17 11