二进制搜索树插入导致堆栈溢出 C++

Question

我正在尝试将值插入到二叉搜索树中。我有一个 class 表示树的叶子，还有一个 class 表示集合本身。这是树叶的 class：

template <class K, class T>
class BSTLeaf{
public:
    BSTLeaf(const K& k, const T& c);
    K key;
    T data;
    BSTLeaf * left;
    BSTLeaf * right;
    void insert(const K& k, const T& c);
private:
};

这是按预期工作的另一个 class 的插入函数：

template <class K,class T>
void BSTKeyedCollection<K,T>::insert(const K& k, const T& c){
    if(root != NULL){
        cout << "trying to insert " << c << endl;
        root->insert(k,c);
    }
    else{
        cout << "ROOT WAS NULL" << endl;
        root = new BSTLeaf<K,T>(k,c);
        cout << "The root node contains " << c << endl;
    }
}

这是导致溢出的函数：

template <class K, class T>
void BSTLeaf<K,T>::insert(const K& k, const T& c){
    //if the key is less than the node it comes to
    if(k < key){
        if(left == NULL){
            left = new BSTLeaf<K,T>(k,c);
        }
        else
            insert(k,c);
    }
    if(k > key){
        if(right == NULL){
            right = new BSTLeaf<K,T>(k,c);
        }
        else
            insert(k,c);
    }

}

不确定构造函数是否有用，但它是：

template <class K,class T>
BSTLeaf<K,T>::BSTLeaf(const K& k, const T& c){
    key = k;
    data = c;
    left = NULL;
    right = NULL;
};

我们可以假设 K 将始终是 < 和 > 适用的类型，因此这不是问题。该函数将在根部插入一个值，再插入一个值，然后溢出。在此先感谢您的帮助！

Answer 1

您在同一个实例上调用同一个函数，导致堆栈溢出（循环调用同一个函数）。我想你的意思是 left->insert(k,c); 和 right->insert(k,c);.

Answer 2

看来您的问题来自对 insert 的递归调用。你应该在当前叶子的右叶或左叶上调用它：

template <class K, class T>
void BSTLeaf<K,T>::insert(const K& k, const T& c){
    //if the key is less than the node it comes to
    if(k < key){
        if(left == NULL){
            left = new BSTLeaf<K,T>(k,c);
        }
        else
            left->insert(k,c);
    }
    if(k > key){
        if(right == NULL){
            right = new BSTLeaf<K,T>(k,c);
        }
        else
            right->insert(k,c);
    }

}

二进制搜索树插入导致堆栈溢出 C++

Binary Search Tree insert causing a stack overflow C++

c++

binary-tree

binary-search-tree