我正在实现一个模板化的类来制作二进制搜索树，但在编译时我得到了以下错误：
BinaryNodeTree.cpp:7:1: error: ‘BinaryNodeTree’ does not name a type
7 | BinaryNodeTree<ItemType>::BinaryNodeTree(){
| ^~~~~~~~~~~~~~
BinaryNodeTree.cpp:18:1: error: ‘BinaryNode’ does not name a type
18 | BinaryNode<ItemType>* BinaryNodeTree<ItemType>::newTree(const BinaryNode<ItemType>* cTree) m
const{
| ^~~~~~~~~~
BinaryNodeTree.cpp:31:20: error: expected initializer before ‘<’ token
31 | void BinaryNodeTree<ItemType>::add(const ItemType& newData){
| ^
BinaryNodeTree.cpp:38:1: error: ‘BinaryNode’ does not name a type
38 | BinaryNode<ItemType>* BinaryNodeTree<ItemType>::inOrderAdd(BinaryNode<ItemType>* subPtr,
BinaryNode<ItemType>* newNodePtr){
| ^~~~~~~~~~
BinaryNodeTree.cpp:59:24: error: expected initializer before ‘<’ token
59 | ItemType BinaryNodeTree<ItemType>::getEntry(const int& value) const{
等等。我所有的课。这是我的.h文件，后面是我的CPP文件：
BinaryNodeTree.h:
#ifndef BINARY_NODE_TREE
#define BINARY_NODE_TREE
#include "BinaryNode.h"
#include "NotFoundException.h"
#include <iostream>
template<class ItemType>
class BinaryNodeTree //:public BinaryTreeInterface<ItemType>
{
private:
BinaryNode<ItemType>* rootPtr;
protected:
//------------------------------------------------------------
// Protected Utility Methods Section:
// Helper methods for public methods.
//------------------------------------------------------------
int getNumberOfNodesHelper(BinaryNode<ItemType>* subTreePtr) const;
BinaryNode<ItemType>* removeValue(BinaryNode<ItemType>* subTreePtr, const int& target, bool& success);
BinaryNode<ItemType>* removeNode(BinaryNode<ItemType>* nodeToDeletePtr);
BinaryNode<ItemType>* removeLeftmostNode(BinaryNode<ItemType>* nodeToDeletePtr, ItemType& inorderSuccessor);
bool isLeaf(BinaryNode<ItemType>* nodeToDeletePtr);
void destroyTree(BinaryNode<ItemType>* subTreePtr);
BinaryNode<ItemType>* findNode(BinaryNode<ItemType>* subTreePtr, int value) const;
void inorderHelper(void visit(ItemType&), BinaryNode<ItemType>* subTreePtr) const;
void preorderHelper(void visit(ItemType&), BinaryNode<ItemType>* subTreePtr) const;
void postorderHelper(void visit(ItemType&), BinaryNode<ItemType>* subTreePtr) const;
void levelOrderHelper(void visit(ItemType&), BinaryNode<ItemType>* subTreePtr, int level);
BinaryNode<ItemType>* inOrderAdd(BinaryNode<ItemType>* subPtr, BinaryNode<ItemType>* newNodePtr);
BinaryNode<ItemType>* newTree(const BinaryNode<ItemType>* cTree) const;
//BinaryNode<ItemType>* getLeftmostNodeHelper(BinaryNode<ItemType>* nodeToGetPtr, ItemType& inorderSuccessor);
public:
//------------------------------------------------------------
// Constructor and Destructor Section.
//------------------------------------------------------------
BinaryNodeTree(); // creates an empty BST
//BinaryNodeTree(const BinaryNodeTree<ItemType>& tree);
~BinaryNodeTree();
//------------------------------------------------------------
// Public Methods Section.
//------------------------------------------------------------
bool isEmpty() const;
int getNumberOfNodes() const;
void add(const ItemType& newEntry);
bool remove(const int& value); //throw(NotFoundException);
ItemType getEntry(const int& value) const; //throw(NotFoundException);
bool contains(const int& value) const;
ItemType getRootData() const;
void setRootData(const ItemType& newData);
void clear();
//ItemType getLeftmostNode();
int getHeight(BinaryNode<ItemType>* subTreePtr) const;
//------------------------------------------------------------
// Public Traversals Section.
//------------------------------------------------------------
void levelOrderTraverse(void visit(ItemType&));
void preorderTraverse(void visit(ItemType&)) const;
void inorderTraverse(void visit(ItemType&)) const;
void postorderTraverse(void visit(ItemType&)) const;
//------------------------------------------------------------
};
// end BinaryNodeTree
#include "BinaryNodeTree.cpp"
#endif
BinaryNodeTree.cpp:
#include <iostream>
//#include "BinaryNodeTree.h"
//using namespace std;
template<typename ItemType>
BinaryNodeTree<ItemType>::BinaryNodeTree(){
rootPtr = nullptr;
std::cout<<"constructor running"<<std::endl;
}
template<typename ItemType>
BinaryNodeTree<ItemType>::~BinaryNodeTree(){
destroyTree(rootPtr);
}
template<typename ItemType>
BinaryNode<ItemType>* BinaryNodeTree<ItemType>::newTree(const BinaryNode<ItemType>* cTree) const{
BinaryNode<ItemType>* newPtr = nullptr;
if (cTree != nullptr){
newPtr = new BinaryNode<ItemType>(cTree->getItem());
newPtr->setLeftChildPtr(newTree(cTree->getLeftChildPtr()));
newPtr->setRightChildPtr(newTree(cTree->getRightChildPtr()));
}
return newPtr;
}
template<typename ItemType>
void BinaryNodeTree<ItemType>::add(const ItemType& newData){
BinaryNode<ItemType>* newNodePtr = new BinaryNode<ItemType>(newData);
rootPtr = inOrderAdd(rootPtr,newNodePtr);
}
template<typename ItemType>
BinaryNode<ItemType>* BinaryNodeTree<ItemType>::inOrderAdd(BinaryNode<ItemType>* subPtr, BinaryNode<ItemType>* newNodePtr){
if(subPtr == nullptr){
return newNodePtr;
}
else if(newNodePtr->getItem() < subPtr->getItem()) {
BinaryNode<ItemType>* tempPtr = inOrderAdd(subPtr ->getLeftChildPtr(), newNodePtr);
subPtr->setLeftChildPtr(tempPtr);
}
else {
BinaryNode<ItemType>* tempPtr = inOrderAdd(subPtr ->getRightChildPtr(), newNodePtr);
subPtr->setRightChildPtr(tempPtr);
}
return subPtr;
}
template<typename ItemType>
ItemType BinaryNodeTree<ItemType>::getEntry(const int& value) const{
BinaryNode<ItemType>* foundPtr = findNode(rootPtr, value);
int foundItemNum = foundPtr->getItem();
if (!contains(foundItemNum)){
throw NotFoundException("No item found for given value.");
}
else
return (foundPtr->getItem());
}
template<typename ItemType>
BinaryNode<ItemType>* BinaryNodeTree<ItemType>::findNode(BinaryNode<ItemType>* subPtr, int value) const{
if (subPtr == nullptr)
return nullptr;
else if(subPtr->getItem() == value)
return subPtr;
else if(subPtr->getItem() > value)
return findNode(subPtr->getLeftChildPtr(), value);
else
return findNode(subPtr->getRightChildPtr(), value);
}
template<typename ItemType>
int BinaryNodeTree<ItemType>::getNumberOfNodesHelper(BinaryNode<ItemType>* subTreePtr) const{
if(subTreePtr == NULL)
return 0;
else
return (1 + getNumberOfNodesHelper(subTreePtr->getLeftChildPtr()) + getNumberOfNodesHelper(subTreePtr->getRightChildPtr()));
}
template<typename ItemType>
bool BinaryNodeTree<ItemType>::isEmpty() const{
if (rootPtr == nullptr)
return true;
else
return false;
}
template<typename ItemType>
int BinaryNodeTree<ItemType>::getNumberOfNodes() const{
return (getNumberOfNodesHelper(rootPtr));
}
template<typename ItemType>
ItemType BinaryNodeTree<ItemType>::getRootData() const {
return rootPtr->getItem();
}
template<typename ItemType>
void BinaryNodeTree<ItemType>::setRootData(const ItemType& newData) {
rootPtr->setItem(newData);
}
template<typename ItemType>
bool BinaryNodeTree<ItemType>::remove(const int& value) {
bool success = false;
rootPtr = removeValue(rootPtr, value, success);
if (success == false){
throw NotFoundException("Could not remove value");
}
else
return success;
}
template<typename ItemType>
BinaryNode<ItemType>* BinaryNodeTree<ItemType>::removeValue(BinaryNode<ItemType>* subTreePtr, const int& target, bool& success){
if (subTreePtr == nullptr){
success = false;
return nullptr;
}
else if (subTreePtr->getItem() == target){
subTreePtr = removeNode(subTreePtr);
success = true;
return subTreePtr;
}
else if(subTreePtr->getItem() > target){
BinaryNode<ItemType>* temp = removeValue(subTreePtr->getLeftChildPtr(), target, success);
subTreePtr->setLeftChildPtr(temp);
return subTreePtr;
}
else {
BinaryNode<ItemType>* temp = removeValue(subTreePtr->getRightChildPtr(), target, success);
subTreePtr->setRightChildPtr(temp);
return subTreePtr;
}
}
template<typename ItemType>
BinaryNode<ItemType>* BinaryNodeTree<ItemType>::removeNode(BinaryNode<ItemType>* nodeToDeletePtr){
//No child pointers
if (nodeToDeletePtr->isLeaf()){
delete nodeToDeletePtr;
nodeToDeletePtr = nullptr;
return nodeToDeletePtr;
}
//One child point
else if ((nodeToDeletePtr->getLeftChildPtr()==nullptr && nodeToDeletePtr->getRightChildPtr()!=nullptr) || (nodeToDeletePtr->getLeftChildPtr()!=nullptr && nodeToDeletePtr->getRightChildPtr()==nullptr)){
BinaryNode<ItemType>* connectPtr;
if(nodeToDeletePtr->getLeftChildPtr() == nullptr)
connectPtr = nodeToDeletePtr->getRightChildPtr();
else
connectPtr = nodeToDeletePtr->getLeftChildPtr();
delete nodeToDeletePtr;
nodeToDeletePtr = nullptr;
return connectPtr;
}
//Two children
else {
ItemType inorderSuccessor;
BinaryNode<ItemType>* temp = removeLeftmostNode(nodeToDeletePtr->getRightChildPtr(), inorderSuccessor);
nodeToDeletePtr->setRightChildPtr(temp);
nodeToDeletePtr->setItem(inorderSuccessor);
}
return nodeToDeletePtr;
}
template<typename ItemType>
BinaryNode<ItemType>* BinaryNodeTree<ItemType>::removeLeftmostNode(BinaryNode<ItemType>* nodeToDeletePtr, ItemType& inorderSuccessor){
if(nodeToDeletePtr->getLeftChildPtr() == nullptr) {
inorderSuccessor = nodeToDeletePtr->getItem();
return removeNode(nodeToDeletePtr);
}
else {
nodeToDeletePtr->setLeftChildPtr(removeLeftmostNode(nodeToDeletePtr->getLeftChildPtr(), inorderSuccessor));
return nodeToDeletePtr;
}
}
template<typename ItemType>
bool BinaryNodeTree<ItemType>::isLeaf(BinaryNode<ItemType>* nodeToDeletePtr){
if (((nodeToDeletePtr->getLeftChildPtr())==nullptr) && ((nodeToDeletePtr->getRightChildPtr())==nullptr))
return true;
else
return false;
}
template<typename ItemType>
void BinaryNodeTree<ItemType>::clear() {
}
template<typename ItemType>
bool BinaryNodeTree<ItemType>::contains(const int& value) const{
if (findNode(rootPtr, value))
return true;
else
return false;
}
template<typename ItemType>
void BinaryNodeTree<ItemType>::preorderTraverse(void visit(ItemType&)) const{
preorderHelper(visit, rootPtr);
}
template<typename ItemType>
void BinaryNodeTree<ItemType>::inorderTraverse(void visit(ItemType&)) const {
inorderHelper(visit, rootPtr);
}
template<typename ItemType>
void BinaryNodeTree<ItemType>::postorderTraverse(void visit(ItemType&)) const {
postorderHelper(visit, rootPtr);
}
template<typename ItemType>
void BinaryNodeTree<ItemType>::levelOrderTraverse(void visit(ItemType&)) {
int hValue = getHeight(rootPtr);
for (int i=1; i<hValue; i++){
levelOrderHelper(visit, rootPtr, i);
}
}
template<typename ItemType>
int BinaryNodeTree<ItemType>::getHeight(BinaryNode<ItemType>* subTreePtr) const{
if (subTreePtr == nullptr){
return(-1);
}
else {
int lHeight = getHeight(subTreePtr->getLeftChildPtr());
int rHeight = getHeight(subTreePtr->getRightChildPtr());
if(rHeight > lHeight){
return(rHeight+1);
} else {
return(lHeight+1);
}
}
}
template<typename ItemType>
void BinaryNodeTree<ItemType>::levelOrderHelper(void visit(ItemType&), BinaryNode<ItemType>* subTreePtr, int level) {
if (subTreePtr != nullptr) {
if (level == 1){
ItemType anItem = subTreePtr->getItem();
visit(anItem);
}
else {
levelOrderHelper(visit, subTreePtr->getLeftChildPtr(), level-1);
levelOrderHelper(visit, subTreePtr->getRightChildPtr(), level-1);
}
}
}
template<typename ItemType>
void BinaryNodeTree<ItemType>::inorderHelper(void visit(ItemType&), BinaryNode<ItemType>* subTreePtr) const{
if(subTreePtr != nullptr){
inorderHelper(visit, subTreePtr->getLeftChildPtr());
ItemType anItem = subTreePtr->getItem();
visit(anItem);
inorderHelper(visit, subTreePtr->getRightChildPtr());
}
}
template<typename ItemType>
void BinaryNodeTree<ItemType>::postorderHelper(void visit(ItemType&), BinaryNode<ItemType>* subTreePtr) const{
if(subTreePtr != nullptr){
postorderHelper(visit, subTreePtr->getLeftChildPtr());
postorderHelper(visit, subTreePtr->getRightChildPtr());
ItemType anItem = subTreePtr->getItem();
visit(anItem);
}
}
template<typename ItemType>
void BinaryNodeTree<ItemType>::preorderHelper(void visit(ItemType&), BinaryNode<ItemType>* subTreePtr) const{
if(subTreePtr != nullptr){
ItemType anItem = subTreePtr->getItem();
visit(anItem);
preorderHelper(visit, subTreePtr->getLeftChildPtr());
preorderHelper(visit, subTreePtr->getRightChildPtr());
}
}
template<typename ItemType>
void BinaryNodeTree<ItemType>::destroyTree(BinaryNode<ItemType>* subTreePtr){
if(subTreePtr != NULL) {
destroyTree(subTreePtr->getLeftChildPtr());
destroyTree(subTreePtr->getRightChildPtr());
delete subTreePtr;
}
}
我不确定问题出在哪里，但我觉得我已经用尽了所有的工具。我试着在互联网上搜索这个问题，但我的努力都白费了。
在BinaryNodeTree.cpp中，#include似乎被注释掉了。这可能至少解决了部分问题。