c++ - 删除二叉树节点的正确方法

Question

我有这个问题，当我尝试删除(使用选项 5)ID 为 101 的节点并想打印剩余的两个节点(ID 为 100,102)时。我的程序正确打印(使用选项 2)100，但对于其余部分它会产生一些垃圾值并且程序停止工作？

我怀疑内存管理有问题，请问有人能找到合适的方法吗。

#include<stdlib.h>
#include<stdio.h>
#include <iostream>
#include <iomanip> 
using namespace std;
struct bin_tree
{
    int Uid;
    int data;
    bool flag_add;
    bool flag_change;
    bool flag_delete;
    struct bin_tree * right, * left;

};
typedef struct bin_tree node;

void insert(node ** tree,int ID, int val,bool new_data, bool change_data, bool delete_data)
{
    node *temp = NULL;
    if(!(*tree))
    {
        temp = new node;
        temp->left =  NULL;
        temp->right = NULL;
        temp->Uid=ID;
        temp->data = val;
        temp->flag_add= new_data;
        temp->flag_change=change_data;
        temp->flag_delete=delete_data;
        *tree = temp;
        return;
    }else
    {

        if(val < (*tree)->data)
        {
            insert(&(*tree)->left, ID, val,new_data, change_data, delete_data);
        }
        else
        {
            insert(&(*tree)->right,ID, val,new_data, change_data, delete_data);
        }
    }
}

void print_preorder(node * tree, int indent=0)
{

    cout<<"GUID"<<tree->Uid <<"D"<< tree->data <<"NF"<<tree->flag_add<<"CF"<<tree->flag_change<<"DF"<<tree->flag_delete<< "\n ";


    if (tree!= NULL)
    {
        if(tree->left) print_preorder(tree->left, indent+2);

        if(tree->right) print_preorder(tree->right, indent+2);

        if (indent)
        {
            std::cout << std::setw(indent) << ' ';
        }

    }
}





node* search(node ** tree, int ID)
{
    if(!(*tree))
    {
        return NULL;
    }

    if(ID < (*tree)->Uid)
    {
        search(&((*tree)->left), ID);
    }
    else if(ID > (*tree)->Uid)
    {
        search(&((*tree)->right), ID);
    }
    else if(ID == (*tree)->Uid)
    {
        return *tree;
    }
}
node*  update(node ** tree,int ID, int val,bool new_data, bool change_data, bool delete_data)
{
    (*tree)->Uid = ID;
    (*tree)->data = val;
    (*tree)->flag_add= new_data;
    (*tree)->flag_change= change_data;
    (*tree)->flag_delete= delete_data;

    return *tree;


}


void change(node ** tree,int ID, int val,bool new_data, bool change_data, bool delete_data)
{

    node *temp;
    node* updt;

    temp = search(&(*tree), ID);

    if(temp)
    {
        cout<<"ID is found"<<endl;
        cout<<"Node current data is "<<temp->Uid<<temp->data<<temp->flag_add<<temp->flag_change<<temp->flag_delete<<endl;
        if(updt = update(&temp,ID, val, new_data, change_data, delete_data))
        {
            cout<<"Node updated data is "<<updt->Uid<<updt->data<<updt->flag_add<<updt->flag_change<<updt->flag_delete;
        }else
        {
            cout<<"data couldnt be updated"<<endl;
        }
    }else
    {
        cout<<"sorry data is not found"<<endl;

    }


}

int deltree(node ** tree, int id)
{
    node *del_node;
    del_node= search( &(*tree), id);
    if(del_node)
    {
        delete del_node;

    }
    return 0;
}

int main()
{
    node *root;
    node *tmp;
    int number;
    int id;



    root = NULL;
    int UID;
    int Data;
    bool n_flag;
    bool c_flag;
    bool d_flag;
    /* Inserting nodes into tree */

    while(1)
    {
        cout<<endl<<endl;
        cout<<" Binary Search Tree Operations "<<endl;
        cout<<" ----------------------------- "<<endl;
        cout<<" 1. Insertion/Creation "<<endl;
        cout<<" 2. Pre-Order Traversal "<<endl;
        cout<<" 3. Removal "<<endl;// actually its for searching not for removal
        cout<<" 4. change "<<endl;
        cout<<" 5. delete "<<endl;
        cout<<" 6. EXIT "<<endl;

        cout<<" Enter your choice : ";
        cin>>number;
        switch(number)
        {
        case 1:

            /*cout<<"enter the number GUID"<<endl;
            cin>>UID;
            cout<<"enter the Data you want"<<endl;
            cin>>Data;
            cout<<"is New data ?"<<endl;
            cin>>n_flag;
            cout<<"is changed data?"<<endl;
            cin>>c_flag;
            cout<<"is delete data ?"<<endl;
            cin>>d_flag;*/

            /*  insert(&root,UID, Data, n_flag, c_flag,d_flag);*/

            insert(&root,100, 700, 1, 0,0);
            insert(&root,101, 701, 1, 0,0);
            insert(&root,102, 702, 1, 0,0);
            break;

        case 2:
            /* Printing nodes of tree */
            cout<<"Pre Order tree Display";
            print_preorder(root);
            break;

        case 3:

            /* Search node into tree */
            tmp = search(&root, 4);
            if (tmp)
            {
                printf("Searched node=%d\n", tmp->data);
            }
            else
            {
                printf("Data Not found in tree.\n");
            }
            break;
        case 4:

            cout<<"enter the number GUID"<<endl;
            cin>>UID;
            cout<<"enter the Data you want"<<endl;
            cin>>Data;
            cout<<"is New data ?"<<endl;
            cin>>n_flag;
            cout<<"is changed data?"<<endl;
            cin>>c_flag;
            cout<<"is delete data ?"<<endl;
            cin>>d_flag;

            change (&root,UID, Data, n_flag, c_flag,d_flag);

            break;
        case 5:
            cout<<"enter the node id to be deleted";
            cin>>id;
            int m;
            m = deltree(&root, id);
            if(m) cout<<"Node_Deleted";
            break;
        case 6 :
            return 0;

        }

    }
}

输出

Answer 1

删除树中的节点时，必须妥善管理其子节点。在这里，您将删除节点和指向其子节点的指针。您需要找到一种方法将剩余的 child 添加回树中。