C++二叉搜索树增删操作后规范输出遍历结果的代码问题修复

需求说明 #

• 先接收用户输入的数值插入二叉搜索树，遇到-1停止插入
• 之后读取所有待删除的节点值，遇到-1停止读取，先把所有待删值全部收集完成
• 收集完成后逐个执行节点删除操作，每删除一个节点依次打印当前树的前序、中序、后序遍历结果

问题描述 #

当前代码逻辑不符合要求：读取待删除数值的过程中，每读入一个就立刻执行删除并打印遍历结果，没有先收集全部待删值再统一处理。

输入示例 #

//These values will be added to tree
50
30
35
61
24
58
62
32
-1
//These values will be removed from tree
30
24
32
-1

预期输出 #

50 32 24 35 61 58 62 
24 32 35 50 58 61 62 
24 35 32 58 62 61 50 

50 32 35 61 58 62 
32 35 50 58 61 62 
35 32 58 62 61 50 

50 35 61 58 62 
35 50 58 61 62 
35 58 62 61 50

实际输出 #

50
30
35
61
24
58
62
32
-1
30
 50 32 24 35 61 58 62
 24 32 35 50 58 61 62
 24 35 32 58 62 61 50
24
 50 32 35 61 58 62
 32 35 50 58 61 62
 35 32 58 62 61 50
32
 50 35 61 58 62
 35 50 58 61 62
 35 58 62 61 50
-1

现有main函数代码 #

int main()
{

    Node *root = NULL;
    int num;
    cin >> num;

    while (num != -1)
    {
        root = insert(root, num);
        cin >> num;
    }
    cin >> num;
    while (num != -1)
    {

        root = deleteNode(root, num); // delete from tree
        preorder(root); // print preorder
        cout << endl;
        inorder(root); // print inorder
        cout << endl;
        postorder(root); //print postorder
        cout << endl;
        cin >> num; 
    }

    return 0;
}

修复方案 #

调整逻辑新增容器存储待删除值，先完成全部待删值收集后再逐个执行删除打印操作，修复后代码如下：

#include <vector> // 引入vector容器存储待删除值

int main()
{
    Node *root = NULL;
    int num;
    cin >> num;

    // 插入节点逻辑保持不变
    while (num != -1)
    {
        root = insert(root, num);
        cin >> num;
    }

    vector<int> delList;
    cin >> num;
    // 仅收集待删除值，不执行删除操作
    while (num != -1)
    {
        delList.push_back(num);
        cin >> num;
    }

    // 逐个删除并打印遍历结果
    for(int delVal : delList)
    {
        root = deleteNode(root, delVal);
        preorder(root);
        cout << endl;
        inorder(root);
        cout << endl;
        postorder(root);
        cout << endl << endl;
    }

    return 0;
}

内容的提问来源于stack exchange，提问作者Anonymous