使用二叉树的模板作为优先级队列

Question

所以，我想打一个代码，创建一个二叉树，保存数据，例如整数像1,6,2,10,8和流行音乐我得到的最大数字，然后它从树中删除，并推我可以插入一个新的元素。这应该是在模板中，所以我可以很容易地改变我想要保存在树中的数据类型。现在我到目前为止，没有模板它是工作好思想，我可以添加项目，我可以打印它们，但是当我尝试把它放在模板中，我得到以下错误：使用类模板需要模板参数列表。可能是什么问题呢？也许我这样做完全错了。欢迎任何建议。

这是我的第一个问题就得到了由avakar TY固定。 （我会在我的问题结束后张贴代码）

我刚刚读了槽的项目请求，和它一样，我不得不让这个东西我在上面描述的问题的第一部分，但它像二进制树应该代表一个优先级队列。这就是为什么在写请求时，我必须使用push按优先级顺序在树中放置一个新元素，并使用弹出窗口，我将获得具有最高优先级的元素，然后该元素将被删除。那么我怎样才能将我的树用作优先队列呢，还是他已经是一个（我认为不是但是谁知道）？我希望我能解释它。

这里是如许的代码：

#include <iostream> 


using namespace std; 


template<class T> 
class BinaryTree 
{ 
struct Node 
    { 
     T data; 
     Node* lChildptr; 
     Node* rChildptr; 

     Node(T dataNew) 
     { 
      data = dataNew; 
      lChildptr = NULL; 
      rChildptr = NULL; 
     } 
    }; 
private: 
    Node* root; 

     void Insert(T newData, Node* &theRoot) 
     { 
      if(theRoot == NULL) 
      { 
       theRoot = new Node(newData); 
       return; 
      } 

      if(newData < theRoot->data) 
       Insert(newData, theRoot->lChildptr); 
      else 
       Insert(newData, theRoot->rChildptr);; 
     } 

     void PrintTree(Node* theRoot) 
     { 
      if(theRoot != NULL) 
      { 
       PrintTree(theRoot->lChildptr); 
       cout<< theRoot->data<<" ";; 
       PrintTree(theRoot->rChildptr); 
      } 
     } 

    public: 
     BinaryTree() 
     { 
      root = NULL; 
     } 

     void AddItem(T newData) 
     { 
      Insert(newData, root); 
     } 

     void PrintTree() 
     { 
      PrintTree(root); 
     } 
    }; 

    int main() 
    { 
     BinaryTree<int> *myBT = new BinaryTree<int>(); 
     myBT->AddItem(1); 
     myBT->AddItem(7); 
     myBT->AddItem(1); 
     myBT->AddItem(10); 
     myBT->AddItem(4); 
     myBT->PrintTree(); 
    } 

Answer 1

如果你想使用二叉树作为优先级队列，您只能通过右子指针步进提取最大元素。任何留下的孩子都会比当前元素小。因此，您记录该节点的值，然后将其删除 - 您仍然必须编写节点删除例程。

用一个简单的BST的问题是，它可以变得不平衡，并发送你的复杂性为O（n）。您可以使用自平衡BST，但对于优先级队列来说是不常见的。正如Kerrek所说，他们通常是heaps，而不是BST。

最简单的堆实现，我个人知道的是binary heap。二进制堆在理论上是一种二叉树，虽然没有像这样存储。所以，根据你是否必须实现一个BST或者只是一个二叉树，它可能符合你的要求。

Answer 2

在此行中：

BinaryTree<int> *myBT = new BinaryTree(); 

您还需要指定要实例化的赋值右侧的模板类型：

BinaryTree<int> *myBT = new BinaryTree<int>(); 

因为BinaryTree不是BinaryTree<int>;一个是模板的名称（BinaryTree），另一个是该模板的特定类型的名称（BinaryTree<int>）。你不能创建普通模板的实例，你必须给它一个你想要使用的模板的类型。