我使用 BST 实现了优先级队列。它的输出不正确。
输出：
输入元素数：9 输入第 1 个，共 9 个：8 输入第 2 个，共 9 个：10 输入第 3 个，共 9 个：14 输入 9 中的第 4 号：13 输入第 5 个，共 9 个：3 输入第 6 个，共 9 个：6 输入第 7 个，共 9 个：7 输入第 8 个，共 9 个：4 输入第 9 个，共 9 个：1 输出 9 个中的第 1 个：14 输出第 2 个，共 9 个：13 输出第 3 个，共 9 个：10 输出第 4 个，共 9 个：3 输出 9 个中的第 5 个：3 输出第 6 个，共 9 个：3 输出 9 个中的第 7 个：3 输出第 8 个，共 9 个：3 输出第 9 个，共 9 个：3 按任意键继续 。. .
测试.cpp
//Arkadiy Vasilkovskiy 832a1
#include <iostream>
#include "CTree.h"
#include "PriorityQueueBST.h"
using namespace std;
int main()
{
int num, input, output;
cout << "Enter number of elements: ";
cin >> num;
PriorityQueueBST p;
for (int x = 0; x < num; x++)
{
cout << "Enter number " << x + 1
<< " of " << num << ": ";
cin >> input;
p.Enqueue(input);
}
for (int y = 0; y < num; y++)
{
cout << "Outputting number " << y + 1
<< " of " << num << ": ";
if(p.IsEmpty())
{
break; //we are done (this is an error!)
}
output = p.Dequeue();
cout << output << endl;
}
system("pause");
return 0;
//CTree* tr = new CTree();
//
//for (int i = 0; i < 3; i++)
// tr->Add();
//tr->View();
//system("pause");
//return 0;
}
BST 声明文件
struct TreeNode
{
int info;
TreeNode* leftLink;
TreeNode* rightLink;
};
class CTree
{
public:
CTree();
~CTree();
void Add(int);
void View();
bool IsEmpty();
int popLargest(TreeNode*);
TreeNode *tree;
private:
void AddItem( TreeNode*&, TreeNode*);
void DisplayTree(TreeNode*);
void Retrieve(TreeNode*&, TreeNode*,bool&);
void Destroy(TreeNode*&);
};
BST 实施文件
#include <iostream>
#include <string>
using namespace std;
#include "CTree.h"
CTree::CTree()
{
tree = NULL;
}
CTree::~CTree()
{
Destroy(tree);
}
void CTree::Destroy(TreeNode*& tree)
{
if (tree != NULL)
{
Destroy(tree->leftLink);
Destroy(tree->rightLink);
delete tree;
}
}
bool CTree::IsEmpty()
{
if(tree == NULL)
{
return true;
}
else
{
return false;
}
}
void CTree::Add(int dataToEnter)
{
TreeNode* newPerson = new TreeNode();
/*cout << "Enter the person's name: ";
std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
cin.getline(newPerson->name, 20);*/
//cout << "Enter the person's contribution: ";
//cin >> newPerson->info;
/*bool found = false;*/
newPerson->info = dataToEnter;
newPerson->leftLink = NULL;
newPerson->rightLink = NULL;
/*Retrieve(tree, newPerson, found);
if (found)
cout << "info allready entered\n";
else*/
AddItem(tree, newPerson);
}
void CTree::View()
{
if (IsEmpty())
{
cout<<"The list is empy";
}
else
{
DisplayTree(tree);
}
};
void CTree::AddItem( TreeNode*& ptr, TreeNode* newPer )
{
if (ptr == NULL)
{
ptr = newPer;
}
else if ( newPer->info < ptr->info)
AddItem(ptr->leftLink, newPer);
else
AddItem(ptr->rightLink, newPer);
}
void CTree::DisplayTree(TreeNode* ptr)
{
if (ptr == NULL)
return;
DisplayTree(ptr->rightLink);
cout << ptr->info << endl; //cout<<ptr->name<<" "<<"$"<<ptr->info <<endl;
DisplayTree(ptr->leftLink);
}
void CTree::Retrieve(TreeNode*& ptr, TreeNode* newPer, bool& found)
{
{
if (ptr == NULL)
{
found = false; // item is not found.
}
else if ( newPer->info < ptr->info)
{
Retrieve(ptr->leftLink, newPer, found);
}
// Search left subtree.
else if (newPer->info > ptr->info)
{
Retrieve(ptr->rightLink, newPer, found);// Search right subtree.
}
else
{
//newPer.info = ptr->info; // item is found.
found = true;
}
}
}
int CTree::popLargest(TreeNode* tr)
{
//Failed Attempt at returning one value at a time and deleting that node
int largest; // = tr->info;
TreeNode* prev = NULL;
TreeNode* cur = tr;
if(tr != NULL)
largest = tr->info;
while (cur->rightLink != NULL)
{
prev = cur;
cur = cur->rightLink;
largest = cur->info;
//DeleteAttemptTwo(tr, largest);//DeleteItem(largest);
}
/*if (prev != NULL)
{
prev->rightLink = cur->leftLink;
}*/
if(prev != NULL)
{
if (cur->leftLink != NULL)
{
prev->rightLink = cur->leftLink;
}
else
{
prev->rightLink = NULL;
}
}
else if (cur->leftLink != NULL)
{
largest = cur->leftLink->info;
}
return largest;
}
优先队列声明文件
#ifndef PRIORITYQUEUESLL__H
#define PRIORITYQUEUESLL__H
class PriorityQueueBST
{
public:
PriorityQueueBST();
~PriorityQueueBST();
void Enqueue(int);
int Dequeue();
bool IsEmpty();
private:
CTree* ourTree;
};
#endif
优先队列实现文件
#include <iostream>
using namespace std;
#include "CTree.h"
#include "PriorityQueueBST.h"
PriorityQueueBST::PriorityQueueBST()
{
ourTree = new CTree();
//head = NULL;
}
PriorityQueueBST::~PriorityQueueBST()
{
}
void PriorityQueueBST::Enqueue(int dataToEnter)
{
ourTree->Add(dataToEnter);
}
int PriorityQueueBST::Dequeue()
{
int largest = ourTree->popLargest(ourTree->tree);
return largest;
}
bool PriorityQueueBST::IsEmpty()
{
return ourTree->IsEmpty();
}