c++ - 实现二叉树时双重释放或损坏

更新:

根据要求添加更多代码。粘贴到问题的末尾。谢谢大家停下来。

当前代码可以删除一个叶子，但是进入根目录后，它不能删除。

====
更新:
我修改代码，将removeRootMatch更改为

tmp = Root;
Root = tmp->Right;
tmp->Right = NULL;
delete tmp;

也没有错误，但它不会删除节点。

=====

该程序很简单，请执行以下步骤:

查找二叉树的最小值；

将最小值记录在 vector 中；

删除树中具有最小值的节点；

重复1-3，直到树为空。

我有removeNode()函数，如果需要删除的一个是Root，它将调用removeRoot函数(下面的检查代码)。但是我在使用此功能时遇到麻烦。我在进行调试，发现removeRootMatch函数出问题了。运行时出现错误。我收到的错误是*** glibc detected *** ./bintree: double free or corruption (fasttop): 0x0000000000727060 ***，有人可以帮助我吗？

树定义如下，语言是c++

typedef struct myNode* LPNode;
typedef struct myNode Node;
struct myNode
{
  double key;

  LPNode Left; //left subtree
  LPNode Right; //right subtree
};

程序主要部分如下:

nmax初始化为0，

sortedvector分配为一个空间，该空间的大小与树中的总节点

相同

min初始化为99999。

minValue将返回树的最小值。

compareDouble(a，b)将返回1 if a < b，返回2 if a > b，如果等于

，则返回3

代码如下

    void removeRootMatch(LPNode Root)
{
    LPNode tmp = MakeNewNode(Root->key);
    tmp->Left = Root->Left;
    tmp->Right = Root->Right;
    //no child
    if(Root->Left==NULL && Root->Right == NULL) {

        Root=NULL;
    delete Root;
    } else if(Root->Left==NULL && Root->Right!=NULL){ //one right child
        //delete Root;
            Root = tmp->Right;
        tmp->Right = NULL;
        delete tmp;
    } else {
        printf("Remove root bug!\n");
    }
}

这是函数调用removeNode函数。

//compare double
int compareDouble(double a,double b)
{
    if(a-b<-EPSILON) //a<b
        return 1;
    else if(a-b>EPSILON)//a>b
        return 2;
    else
        return 3;
}


//find the min key in a tree
double minValue(LPNode Root,double min)
{
    if(Root == NULL)
        return min;
    if(compareDouble(Root->key,min)==1)
        min = Root->key;
    min = minValue(Root->Left, min);
    min = minValue(Root->Right, min);
    return min;
}

//remove root
void removeRootMatch(LPNode& Root)
{
    LPNode tmp = MakeNewNode(Root->key);
    tmp->Left = Root->Left;
    tmp->Right = Root->Right;
    //no child
    if(Root->Left==NULL && Root->Right == NULL) {
        Root=NULL;
        delete Root;
    } else if(Root->Left==NULL && Root->Right!=NULL){ //one right child

        double k = Root->key;


        Root = tmp->Right;
        tmp->Right = NULL;
        delete tmp;
        //tmp=tmp->Right;
        //Root->Right = NULL;
        //delete Root;
        //Root = tmp;





    } else {
        printf("Remove root bug!\n");
    }
}

//remove a node
void removeMatch(LPNode& Root,LPNode match,bool left)
{
    //no child
    if(match->Left==NULL && match->Right == NULL){
        double k = match->key;
        left==true?
        Root->Left=NULL:
        Root->Right=NULL;
        delete match;
        if(!Root->Left)printf("%f  ",k);
    }
    else if(match->Left==NULL && match->Right!=NULL){//one right child
                double k = match->key;

        left==true?
        Root->Left=match->Right:
        Root->Right=match->Right;
        delete match;
        if(!Root->Left)printf("%f  ",k);
    } else {
        printf("Remove root bug!\n");
    }
}


//delete a node
void removeNode(LPNode Root,double min)
{
    if(compareDouble(min,Root->key)==3){
        removeRootMatch(Root);
    }else if(compareDouble(min,Root->key)==1 && Root->Left != NULL) {

        compareDouble(min,Root->Left->key)==3 ?
        removeMatch(Root,Root->Left,true):
        removeNode(Root->Left,min);
    }else if(compareDouble(min,Root->key)==2 && Root->Right != NULL){

        compareDouble(min,Root->Right->key)==3 ?
        removeMatch(Root,Root->Right,false):
        removeNode(Root->Right,min);
    }else{
        printf("Remove bug1!\n");
    }
}

//call minValue to find the min key
//record the min key in a vector
//call removeNode to delete the Node
//repeat till the tree is empty
void problem1(LPNode Root,double* sortedvector,int& nmax)
{
    double min;
    //while(Root!=NULL)
    for(int i=0;i<3;i++)
    {
        min = MAX;
        sortedvector[nmax] = minValue(Root,min) ;
        printf("inv%f\n",sortedvector[nmax]);
        removeNode(Root,sortedvector[nmax]);
        nmax++;
    }
    printf("The tree is empty");
}

最佳答案

如果您的函数removeNode可以调整Root，则说明您的函数未正确声明。

 void removeRootMatch(LPNode Root)

您正在传递指向Root的指针。在removeRootMatch函数内部，您正在处理指针的副本。因此，在removeRootMatch函数内部的代码如下:

Root = tmp->Right;
    tmp->Right = NULL;
    delete tmp;

函数返回时不会更改“根”节点。

要解决此问题，您应该通过引用传递Root指针:

 void removeRootMatch(LPNode& Root)