c++ - 访问 BST 子节点时出现段错误。为什么？

Question

当我尝试访问下面定义中的 (x->left) 时，函数 tdeleteLeft(x) 发生段错误:

void BST::tdeleteLeft(Node* x){
    if (x->left == NULL){
        tdelete(x);
        }
        else{
        Node* y;
        y = max(x->left);
        tdelete(x->left);
        x = y;}
}

这是完整的程序:

#include <iostream>
#include <ctime>  
#include <cstdlib>
#include <iostream>

using namespace std;


class BST {
    public:
    typedef struct node {
              int value;         
              struct node *left;  
              struct node *right; 

              node() {
                left = NULL;
                right = NULL;
                }
       }Node;

    Node *root;
    Node* i;
    Node* y;
    int z;
    static int c;


    int count();
    void inc();
    BST(int n);
    void tdelete(Node* x);
    Node* max(Node* x);
    void remove_node(Node* x);
    Node* min(Node* x);
    void tdeleteLeft(Node* x);
    void insert(Node* tree, int val);

};




int main ()
{  
  // create BST tree with n nodes
  BST *tree = new BST(10);

  clock_t t;
  t = clock();
  tree->remove_node(tree->root);
  t = clock() - t;
  cout << t << " clicks " <<  ((float)t)/CLOCKS_PER_SEC << "seconds).\n" << endl;

  return 0;
}




BST::BST(int n){
    c = 1;
    z = 0;
    Node *root = NULL;
    for (int i=0; i<n; i++){
        int rando = rand() % 10;
        insert(root, rando);
        }
    cout << "created " << n << "-node BST" << endl; 
}

int BST::c;

int BST::count(){
    return c;
    }

void BST::inc(){
    c++;
    }


BST::Node* BST::max(Node* x){
    if (x->right == NULL){
        return x;
        }
    else
        return max(x->right);   
    }

BST::Node* BST::min(Node* x){
    Node* i = x;
    while (i->left !=NULL){
        i = i->left;
        }
    return i    ;
    }


void BST::tdelete(Node* x){
    if (x->right!=NULL){
        tdelete(x->right);
        }
    if  (x->left!=NULL){
        tdelete(x->left);
        }
    delete(x);
    }

void BST::tdeleteLeft(Node* x){
    if (x->left == NULL){
        tdelete(x);
        }
        else{
        Node* y;
        y = max(x->left);
        tdelete(x->left);
        x = y;}
}

void BST::remove_node(Node* x){
    tdeleteLeft(x);
}



void BST::insert(Node *tree, int val){

               if(tree==NULL){
                    BST::Node* tree = new BST::Node();
                    tree->left = NULL;
                    tree->right = NULL;
                    tree->value = val;
                    c++;
                    }
               else{
                    if(c%2==0){
                        insert(tree->left, val);}
                    else
                    insert(tree->right, val);}

}

Answer 1

一方面，BST::BST(int)

中局部变量 root 的以下声明

BST::BST(int n){
    c = 1;
    z = 0;
    Node *root = NULL;  // <--- This defines a local variable which shadows BST::root
    for (int i=0; i<n; i++){
    ...

shadows同名成员。相应地，main 中的tree->root 在调用构造函数后保持未初始化状态。结果 tree->remove_node(tree->root) 尝试删除未初始化指针的“左”节点，这导致您观察到的段错误。要解决该问题，您需要删除 root 变量的局部声明:

BST::BST(int n){
    c = 1;
    z = 0;
    for (int i=0; i<n; i++){
    ...

那么你应该注意到 insert(root, rando) 不会更新调用者上下文中的 root 变量，因为指针是按值传递的，所以分配的树节点变得不可访问。为防止这种情况，您可以返回更新后的根节点:

Node* BST::insert(Node* tree, int val){

    if(tree==NULL){
        tree = new BST::Node(); // careful about shadowing the "tree" argument
        ...
    }
    else{
        if(c%2==0){
            tree->left  = insert(tree->left, val);
        }
        else{
            tree->right = insert(tree->right, val);
        }
    }
    return tree;
}

你可以像这样在构造函数中调用它:

BST::BST(int n){
    c = 1;
    z = 0;
    for (int i=0; i<n; i++){
        int rando = rand() % 10;
        root = insert(root, rando);
    }
}

或者通过引用传递指针:

void BST::insert(Node*& tree, int val){
   ...
}