우선 순위 큐로 템플릿의 이진 트리 사용

Question

그래서 이진 트리를 만드는 코드를 만들고 싶습니다. 예를 들어 ints가 1,6,2,10,8와 같은 데이터를 보유하고 있고 팝업에서 가장 큰 값을 얻습니다. 번호, 그리고 그 후에 나무에서 삭제되면, 그리고 푸시에 나는 새로운 요소를 삽입 할 수 있습니다. 그리고 이것은 템플릿에 있어야하므로 트리에서 유지하고자하는 데이터 유형을 쉽게 변경할 수 있습니다. 이제는 템플릿을 사용하지 않고 템플릿을 사용하여 항목을 추가하고 인쇄 할 수 있지만 템플리트에 넣으려고하면 다음 오류가 발생합니다. 클래스 템플리트 사용에는 템플리트가 필요합니다. 인수 목록. 무엇이 문제 일 수 있습니까? 어쩌면 나는 그것을 완전히 잘못하고있다. 어떤 제안이라도 환영합니다.

이것은 avakar ty가 고쳐 준 첫 번째 질문이었습니다. (내 질문의 끝 부분에 코드를 게시 할 것입니다)

그냥 물마루 프로젝트 요청을 읽고, 그 같은, 내가 질문을 첫 번째 부분에서 설명한이 위의 만들 필요가 있지만 그 바이너리처럼 트리는 우선 순위 대기열을 나타내야합니다. 그래서 요청에서 우선 순위에 따라 트리에 새 요소를 넣고 팝업을 사용하여 우선 순위가 가장 높은 요소를 가져온 다음 요소를 삭제해야합니다. 그럼 어떻게 우선 순위 대기열로 내 나무를 사용할 수 있습니까, 아니면 이미 하나입니까 (나는 생각하지만 누가 알았지?)? 내가 설명 할 수 있었으면 좋겠어.

#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는 BST 대신에 보통 heaps라고 말했습니다.

개인적으로 알고있는 가장 단순한 힙 구현은 binary heap입니다. 이진 힙은 이론적으로 이진 트리 유형이지만 저장되지는 ​​않습니다. 따라서 BST를 구현해야하는지 또는 이진 트리 만 구현해야하는지에 따라 요구 사항에 맞을 수도 있습니다.

Answer 2

이 줄에 : 당신은 또한 당신이 과제의 오른쪽에 인스턴스화 할 템플릿의 유형을 지정해야

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

그리고 여기가 약속대로 코드입니다 :

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

BinaryTree이 BinaryTree<int>되지 않기 때문에; 하나는 템플리트 이름 (BinaryTree)이고 다른 하나는 해당 템플리트의 특정 유형 이름 (BinaryTree<int>)입니다. 일반 템플릿의 인스턴스는 만들 수 없으며 항상 사용하려는 템플릿 유형을 지정해야합니다.