创建二进制搜索树时出现分段故障问题

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

我认为segfault在这条线上

cout<lt；T->父->键；

如果T->parent为null，也就是说，如果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. 由于某种原因，prevnode最初不为null（连续插入时会出现这种情况，除非您在其他地方重置它）
2. 当你使用prevnode时，它发生了变化（想想线程安全）