创建二进制搜索树时出现分段错误问题

Question

我开始时提供了所有我认为相关的代码。基本上二进制搜索树已经定义了，我们需要添加一个父节点功能。我已经这样做了，但是我不断收到分段错误。

template <class TKey> 
class bst { 
    private: 
    struct node { 
     node() { key=TKey(); link[0]=link[1]=NULL; parent=NULL; } 
     operator TKey() { return key; } 
     void print(); 

     TKey key; 
     node *link[2]; 
     node *parent; 
    }; 

    public: 
    class iterator { 
    public: 
    private: 
     friend class bst<TKey>; 
     node *p; 
    }; 
    node *prev_node; 
    iterator begin() { } 
    iterator end() { } 

    bst() { Troot=NULL; } 
    ~bst() { clear(Troot); } 

    bool empty() { return Troot==NULL; } 
    void clear() { clear(Troot); Troot=NULL; } 

    void erase(TKey &key); 
    void insert(TKey &key); 

    void print_inorder() { print_inorder(Troot); } 
    void print_bylevel(); 

    private: 
    void clear(node *); 

    node *minmax_key(node *, int); 
    node *erase(node *, TKey &); 
    node *insert(node *, TKey &); 

    void print_inorder(node *); 

    node *Troot; 
}; 

那就是类定义。

template <class TKey> 
void bst<TKey>::insert(TKey &key) 
{ 
    Troot = insert(Troot, key); 
} 

template <class TKey> 
class bst<TKey>::node *bst<TKey>::insert(node *T, TKey &key) 
{ 

     cout << "insert1" << endl; 
    if (T == NULL) { 

     T = new node; 
     T->key = key; 
     if (prev_node != NULL) 
      T->parent = prev_node; 
     cout << T->parent->key; 
    } else if (T->key == key) { 
     cout << "key " << key << " already in tree" << endl; 
    } else { 
     prev_node = T; 
     int dir = T->key < key; 
     T->link[dir] = insert(T->link[dir], key); 
    } 

    return T; 
} 

这些是插入功能。我猜我正在做一些乱七八糟的事情，因为我仍然很生疏，递归。当我运行使用该树的测试程序时，它会输出inser1行，但会发出seg故障。所以我知道这是搞乱了第一次插入。任何帮助？如果您需要查看代码的其余部分，我可以把它放在一起，但它会有很多与我所做的更改无关的东西。

Answer 1

我想的段错误是在这条线

COUT < < T->父 - >键;

如果T> parent为空，那么如果T是新创建的根（即，如果prev_node == NULL），那么您无法访问NULL值的'key'。

注意：请注意，我只删除了您的代码，所以这只是我遇到的第一件事情，可能还有其他错误。

编辑： 你是什么意思，“我还有问题”，你有什么问题？

这可能不是我将如何实施BST插入，但我不能看到任何跳出来说这是错误的。

我将如何实现它，而不是一个全局变量prev_node，我可能会改变，像这样的代码：

template <class TKey> 
void bst<TKey>::insert(TKey &key) 
{ 
    // Note that I have an initial prev_node of NULL 
    Troot = insert(Troot, key, NULL); 
} 

// Note the extra function parameter 
template <class TKey> 
class bst<TKey>::node *bst<TKey>::insert(node *T, TKey &key, node *prev_node) 
{ 

    cout << "insert1" << endl; 
    if (T == NULL) { 

     T = new node; 
     T->key = key; 
     // I have a habit of always using braces, so that it is easier to read. 
     // This would have helped you with your initial problem. 
     if (prev_node != NULL) { 
      T->parent = prev_node; 
     } 
     //cout << T->parent->key; 
    } else if (T->key == key) { 
     cout << "key " << key << " already in tree" << endl; 
    } else { 
     int dir = T->key < key; 
     T->link[dir] = insert(T->link[dir], key, T); // Note diff here 
    } 

    return T; 
} 

除非你使用prev_node别的地方。

但是，这不应该改变怎么插入的作品，除非您的实现：

1. prev_node不为空最初出于某种原因（这将是在连续插入物的情况，除非你是某处将其复位其他）。
2. 事情是当你使用它改变prev_node（认为线程安全）