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

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

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 đệ quy xóa nút lá có giá trị k:

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

Duyệt inorder để in cây sau xóa.

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* deleteLeafNode(Node* root, int k) {
    if (root == NULL)
        return nullptr;
    root->leftChild = deleteLeafNode(root->leftChild, k);
    root->rightChild = deleteLeafNode(root->rightChild, k);
    if (root->data == k && 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(6);
    root->leftChild = newNode(7);
    root->rightChild = newNode(7);
    root->leftChild->leftChild = newNode(5);
    root->leftChild->rightChild = newNode(3);
    root->rightChild->rightChild = newNode(7);
    deleteLeafNode(root, 7);
    cout << "Duyệt inorder sau xóa nút lá 7: ";
    inorder(root);
    return 0;
}

Kết quả

Duyệt inorder sau xóa nút lá 7: 5 3 7 6