include <iostream>

// 定义二叉树节点结构
struct TreeNode {

int data;
TreeNode* left;
TreeNode* right;

TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}

};

// 在二叉搜索树中查找要删除的节点
TreeNode findMin(TreeNode node) {

while (node->left != nullptr) {
    node = node->left;
}
return node;

}

// 删除节点
TreeNode deleteNode(TreeNode root, int key) {

if (root == nullptr) return root;

// 在左子树中递归查找要删除的节点
if (key < root->data) {
    root->left = deleteNode(root->left, key);
}
// 在右子树中递归查找要删除的节点
else if (key > root->data) {
    root->right = deleteNode(root->right, key);
}
// 当找到要删除的节点时
else {
    // 节点只有一个子节点或者没有子节点
    if (root->left == nullptr) {
        TreeNode* temp = root->right;
        delete root;
        return temp;
    } else if (root->right == nullptr) {
        TreeNode* temp = root->left;
        delete root;
        return temp;
    }
    
    // 节点有两个子节点
    TreeNode* temp = findMin(root->right);
    root->data = temp->data;
    root->right = deleteNode(root->right, temp->data);
}
return root;

}

// 中序遍历打印二叉树节点值
void inorderTraversal(TreeNode* root) {

if (root == nullptr) return;
inorderTraversal(root->left);
std::cout << root->data << " ";
inorderTraversal(root->right);

}

int main() {

TreeNode* root = nullptr;

// 添加节点
root = insertNode(root, 5);
insertNode(root, 3);
insertNode(root, 7);
insertNode(root, 1);
insertNode(root, 4);
insertNode(root, 6);
insertNode(root, 8);

std::cout << "Binary Tree before deletion: ";
inorderTraversal(root);
std::cout << std::endl;

// 删除节点值为3的节点
root = deleteNode(root, 3);

std::cout << "Binary Tree after deletion: ";
inorderTraversal(root);
std::cout << std::endl;

return 0;

}