在 C++ 中使用添加和删除节点函数实现模板二叉搜索树

Question

我创建了一个带有函数的 bst class，但现在我希望它可以使用模板。到目前为止，这是我添加节点的代码，但它不起作用。

 template <typename T>
void Tree<T>::addNode(Node<T>*& movingPtr, T newItem)
{
    if (movingPtr == NULL)
    {
        movingPtr = new Node;
        movingPtr -> data = newItem;
        movingPtr -> prev = NULL;
        movingPtr -> next = NULL;
    }
    else
    {
        if (movingPtr -> data > newItem)
            addNode(movingPtr -> prev, newItem);
        else
            addNode(movingPtr -> next, newItem);
    }
}

如果有人知道我在哪里可以找到已实现的模板 class，请告诉我。我犯了什么错误？我知道模板的基础知识，但是关于更高级的模板使用的信息很少，这些信息清楚地解释了如何实现模板 classes 和函数。

Answer 1

(1)节点应该是模板

template <typename T>
struct Node
{
    T data;
    Node *prev;
    Node *next;
};

(2)class 应该是模板 class

template <typename T>
class Tree{
public:
    void addNode(Node<T>*& movingPtr, T newItem);
};

(3)创建模板类型的节点

movingPtr = new Node<T>;

您可以尝试下面的完整测试代码：

template <typename T>
struct Node
{
    T data;
    Node *prev;
    Node *next;
};

template <typename T>
class Tree{
public:
    void addNode(Node<T>*& movingPtr, T newItem);
};

template <typename T>
void Tree<T>::addNode(Node<T>*& movingPtr, T newItem)
{
    if (movingPtr == NULL)
    {
        movingPtr = new Node<T>;
        movingPtr->data = newItem;
        movingPtr->prev = NULL;
        movingPtr->next = NULL;
    }
    else
    {
        if (movingPtr->data > newItem)
            addNode(movingPtr->prev, newItem);
        else
            addNode(movingPtr->next, newItem);
    }
}


int main()
{
    Node<int> *n1 = new Node<int>();
    n1->data = 2;

    Tree<int> t;
    t.addNode(n1, 1);
    t.addNode(n1, 3);

    return 0;
}

在 C++ 中使用添加和删除节点函数实现模板二叉搜索树

Implementing a template Binary Search Tree with Add and Delete node functions in C++

c++

templates

tree

binary-tree

binary-search-tree