高度平衡树代码中的分段错误

Question

当我尝试这样做时：

int main(){

    node * root;

    insert(&root, 10);
    insert(&root, 20);
    insert(&root, 30);
    insert(&root, 40);
    insert(&root, 50);
    insert(&root,60);

    preorder(root);

return 0;
}

我的代码运行良好并给出了输出。

但是当我这样做时：

int main(){

    node * root;

    insert(&root, 10);
    insert(&root, 20);
    insert(&root, 30);
    insert(&root, 40);
    insert(&root, 50);
    insert(&root,60);

    preorder(root);

    node * t;

    insert(&t,9);
    insert(&t,15);
    insert(&t,18);
    insert(&t,33);
    insert(&t,55);
    insert(&t,44);
    insert(&t,61);

return 0;
}

它给出了一个分段错误...

此外，如果我评论：

preorder(root);

代码运行良好..

如果我最后对节点 t 进行了预订，它就可以正常工作... 不知道当我尝试在 t 之前打印 root 的预序时我是如何得到这个分段错误的？

插入代码段：

void insert(node ** root, int d){
    node * t= *root;

    *root=_insert(t,d);
}

node * _insert(node * t, int d){
    if(t==NULL)
        return newNode(d);
    else{

        if(d < t->data)
            t->left=_insert(t->left,d);

        if(d > t->data)
            t->right=_insert(t->right,d);

        t->height= max(ht(t->left),ht(t->right))+1;

        int bal= ht(t->left)-ht(t->right);

        if(bal > 1 && d < t->data)
            return rightRotate(t);

        if(bal < -1 && d > t->data)
            return leftRotate(t);

        if(bal < -1  && d > t->data){
            t->right=rightRotate(t->right);
            return leftRotate(t);
        }   

        if(bal >1 && d < t->data){
            t->left=leftRotate(t->left);
            return rightRotate(t);
        }

        return t;
    }
}

预购代码段：

void preorder(node * t){
    if(t==NULL)
        return;

    else {
        cout<<t->data<<" ";
        preorder(t->left);
        preorder(t->right);
    }
}

代码和节点结构中使用的辅助函数：

struct node{
    int data;
    node * left;
    node * right;
    int height;
};


node * newNode(int d){
    node * t;
    t= new node;
    t->data = d;
    t->left=NULL;
    t->right=NULL;
    t->height=1;
    return t;
}


int ht(node * t){
    if(t==NULL)
        return 0;
    else
        return t->height;
}

node * leftRotate(node * t){
    node * y = t->right;
    t->right= y->left;
    y->left=t;

    return y;
}


node * rightRotate(node * t){
    node * y = t->left;
    t->left= y->right;
    y->right=t;

    return y;
}

Answer 1

你的代码中有undefined behavior，因为局部变量没有初始化，它们的值是不确定的。

您需要先初始化变量，然后再尝试使用它们，例如

node* root = nullptr;  // or `0` or `NULL`

高度平衡树代码中的分段错误

segmentation fault in height balance tree code

c++

segmentation-fault

avl-tree