访问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++){
    ...

阴影相同名称的成员。相应地，在调用构造函数之后，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){
   ...
}