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

Định nghĩa cấu trúc nút cây nhị phân:

struct Node {
    int data;
    struct Node *leftChild, *rightChild;
};

Hàm tạo nút mới:

struct Node* newNode(int data) {
    struct Node* newNode = new Node;
    newNode->data = data;
    newNode->leftChild = newNode->rightChild = NULL;
    return (newNode);
}

Hàm deleteLeafNode (hoặc deleteNode) đệ quy xóa nút lá giá trị x:

Node* deleteLeafNode(Node* root, int x) {
    if (root == NULL)
        return nullptr;
    root->leftChild = deleteLeafNode(root->leftChild, x);
    root->rightChild = deleteLeafNode(root->rightChild, x);
    if (root->data == x && root->leftChild == NULL && root->rightChild == NULL)
        return nullptr;
    return root;
}

Ví dụ hoàn chỉnh

#include <iostream>
using namespace std;

struct Node {
    int data;
    struct Node *leftChild, *rightChild;
};

struct Node* newNode(int data) {
    struct Node* newNode = new Node;
    newNode->data = data;
    newNode->leftChild = newNode->rightChild = NULL;
    return (newNode);
}

Node* deleteNode(Node* root, int x) {
    if (root == NULL)
        return nullptr;
    root->leftChild = deleteNode(root->leftChild, x);
    root->rightChild = deleteNode(root->rightChild, x);
    if (root->data == x && root->leftChild == NULL && root->rightChild == NULL)
        return nullptr;
    return root;
}

void inorder(Node* root) {
    if (root != NULL) {
        inorder(root->leftChild);
        inorder(root->rightChild);
        cout << root->data << " ";
    }
}

int main(void) {
    struct Node* root = newNode(4);
    root->leftChild = newNode(2);
    root->rightChild = newNode(12);
    root->leftChild->leftChild = newNode(3);
    root->leftChild->rightChild = newNode(5);
    root->rightChild->rightChild = newNode(9);
    deleteNode(root, 3);
    cout << "Duyệt inorder sau xóa: ";
    inorder(root);
    return 0;
}

Kết quả

Duyệt inorder sau xóa: 5 2 9 12 4