訪問BST子節點時出現分段錯誤。爲什麼？

Question

在功能tdeleteLeft（X）發生分段錯誤，當我嘗試訪問（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

一件事中，局部變量的root在BST::BST(int)

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日的構件下面的聲明同名。相應地，tree->root的main在調用構造函數之後仍然未初始化。 因此，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){ 
    ... 
}