我为我的数据结构类编写了一个优先级队列，它使用二叉搜索树。它产生的输出对于某些输入是正确的，而对于其他输入则是错误的。 正确输出:
输入元素数量:5
输入 5 个数字中的第 1 个:1
输入 5 中的第 2 个:2
输入第 3 个(共 5 个):3
输入第 4 个(共 5 个):4
输入第 5 个(共 5 个):5
输出第 1 个(共 5 个):5
输出 5 中的第 2 个:4
输出第 3 个(共 5 个):3
输出第 4 个(共 5 个):2
输出第 5 个，共 5 个:1
按任意键继续。 。 .
输出不正确
输入元素数量:5
输入第 1 个(共 5 个):-56
输入 5 中的第 2 个:4
输入第 3 个(共 5 个):56
输入第 4 个(共 5 个):21
输入第 5 个(共 5 个):32
输出第 1 个(共 5 个):56
输出 5 中的第 2 个:4
输出第 3 个(共 5 个):-56
输出第 4 个(共 5 个):-56
输出第 5 个(共 5 个):-56
按任意键继续。 。 .
测试.cpp
#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声明
//#ifndef CTREE_H
//#define CTREE_H
//using namespace std;
struct TreeNode
{
int info;
TreeNode* leftLink;
TreeNode* rightLink;
};
class CTree
{
public:
CTree();
~CTree();
void Add(int);
void View();
bool IsEmpty();
int DeleteLargest(TreeNode*);
TreeNode *tree;
private:
void AddItem( TreeNode*&, TreeNode*);
void DisplayTree(TreeNode*);
void Retrieve(TreeNode*&, TreeNode*,bool&);
void Destroy(TreeNode*&);
};
//#endif
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::DeleteLargest(TreeNode* tr)
{
int largest = tr->info;
TreeNode* prev = NULL;
while (tr->rightLink != NULL)
{
prev = tr;
tr = tr->rightLink;
largest = tr->info;
}
if (prev != NULL && prev->rightLink != NULL)
{
delete prev->rightLink;
prev->rightLink = NULL;
}
return largest;
}
//
//int CTree::DeleteLargest(TreeNode* tr)
//{
// int largest = 0;
// TreeNode* prev = NULL;
//
//
// while (tr->rightLink != NULL)
// {
// prev = tr;
// tr = tr->rightLink;
// largest = tr->info;
// }
//
// prev->rightLink = NULL;
//
// return largest;
//}
/*
if (tr == NULL)
{
cout << "The tree is empty"<<endl;
}
else if (tr->rightLink == NULL)
{
largest = tr->info;
prev->rightLink = NULL;
}
else
{
prev = tr;
tr = tr->rightLink;
largest = DeleteLargest(tr);
}
*/
PQ声明
//#include <iostream>
//using namespace std;
//#include "SortedLinkedList.h"
#ifndef PRIORITYQUEUESLL__H
#define PRIORITYQUEUESLL__H
class PriorityQueueBST
{
public:
PriorityQueueBST();
~PriorityQueueBST();
void Enqueue(int);
int Dequeue();
bool IsEmpty();
private:
CTree* ourTree;
//sslNode* head;
};
#endif
PQ 实现
#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()
{
//check for empty??
return ourTree->DeleteLargest(ourTree->tree);
}
bool PriorityQueueBST::IsEmpty()
{
return ourTree->IsEmpty();
}
最佳答案
在DeleteLargest中，考虑如果树看起来像这样会发生什么
4
/ \
/ \
2 7
/ \ /
1 3 5
与
int CTree::DeleteLargest(TreeNode* tr)
{
int largest = tr->info;
TreeNode* prev = NULL;
while (tr->rightLink != NULL)
{
prev = tr;
tr = tr->rightLink;
largest = tr->info;
}
if (prev != NULL && prev->rightLink != NULL)
{
delete prev->rightLink;
prev->rightLink = NULL;
}
return largest;
}
你找到了 7，但是把 5 从树上砍下来，那么它就丢失了。而当根节点的右子树被完全删除后，tr->rightLink从一开始就是NULL，所以prev仍然是 >NULL 并且没有删除任何内容。
对于第一种情况，在删除 tr 之前，您必须将 tr 的左子节点移植到 prev 的右子节点。第二种情况有点复杂。由于您无法在不更改函数签名的情况下更改包含的CTree，因此您无法删除传入的根节点。您必须通过复制其左子节点的值来伪造它，重新链接的子级，并删除原来的左子级。
¹ 嗯，当然还有其他可用的方法，但我能想到的只是复制 info 并删除不同的节点。
关于c++ - 利用 BST 的优先级队列 - 有趣的输出，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/12432632/