c++ - 二叉搜索树 : Issue with Insert Function

Question

我一直在研究如何创建二叉搜索树，但在尝试创建自己的树时遇到了问题。我必须使用以下私有(private)结构来创建树。我看过的每个示例都使用指向结构的左指针和右指针，我必须使用指向模板类的左指针和右指针。我一直在试图弄清楚如何编写用于将新节点添加到我的树中的插入函数，但由于这两个指针的设置方式，我一直遇到问题。有没有人知道如何让它与下面的这两个指针一起工作？

private:
struct BinaryNode
{
    Comparable element;
    BinarySearchTree<Comparable> *left;
    BinarySearchTree<Comparable> *right;
};
 BinaryNode *root;
};

这是我的构造函数

BinarySearchTree<Comparable>::BinarySearchTree() {
BinaryNode *temp;
temp = new BinaryNode;

temp->left= NULL;
temp->right= NULL;

root = temp;
}

Answer 1

尝试以下操作:

public:
    template <typename Comparable>
    void insert(const Comparable& key)
    {
        root = insert(root, key);
    }

private:
    template <typename Comparable>
    BinaryNode* insert(BinaryNode*& current_node, const Comparable& key)
    {
        if (current_node == nullptr)
        {
            // Create a leaf node and return it, thus attaching
            // it to the node we last called the function with

            return new BinaryNode{key, nullptr, nullptr};
        }

        if (key == current_node->element)
            // duplicate element, take some action
        else if (key < current_node->element)
            current_node->left = insert(current_node->left, key);
        else
            current_node->right = insert(current_node->right, key);

        return current_node;
    }