c++ - 在模板中传递参数

Question

我正在实现一个红黑树，其中插入函数应该有两个模板，一个用于项目，另一个用于键。我以这种方式在插入函数中传递参数:

template <class Item, class Key>
void RedBlackTreeNode<Item, Key>::InsertKey(const Item *&T, const Key *&z)

我试图在第二个参数中传递一个数组(由随机元素组成)，这样:

const int* pointer = &arr[i];
t1.InsertKey(//something else here// , pointer); //insert the tree and the node

但是，为了在红黑树中插入元素，我不知道要传递什么作为第一个参数。第一个参数代表什么？我试图通过这种方式传递树的根:

Node<int, int> n1;
t1.InsertKey(n1->root, pointer);

不幸的是，这不起作用。有什么帮助吗？

提前致谢。

Answer 1

如果你正在实现一个红黑树(或者甚至只是一个二叉树)，你的插入方法只是将要插入的元素作为参数。您要插入一个 Item可以与另一个项目进行比较，没有 Key 的概念.如果你想创建 Key/Value容器，你可以拿一个std::pair<Key, Value>项目并比较 item.first ，或类似的东西。

这是 binary search tree 的代码模型插入。您可以从它开始添加必须为[红黑树插入(http://en.wikipedia.org/wiki/Red%E2%80%93black_tree#Insertion)保留的属性:

template <class Item>
void BinarySearchTreeNode<Item>::Insert(Item item)
{
   if (item < this->item)
   {
     if (this->leftChild == nullptr)
        this->leftChild = new BinarySearchTreeNode(item);
     else
        insert(this->leftChild, item);
   } 
   else 
   {
     if (this->rightChild == nullptr)
        this->rightChild = new BinarySearchTreeNode(item);
     else
        insert(this->rightChild, item);
   }
}

这里是一个示例用法(假设其余的实现已经完成):

BinarySearchTree<int> tree;


tree.Insert(1); // Call insert on root node