#c #binary-search-tree #priority-queue
Вопрос:
Включил все файлы, которые я получил на всякий случай, но двоичное дерево поиска.h находится в конце. Я знаю, что приоритетная очередь нуждается в очереди (), для которой требуется int для приоритета, функция dequeue (), которая удалит верхние данные, функция peek() покажет данные, которые были первыми (способом FIFO), но как реализовать приоритетную очередь с использованием этого BinarySearchADT? Я не жду полного ответа, но, по крайней мере, укажи мне правильное направление.
Редактировать: Добавлен ADT Prio_Queue, который использует двоичный файл.h в конце. Все еще немного невежествен.
#pragma once
#ifndef _BINARY_TREE_INTERFACE
#define _BINARY_TREE_INTERFACE
#include "NotFoundException.h"
template< class ItemType>
class BinaryTreeInterface
{
public:
virtual bool isEmpty() const = 0;
virtual int getHeight() const = 0;
virtual int getNumberOfNodes() const = 0;
virtual ItemType getRootData() const = 0;
virtual void setRootData(const ItemTypeamp; newData) = 0;
virtual bool add(const ItemType amp; newData) = 0;
virtual bool remove(const ItemType amp; data) = 0;
virtual void clear() = 0;
virtual ItemType getEntry(const ItemType amp; anEntry) const throw(NotFoundException) = 0;
virtual bool contains(const ItemType amp; anEntry) const = 0;
virtual void preorderTraverse(void visit(ItemTypeamp;)) const = 0;
virtual void inorderTraverse(void visit(ItemTypeamp;)) const = 0;
virtual void postorderTraverse(void visit(ItemTypeamp;)) const = 0;
};
#endif
#pragma once
#ifndef _BINARY_NODE
#define _BINARY_NODE
template< class ItemType>
class BinaryNode
{
private:
ItemType item;
BinaryNode<ItemType>* leftChildPtr;
BinaryNode<ItemType>* rightChildPtr;
public:
BinaryNode();
BinaryNode(const ItemTypeamp; anItem);
BinaryNode(const ItemTypeamp; anItem,
BinaryNode<ItemType>* leftPtr,
BinaryNode<ItemType>* rightPtr);
void setItem(const ItemTypeamp; anItem);
ItemType getItem() const;
ItemType getCon() const;
bool isLeaf() const;
BinaryNode<ItemType>* getLeftChildPtr() const;
BinaryNode<ItemType>* getRightChildPtr() const;
void setLeftChildPtr(BinaryNode<ItemType>* leftPtr);
void setRightChildPtr(BinaryNode<ItemType>* rightPtr);
};
#endif
template<class ItemType>
BinaryNode<ItemType>::BinaryNode():item(nullptr), leftChildPtr(nullptr), rightChildPtr(nullptr)
{
}
template<class ItemType>
BinaryNode<ItemType>::BinaryNode(const ItemTypeamp; anItem) :item(NULL), leftChildPtr(nullptr), rightChildPtr(nullptr)
{
}
template<class ItemType>
BinaryNode<ItemType>::BinaryNode(const ItemTypeamp; anItem, BinaryNode* leftPtr, BinaryNode* rightPtr) :item(anItem), leftChildPtr(nullptr), rightChildPtr(nullptr)
{
}
template<class ItemType>
void BinaryNode<ItemType>::setItem(const ItemTypeamp; anItem)
{
item = anItem;
}
template<class ItemType>
ItemType BinaryNode<ItemType>::getItem() const
{
return item;
}
template<class ItemType>
ItemType BinaryNode<ItemType>::getCon() const
{
return con;
}
template<class ItemType>
bool BinaryNode<ItemType>::isLeaf() const
{
return ((leftChildPtr == nullptr) amp;amp; (rightChildPtr == nullptr));
}
template<class ItemType>
void BinaryNode<ItemType>::setLeftChildPtr(BinaryNode* leftPtr)
{
leftChildPtr = leftPtr;
}
template<class ItemType>
void BinaryNode<ItemType>::setRightChildPtr(BinaryNode* rightPtr)
{
rightChildPtr = rightPtr;
}
template<class ItemType>
BinaryNode<ItemType>* BinaryNode<ItemType>::getLeftChildPtr() const
{
return leftChildPtr;
}
template<class ItemType>
BinaryNode<ItemType>* BinaryNode<ItemType>::getRightChildPtr() const
{
return rightChildPtr;
}
#pragma once
#ifndef _BINARY_NODE_TREE
#define _BINARY_NODE_TREE
#include "BinaryTreeInterface.h"
#include "BinaryNode.h"
#include "PrecondViolatedExcep.h"
#include "NotFoundException.h"
template< class ItemType>
class BinaryNodeTree : public BinaryTreeInterface<ItemType>
{
private:
BinaryNode<ItemType>* rootPtr;
protected:
// Recursive methods
int getHeightHelper(BinaryNode<ItemType>* subTreePtr) const;
int getNumberOfNodesHelper(BinaryNode<ItemType>* subTreePtr) const;
void destroyTree(BinaryNode<ItemType>* subTreePtr);
BinaryNode<ItemType>* balancedAdd(BinaryNode<ItemType>* subTreePtr, BinaryNode<ItemType>* newNodePtr);
BinaryNode<ItemType>* removeValue(BinaryNode<ItemType>* subTreePtr, const ItemType target, boolamp; success);
BinaryNode<ItemType>* moveValuesUpTree(BinaryNode<ItemType>* subTreePtr);
BinaryNode<ItemType>* findNode(BinaryNode<ItemType>* treePtr, const ItemTypeamp; target, boolamp; success) const;
BinaryNode<ItemType>* copyTree(const BinaryNode<ItemType>* treePtr) const;
void preorder(void visit(ItemTypeamp;), BinaryNode<ItemType>* treePtr) const;
void inorder(void visit(ItemTypeamp;), BinaryNode<ItemType>* treePtr) const;
void postorder(void visit(ItemTypeamp;), BinaryNode<ItemType>* treePtr) const;
public:
BinaryNodeTree();
BinaryNodeTree(const ItemTypeamp; rootItem);
BinaryNodeTree(const ItemTypeamp; rootItem, const BinaryNodeTree<ItemType>* leftTreePtr, const BinaryNodeTree<ItemType>* rightTreePtr);
BinaryNodeTree(const BinaryNodeTree<ItemType>amp; tree);
virtual ~BinaryNodeTree();
bool isEmpty() const;
int getHeight() const;
int getNumberOfNodes() const;
ItemType getRootData() const throw(PrecondViolatedExcep);
void setRootData(const ItemTypeamp; newData);
bool add(const ItemTypeamp; newData);
bool remove(const ItemTypeamp; data);
void clear();
ItemType getEntry(const ItemTypeamp; anEntry) const throw(NotFoundException);
bool contains(const ItemTypeamp; anEntry) const;
void preorderTraverse(void visit(ItemTypeamp;)) const;
void inorderTraverse(void visit(ItemTypeamp;)) const;
void postorderTraverse(void visit(ItemTypeamp;)) const;
BinaryNodeTreeamp; operator=(const BinaryNodeTreeamp; rightHandSide);
};
#endif
template<class ItemType>
int BinaryNodeTree<ItemType>::getHeightHelper(BinaryNode<ItemType>* subTreePtr)const
{
if (subTreePtr == nullptr)
return 0;
else
return 1 max(getHeightHelper(subTreePtr->getLeftChildPtr()), getHeightHelper(subTreePtr->getRightChildPtr()));
}
template<class ItemType>
int BinaryNodeTree<ItemType>::getNumberOfNodesHelper(BinaryNode<ItemType>* subTreePtr)const
{
if (subTreePtr == nullptr)
return 0;
else
return 1 getNumberOfNodesHelper(subTreePtr->getLeftChildPtr()) getNumberOfNodesHelper(subTreePtr->getRightChildPtr());
}
template<class ItemType>
BinaryNode<ItemType>* BinaryNodeTree<ItemType>::balancedAdd(BinaryNode<ItemType>* subTreePtr, BinaryNode<ItemType>* newNodePtr)
{
if (subTreePtr == nullptr)
return newNodePtr;
else
{
BinaryNode<ItemType>* leftPtr = subTreePtr->getLeftChildPtr();
BinaryNode<ItemType>* rightPtr = subTreePtr->getRightChildPtr();
if (getHeightHelper(leftPtr) > getHeightHelper(rightPtr))
{
rightPtr = balancedAdd(rightPtr, newNodePtr);
subTreePtr->setRightChildPtr(rightPtr);
}
else
{
leftPtr = balancedAdd(leftPtr, newNodePtr);
subTreePtr->setLeftChildPtr(leftPtr);
}
return subTreePtr;
}
}
template<class ItemType>
BinaryNode<ItemType>* BinaryNodeTree<ItemType>::moveValuesUpTree(BinaryNode<ItemType>* subTreePtr)
{
BinaryNode<ItemType>* leftPtr = subTreePtr->getLeftChildPtr();
BinaryNode<ItemType>* rightPtr = subTreePtr->getRightChildPtr();
int leftHeight = getHeightHelper(leftPtr);
int rightHeight = getHeightHelper(rightPtr);
if (leftHeight > rightHeight)
{
subTreePtr->setItem(leftPtr->getItem());
leftPtr = moveValuesUpTree(leftPtr);
subTreePtr->setLeftChildPtr(leftPtr);
return subTreePtr;
}
else
{
if (rightPtr != nullptr)
{
subTreePtr->setItem(rightPtr->getItem());
rightPtr = moveValuesUpTree(rightPtr);
subTreePtr->setRightChildPtr(rightPtr);
return subTreePtr;
}
else
{
delete subTreePtr;
return nullptr;
}
}
}
template<class ItemType>
BinaryNode<ItemType>* BinaryNodeTree<ItemType>::removeValue(BinaryNode<ItemType>* subTreePtr, const ItemType target, boolamp; success)
{
if (subTreePtr == nullptr)
return nullptr;
if (subTreePtr->getItem() == target)
{
subTreePtr = moveValuesUpTree(subTreePtr);
success = true;
return subTreePtr;
}
else
{
BinaryNode<ItemType>* targetNodePtr = removeValue(subTreePtr->getLeftChildPtr(), target, success);
subTreePtr->setLeftChildPtr(targetNodePtr);
if (!success)
{
targetNodePtr = removeValue(subTreePtr->getRightChildPtr(), target, success);
subTreePtr->setRightChildPtr(targetNodePtr);
}
return subTreePtr;
}
}
template<class ItemType>
BinaryNode<ItemType>* BinaryNodeTree<ItemType>::findNode(BinaryNode<ItemType>* treePtr, const ItemTypeamp; target, boolamp; success) const
{
if (treePtr == nullptr)
return nullptr;
if (treePtr->getItem() == target)
{
success = true;
return treePtr;
}
else
{
BinaryNode<ItemType>* targetNodePtr = findNode(treePtr->getLeftChildPtr(), target, success);
if (!success)
{
targetNodePtr = findNode(treePtr->getRightChildPtr(), target, success);
}
return targetNodePtr;
}
}
template<class ItemType>
BinaryNode<ItemType>* BinaryNodeTree<ItemType>::copyTree(const BinaryNode<ItemType>* treePtr) const
{
BinaryNode* newTreePtr = nullptr;
if (treePtr != nullptr)
{
newTreePtr = new BinaryNode(treePtr->getItem(), nullptr, nullptr);
newTreePtr->setLeftChildPtr(copyTree(treePtr->getLeftChildPtr()));
newTreePtr->setRightChildPtr(copyTree(treePtr->getRightChildPtr()));
}
return newTreePtr;
}
template<class ItemType>
void BinaryNodeTree<ItemType>::destroyTree(BinaryNode<ItemType>* subTreePtr)
{
if (subTreePtr != nullptr)
{
destroyTree(subTreePtr->getLeftChildPtr());
destroyTree(subTreePtr->getRightChildPtr());
delete subTreePtr;
}
}
template<class ItemType>
void BinaryNodeTree<ItemType>::preorder(void visit(ItemTypeamp;), BinaryNode<ItemType>* treePtr) const
{
if (treePtr != nullptr)
{
ItemType theItem = treePtr->getItem();
visit(theItem);
preorder(visit, treePtr->getLeftChildPtr());
preorder(visit, treePtr->getRightChildPtr());
}
}
template<class ItemType>
void BinaryNodeTree<ItemType>::inorder(void visit(ItemTypeamp;), BinaryNode<ItemType>* treePtr) const
{
if (treePtr != nullptr)
{
inorder(visit, treePtr->getLeftChildPtr());
ItemType theItem = treePtr->getItem();
visit(theItem);
inorder(visit, treePtr->getRightChildPtr());
}
}
template<class ItemType>
void BinaryNodeTree<ItemType>::postorder(void visit(ItemTypeamp;), BinaryNode<ItemType>* treePtr) const
{
if (treePtr != nullptr)
{
postorder(visit, treePtr->getLeftChildPtr());
postorder(visit, treePtr->getRightChildPtr());
ItemType theItem = treePtr->getItem();
visit(theItem);
}
}
template<class ItemType>
BinaryNodeTree<ItemType>::BinaryNodeTree() : rootPtr(nullptr)
{
}
template<class ItemType>
BinaryNodeTree<ItemType>::BinaryNodeTree(const ItemTypeamp; rootItem)
{
rootPtr = new BinaryNode(rootItem, nullptr, nullptr);
}
template<class ItemType>
BinaryNodeTree<ItemType>::BinaryNodeTree(const ItemTypeamp; rootItem, const BinaryNodeTree* leftTreePtr, const BinaryNodeTree* rightTreePtr)
{
rootPtr = new BinaryNode(rootItem, copyTree(leftTreePtr->rootPtr), copyTree(rightTreePtr->rootPtr));
}
template<class ItemType>
BinaryNodeTree<ItemType>::BinaryNodeTree(const BinaryNodeTreeamp; treeItem)
{
rootPtr = copyTree(treeItem.rootPtr);
}
template<class ItemType>
BinaryNodeTree<ItemType>::~BinaryNodeTree()
{
destroyTree(rootPtr);
}
template<class ItemType>
bool BinaryNodeTree<ItemType>::isEmpty() const
{
return rootPtr == nullptr;
}
template<class ItemType>
int BinaryNodeTree<ItemType>::getHeight() const
{
return getHeightHelper(rootPtr);
}
template<class ItemType>
int BinaryNodeTree<ItemType>::getNumberOfNodes() const
{
return getNumberOfNodesHelper(rootPtr);
}
template<class ItemType>
void BinaryNodeTree<ItemType>::clear()
{
destroyTree(rootPtr);
rootPtr = nullptr;
}
template<class ItemType>
ItemType BinaryNodeTree<ItemType>::getRootData()const throw (PrecondViolatedExcep)
{
if (isEmpty())
throw PrecondViolatedExcep("getRootData() called with empty tree");
return rootPtr->getItem();
}
//setRootData definition
template<class ItemType>
void BinaryNodeTree<ItemType>::setRootData(const ItemTypeamp; newItem)
{
if (isEmpty())
rootPtr = new BinaryNode<ItemType>(newItem, nullptr, nullptr);
else
rootPtr->setItem(newItem);
}
template<class ItemType>
bool BinaryNodeTree<ItemType>::add(const ItemTypeamp; newData)
{
BinaryNode<ItemType>* newNodePtr = new BinaryNode<ItemType>(newData);
rootPtr = balancedAdd(rootPtr, newNodePtr);
return true;
}
template<class ItemType>
bool BinaryNodeTree<ItemType>::remove(const ItemTypeamp; target)
{
bool isSuccessful = false;
rootPtr = removeValue(rootPtr, target, isSuccessful);
return isSuccessful;
}
template<class ItemType>
ItemType BinaryNodeTree<ItemType>::getEntry(const ItemTypeamp; anEntry) const throw (NotFoundException)
{
bool isSuccessful = false;
BinaryNode<ItemType>* binaryNodePtr = findNode(rootPtr, anEntry, isSuccessful);
if (isSuccessful)
return binaryNodePtr->getItem();
else
throw PrecondViolatedExcep("Entry Not found in tree");
}
template<class ItemType>
bool BinaryNodeTree<ItemType>::contains(const ItemTypeamp; anEntry) const
{
bool isSuccessful = false;
findNode(rootPtr, anEntry, isSuccessful);
return isSuccessful;
}
template<class ItemType>
void BinaryNodeTree<ItemType>::preorderTraverse(void visit(ItemTypeamp;))const
{
preorder(visit, rootPtr);
}
template<class ItemType>
void BinaryNodeTree<ItemType>::inorderTraverse(void visit(ItemTypeamp;))const
{
inorder(visit, rootPtr);
}
template<class ItemType>
void BinaryNodeTree<ItemType>::postorderTraverse(void visit(ItemTypeamp;))const
{
postorder(visit, rootPtr);
}
template<class ItemType>
BinaryNodeTree<ItemType>amp; BinaryNodeTree<ItemType>::operator=(const BinaryNodeTreeamp; rightHandSide)
{
if (!isEmpty())
clear();
this = copyTree(amp;rightHandSide);
return *this;
}
#pragma once
#define _NOT_FOUND_EXCEPTION
using namespace std;
#include "PrecondViolatedExcep.h"
#include <iostream>
#include <string>
#include <stdexcept>
class NotFoundException : public logic_error
{
public:
NotFoundException(const stringamp; message = "");
};
NotFoundException::NotFoundException(const stringamp; message) : logic_error("Precondition Violated Exception: " message)
{
}
#pragma once
#ifndef _PRECOND_VIOLATED_EXCEP
#define _PRECOND_VIOLATED_EXCEP
#include <stdexcept>
#include <string>
using namespace std;
class PrecondViolatedExcep : public logic_error
{
public:
PrecondViolatedExcep(const stringamp; message = "");
};
PrecondViolatedExcep::PrecondViolatedExcep(const string amp; message) :
logic_error("Precondition Violated Exception: " message)
{
}
#endif
#pragma once
#ifndef _BINARY_SEARCH_TREE
#define _BINARY_SEARCH_TREE
#include "BinaryTreeInterface.h"
#include "BinaryNodeTree.h"
#include "NotFoundException.h"
#include "PrecondViolatedExcep.h"
template<class ItemType>
class BinarySearchTree : public BinaryNodeTree<ItemType>
{
private:
BinaryNode<ItemType>* rootPtr;
protected:
//------------------------------------------------------------
// Protected Utility Methods Section:
// Recursive helper methods for the public methods.
//------------------------------------------------------------
// Recursively finds where the given node should be placed and
// inserts it in a leaf at that point.
BinaryNode<ItemType>* insertInorder(BinaryNode<ItemType>* subTreePtr, BinaryNode<ItemType>* newNode);
BinaryNode<ItemType>* removeValue(BinaryNode<ItemType>* subTreePtr,const ItemType target,boolamp; success);
BinaryNode<ItemType>* removeNode(BinaryNode<ItemType>* nodePtr);
BinaryNode<ItemType>* removeLeftmostNode(BinaryNode<ItemType>* subTreePtr, ItemTypeamp; inorderSuccessor);
BinaryNode<ItemType>* findNode(BinaryNode<ItemType>* treePtr, const ItemTypeamp; target) const;
public:
//------------------------------------------------------------
// Constructor and Destructor Section.
//------------------------------------------------------------
BinarySearchTree();
BinarySearchTree(const ItemTypeamp; rootItem);
BinarySearchTree(const BinarySearchTree<ItemType>amp; tree);
virtual ~BinarySearchTree();
//------------------------------------------------------------
// Public Methods Section.
//------------------------------------------------------------
bool isEmpty() const;
int getHeight() const;
int getNumberOfNodes() const;
ItemType getRootData() const throw(PrecondViolatedExcep);
void setRootData(const ItemTypeamp; newData) const throw(PrecondViolatedExcep);
bool add(const ItemTypeamp; newEntry);
bool remove(const ItemTypeamp; anEntry);
void clear();
ItemType getEntry(const ItemTypeamp; anEntry) const throw(NotFoundException);
bool contains(const ItemTypeamp; anEntry) const;
//------------------------------------------------------------
// Public Traversals Section.
//------------------------------------------------------------
void preorderTraverse(void visit(ItemTypeamp;)) const;
void inorderTraverse(void visit(ItemTypeamp;)) const;
void postorderTraverse(void visit(ItemTypeamp;)) const;
//------------------------------------------------------------
// Overloaded Operator Section.
//------------------------------------------------------------
BinarySearchTree<ItemType>amp; operator=(const BinarySearchTree<ItemType>amp;
rightHandSide);
};
#endif
#include <iostream>
template<class ItemType>
BinaryNode<ItemType>*BinarySearchTree<ItemType>::insertInorder(BinaryNode<ItemType>*subTreePtr, BinaryNode<ItemType>*newNodePtr)
{
if (subTreePtr == nullptr)
return newNodePtr;
else
{
if (subTreePtr->getItem() > newNodePtr->getItem())
subTreePtr->setLeftChildPtr(insertInorder(subTreePtr -> getLeftChildPtr(), newNodePtr));
else
subTreePtr->setRightChildPtr(insertInorder(subTreePtr -> getRightChildPtr(), newNodePtr));
return subTreePtr;
}
}
template<class ItemType>
BinaryNode<ItemType>*
BinarySearchTree<ItemType>::removeValue(BinaryNode<ItemType>*subTreePtr,
const ItemType target,
boolamp; success)
{
if (subTreePtr == nullptr)
{
success = false;
return nullptr;
}
if (subTreePtr->getItem() == target)
{
subTreePtr = removeNode(subTreePtr);
success = true;
return subTreePtr;
}
else
{
if (subTreePtr->getItem() > target)
subTreePtr->setLeftChildPtr(removeValue(subTreePtr->getLeftChildPtr(), target, success));
else
subTreePtr->setRightChildPtr(removeValue(subTreePtr->getRightChildPtr(), target, success));
return subTreePtr;
}
}
template<class ItemType>
BinaryNode<ItemType>*
BinarySearchTree<ItemType>::removeNode(BinaryNode<ItemType>* nodePtr)
{
if (nodePtr->isLeaf())
{
delete nodePtr;
return (nodePtr = nullptr);
}
else if (nodePtr->getLeftChildPtr() == nullptr)
{
BinaryNode<ItemType>* nodeToConnectPtr = nodePtr->getRightChildPtr();
delete nodePtr;
nodePtr = nullptr;
return nodeToConnectPtr;
}
else if (nodePtr->getRightChildPtr() == nullptr)
{
BinaryNode<ItemType>* nodeToConnectPtr = nodePtr->getLeftChildPtr();
delete nodePtr;
nodePtr = nullptr;
return nodeToConnectPtr;
}
else
{
ItemType newNodeValue;
nodePtr->setRightChildPtr(removeLeftmostNode(nodePtr-> getRightChildPtr(), newNodeValue));
nodePtr->setItem(newNodeValue);
return nodePtr;
}
}
template<class ItemType>
BinaryNode<ItemType>*
BinarySearchTree<ItemType>::removeLeftmostNode(BinaryNode<ItemType>* nodePtr,
ItemTypeamp; inorderSuccessor)
{
if (nodePtr->getLeftChildPtr() == nullptr)
{
inorderSuccessor = nodePtr->getItem();
return removeNode(nodePtr);
}
else
{
nodePtr->setLeftChildPtr(removeLeftmostNode(nodePtr-> getLeftChildPtr(), inorderSuccessor));
return nodePtr;
}
}
template<class ItemType>
BinaryNode<ItemType>* BinarySearchTree<ItemType>::findNode(BinaryNode<ItemType>*subTreePtr, const ItemTypeamp; target) const
{
if (subTreePtr == nullptr)
return nullptr;
else if (subTreePtr->getItem() == target)
return subTreePtr;
else if (subTreePtr->getItem() > target)
return findNode(subTreePtr->getLeftChildPtr(), target);
else
return findNode(subTreePtr->getRightChildPtr(), target);
}
template<class ItemType>
BinarySearchTree<ItemType>::BinarySearchTree() : rootPtr(nullptr)
{
}
template<class ItemType>
BinarySearchTree<ItemType>::BinarySearchTree(const ItemTypeamp; rootItem)
{
rootPtr = new BinaryNode<ItemType>(rootItem, nullptr, nullptr);
}
template<class ItemType>
BinarySearchTree<ItemType>::BinarySearchTree(const BinarySearchTree<ItemType>amp;
treePtr)
{
rootPtr = this->copyTree(treePtr.rootPtr);
}
template<class ItemType>
BinarySearchTree<ItemType>::~BinarySearchTree()
{
this->destroyTree(rootPtr);
}
template<class ItemType>
bool BinarySearchTree<ItemType>::isEmpty() const
{
return rootPtr == nullptr;
}
template<class ItemType>
int BinarySearchTree<ItemType>::getHeight() const
{
return this->getHeightHelper(rootPtr);
}
template<class ItemType>
int BinarySearchTree<ItemType>::getNumberOfNodes() const
{
return this->getNumberOfNodesHelper(rootPtr);
}
template<class ItemType>
void BinarySearchTree<ItemType>::clear()
{
this->destroyTree(rootPtr);
rootPtr = nullptr;
}
template<class ItemType>
ItemType BinarySearchTree<ItemType>::getRootData() const
throw(PrecondViolatedExcep)
{
if (isEmpty())
throw PrecondViolatedExcep("getRootData() called with empty tree.");
return rootPtr->getItem();
}
template<class ItemType>
bool BinarySearchTree<ItemType>::add(const ItemTypeamp; newData)
{
BinaryNode<ItemType>* newNodePtr = new BinaryNode<ItemType>(newData);
rootPtr = insertInorder(rootPtr, newNodePtr);
return true;
}
template<class ItemType>
bool BinarySearchTree<ItemType>::remove(const ItemTypeamp; target)
{
bool isSuccessful = false;
rootPtr = removeValue(rootPtr, target, isSuccessful);
return isSuccessful;
}
template<class ItemType>
ItemType BinarySearchTree<ItemType>::getEntry(const ItemTypeamp; anEntry) const
throw(NotFoundException)
{
BinaryNode<ItemType>* nodeWithEntry = findNode(rootPtr, anEntry);
if (nodeWithEntry == nullptr)
throw NotFoundException("Entry not found in tree.");
else
return nodeWithEntry->getItem();
}
template<class ItemType>
bool BinarySearchTree<ItemType>::contains(const ItemTypeamp; anEntry) const
{
return findNode(rootPtr, anEntry);
}
template<class ItemType>
void BinarySearchTree<ItemType>::preorderTraverse(void visit(ItemTypeamp;)) const
{
this->preorder(visit, rootPtr);
}
template<class ItemType>
void BinarySearchTree<ItemType>::inorderTraverse(void visit(ItemTypeamp;)) const
{
this->inorder(visit, rootPtr);
}
template<class ItemType>
void BinarySearchTree<ItemType>::postorderTraverse(void visit(ItemTypeamp;)) const
{
this->postorder(visit, rootPtr);
}
template<class ItemType>
BinarySearchTree<ItemType>amp; BinarySearchTree<ItemType>::
operator=(const BinarySearchTree<ItemType>amp; rightHandSide)
{
if (!isEmpty())
clear();
this = copyTree(amp;rightHandSide);
return *this;
}
#pragma
#include "BinarySearchTree.h"
template<class ItemType>
class Prio_Queue : public BinarySearchTree<ItemType>
{
BinarySearchTree<ItemType> BST;
public:
Prio_Queue();
void Enqueue(ItemType);
void Dequeue(ItemType);
void Peek();
};
template<class ItemType>
Prio_Queue<ItemType>::Prio_Queue()
{
}
template<class ItemType>
void Prio_Queue<ItemType>::Enqueue(ItemType entry)
{
if (BST.isEmpty())
{
BST.setRootData(entry);
}
else
BST.add(entry);
}
template<class ItemType>
void Prio_Queue<ItemType>::Dequeue(ItemType entry)
{
BST.remove(entry);
}
template<class ItemType>
void Prio_Queue<ItemType>::Peek()
{
cout << BST.getRootData();
}
Комментарии:
1. Очереди приоритетов обычно реализуются с минимальными кучами, а не с двоичными деревьями поиска. Это более эффективно.
2. Я читал это, но мне поручено сделать это с помощью деревьев двоичного поиска
3. Прежде чем вы напишете одну строку кода, у вас должен быть дизайн. Код — это не дизайн. На бумаге, как бы вы этого добились? Притворись, что C не существует. Теперь все, что вы реализовали на бумаге, вы переводите на C .
4. Весь код в вашем вопросе не имеет отношения к вопросу.