二叉查找树的结点删除操作

Question

该代码实现二叉查找树的建立、中序遍历、结点的插入与删除等操作。为什么该代码还没有输入要删除的结点，程序就自动执行了？

经过断点调试，scanf语句似乎没起到应有的作用。

#include <stdio.h>
#include <stdlib.h>
#include <vector>

using namespace std;

typedef int KeyType;

// 二叉查找树的结构体
typedef struct BSTNode {
    KeyType key;   // 数据
    BSTNode *lchild, *rchild;   // 左右子树
} BSTNode, *BiTree;

// 向二叉查找树插入结点
void insert_to_tree(BiTree& tree, KeyType key) {
    BiTree tnode = (BiTree)calloc(1, sizeof(BSTNode));   // 新结点
    tnode->key = key;    // 把值放入
    if (tree != NULL) {
        BiTree tcur = tree, parent;   // tcur为当前结点，parent为父节点
        while (tcur) {
            parent = tcur;
            if (key < tcur->key) {
                tcur = tcur->lchild;
            } else {
                tcur = tcur->rchild;
            }
        }
        if (key < parent->key) {
            parent->lchild = tnode;
        } else {
            parent->rchild = tnode;
        }
        return;
    } else {
        tree = tnode;
        return;
    }
}

// 建立二叉查找树
void create_BST(BiTree& tree) {
    KeyType key;
    vector<KeyType> vk;
    while(scanf("%d", &key)) {
        vk.push_back(key);
    }
    for (int i = 0; i < vk.size(); i++) {
        key = vk[i];
        insert_to_tree(tree, key);
    }
}

void delete_BST(BiTree& tree, KeyType key) {
    if (tree == nullptr) {
        return;
    }

    if (tree->key < key) {
        delete_BST(tree->rchild, key);
    } else if (tree->key > key) {
        delete_BST(tree->lchild, key);
    } else {
        // 找到待删除结点
        BiTree temp = tree;
        if (tree->lchild == nullptr) {
            tree = tree->rchild;
            free(temp);
        } else if (tree->rchild == nullptr) {
            tree = tree->lchild;
            free(temp);
        } else {
            temp = tree->lchild;
            while (temp->rchild) {
                temp = temp->rchild;
            }
            tree->key = temp->key;
            delete_BST(tree->lchild, temp->key);
        }
    }

}

void in_order(BiTree tree) {
    if (tree) {
        in_order(tree->lchild);
        printf("%3d", tree->key);
        in_order(tree->rchild);
    }
}

int main() {
    BiTree tree = nullptr;
    create_BST(tree);
    in_order(tree);

    KeyType k;
    printf("\nPlease input the key: ");
    scanf("%d", &k);
    delete_BST(tree, k);
    in_order(tree);
    return 0;
}

Answer 1

【以下回答由 GPT 生成】

要优化代码以便在执行删除操作之前需要先输入要删除的节点，可以修改delete_BST函数的实现。

修改后的代码如下:

void delete_BST(BiTree& tree, KeyType key) {
    if (tree == nullptr) {
        return;
    }

    // 在删除操作之前首先输入要删除的节点
    KeyType deleteKey;
    printf("请输入要删除的节点: ");
    scanf("%d", &deleteKey);

    if (tree->key < deleteKey) {
        delete_BST(tree->rchild, deleteKey);
    } else if (tree->key > deleteKey) {
        delete_BST(tree->lchild, deleteKey);
    } else {
        // 执行删除操作
    }
}

在函数开始部分添加了输入语句printf("请输入要删除的节点: ");和scanf语句，用于在执行删除操作之前先输入要删除的节点。

这样，当调用delete_BST函数时，会先要求输入要删除的节点，然后再执行相应的删除操作。

希望以上解决方案能对您有所帮助，如果有任何其他问题，请随时提问。

【相关推荐】

• 帮你找了个相似的问题, 你可以看下: https://ask.csdn.net/questions/7615003
• 这篇博客你也可以参考下：指针详细概念知识点及运用，指针与常量，指针的运算，scanf()中的&有什么用？你想知道的，都在这儿~ 1.1.4
• 您还可以看一下 张景平老师的C语言零基础入门(计算机二级考试)课程中的 06-16 scanf函数特殊用法小节, 巩固相关知识点
  
• 除此之外, 这篇博客: 【C语言】华软C语言程序设计复习中的 17. scanf函数与gets函数各自的优缺点（能否正常接收空格字符） 部分也许能够解决你的问题。

如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^