c++ - 分段故障二叉树

Question

我正在尝试实现二进制树，但我在插入方法中遇到了问题。如果我添加第一个元素，程序不会崩溃，但是当我引入 2 个或更多元素时，程序会崩溃。

这是代码

template <typename T>
void Arbol<T>:: insertar( T c){
    if(laraiz==0)
    {
        laraiz=new celdaArbol;
        laraiz->elemento=c;
        laraiz->padre=laraiz->hizqu=laraiz->hder=0;
    }
    else {
        celdaArbol *com=laraiz;
        bool poner=false;
        while(poner==false){
            if(c>com->elemento){
                if(com->hder==0){
                    com->hder= new celdaArbol;
                    com->hder->elemento=c;
                    com->hder->padre=com;
                    poner=true;
                }
                else{
                    com=com->hder;
                }
            }
            else {
                if(com->hizqu==0){
                    com->hizqu= new celdaArbol;
                    com->hizqu->elemento=c;
                    com->hizqu->padre=com;
                    poner=true;
                }
                else {
                    com=com->hizqu;
                }
            }
        }
    }
}

我认为问题出在else:

else{
    com=com->hizqu; //com=com->hder;
}

因为我在调试器中看到程序在section中多次进入，不应该。

Answer 1

根据这段代码:

laraiz->padre=laraiz->hizqu=laraiz->hder=0;

您没有在 celdaArbol 类的构造函数中正确地将指针 hizqu 和 hder 初始化为 nullptr。而且您没有在 if(c>com->elemento){ 的任何一个分支中初始化它们，因此它们似乎具有垃圾值。

如果您使用正确的 C++ 结构，您的代码也可以变得更易读并且更不容易出错:

    celdaArbol *com=laraiz;
    while( true ){
        celdaArbol *&ptr = c > com->elemento ? com->hder : com->hizqu;
        if( ptr  ) {
            com = ptr;
            continue;
        }
        ptr = new celdaArbol;
        ptr->elemento=c;
        ptr->padre=com;
        ptr->hder = ptr->hizqu = nullptr;
        break;
    }

此代码在逻辑上与您的相同，只是更短、更易于阅读、避免重复并修复了您的错误。