我搞不懂这个问题。我的搜索树只保存输入列表中的第一个条目。我想建立前、内联和后遍历以及一些其他函数（这将在我解决这个混乱的问题后完成）。
有很多解决方案，但我想变得更好，所以我想知道我做的事情有什么问题。
BSNODE.H
#include <iostream>
#include <cstddef>
#ifndef BSNODE_H
#define BSNODE_H
template <typename T>
class BSNode
{
private:
T m_entry; // A data item
BSNode<T>* m_left; // Pointer to next node
BSNode<T>* m_right;
public:
BSNode();
BSNode(const T& entry);
BSNode(const T& entry, BSNode<T>* left, BSNode<T>* right);
void setEntry(const T& entry);
void setLeft(BSNode<T>* left);
void setRight(BSNode<T>* right);
T getEntry() const ;
BSNode<T>* getLeft() const ;
BSNode<T>* getRight() const ;
};
#include "BSNode.cpp"
#endif
BSNODE.CPP
#include "BSNode.h"
using namespace std;
/*Class member variables
char m_entry;
BSNode* m_next;*/
template <typename T>
BSNode<T>::BSNode() : m_left(nullptr), m_right(nullptr)
{
}
template <typename T>
BSNode<T>::BSNode(const T& entry) : m_entry(entry), m_left(nullptr), m_right(nullptr)
{
}
template <typename T>
BSNode<T>::BSNode(const T& entry, BSNode<T>* left, BSNode<T>* right): m_entry(entry), m_left(left), m_right(right)
{
}
template <typename T>
T BSNode<T>::getEntry() const{
return m_entry;
}
template <typename T>
void BSNode<T>::setEntry(const T& entry){
m_entry=entry;
}
template <typename T>
BSNode<T>* BSNode<T>::getLeft() const{
return m_left;
}
template <typename T>
void BSNode<T>::setLeft(BSNode<T>* left){
m_left=left;
}
template <typename T>
BSNode<T>* BSNode<T>::getRight() const{
return m_right;
}
template <typename T>
void BSNode<T>::setRight(BSNode<T>* right){
m_right=right;
}
BSTINTERFACE.H
#ifndef BSTINTERFACE_H
#define BSTINTERFACE_H
#include <iostream>
#include "BSNode.h"
using namespace std;
//ItemType: What is being stored in the tree?
//KeyType: What type is used to search for an Item?
template <typename ItemType, typename KeyType>
class BinarySearchTreeInterface
{
public:
virtual ~BinarySearchTreeInterface(){}
virtual void add(ItemType entry) = 0;
virtual ItemType search(KeyType key) const = 0;
virtual void clear() = 0;
//More methods to come in next lab
};
#endif
BST.H
#ifndef BST_H
#define BST_H
#include <iostream>
#include "BSTInterface.h"
#include <stdexcept>
template <typename ItemType, typename KeyType>
class BST : public BinarySearchTreeInterface<ItemType, KeyType>
{
public:
BST():m_root(nullptr){};
~BST(){};
virtual ItemType search(KeyType key) const;
virtual void add(ItemType entry);
virtual void clear();
private:
BSNode<ItemType>* m_root;
/**add function will take in Pokemon ID with m_root as subtree. Will make for checks to see if duplicates are made **/
void add(ItemType entry, BSNode<ItemType>* subtree);
/**search will traverse through the tree recursively using operator overloads and doing checks for a Pokemon object with an ID taken from user**/
ItemType search(KeyType key, BSNode<ItemType>* subtree) const;
/**clear will use recursive calls get subtree to where it needs to get to and with recursive mix calls of subtree->getLeft subtree->getRight with delete subtree, this will
* delete the tree**/
void clear(BSNode<ItemType>* subtree);
};
#include "BST.cpp"
#endif
BST.CPP
#include "BST.h"
using namespace std;
template <typename ItemType, typename KeyType>
void BST<ItemType,KeyType>::clear(){
clear(m_root);
}
template <typename ItemType, typename KeyType>
void BST<ItemType,KeyType>::clear(BSNode<ItemType>* subtree){
if(subtree->getLeft()!= nullptr){
clear(subtree->getLeft());
}
if(subtree->getRight()!=nullptr){
clear(subtree->getRight());
}
delete subtree;
}
//public add func
template <typename ItemType, typename KeyType>
void BST<ItemType,KeyType>::add(ItemType entry){
if(m_root == nullptr){
m_root= new BSNode<ItemType>(entry);
}
else{
add(entry, m_root);
}
}
//private add func
template <typename ItemType, typename KeyType>
void BST<ItemType,KeyType>::add(ItemType entry, BSNode<ItemType>* subtree){
if(subtree->getEntry() > entry.getID()){
if(subtree->getRight()!=nullptr){
add(entry,subtree->getRight());
}
else{
BSNode<ItemType>* n= new BSNode<ItemType>(entry);
subtree->setRight(n);
}
}
else if(subtree->getEntry() < entry.getID()){
if(subtree->getLeft()!=nullptr){
add(entry, subtree->getLeft());
}
else{
BSNode<ItemType>* n= new BSNode<ItemType>(entry);
subtree->setLeft(n);
}
}
else{
throw(std::runtime_error("There are duplicate pokemon in the file that were not added\n"));
}
}
//public search func
template <typename ItemType, typename KeyType>
ItemType BST<ItemType, KeyType>::search(KeyType key) const{
return(search(key, m_root));
}
//private search func
template<typename ItemType, typename KeyType>
ItemType BST<ItemType, KeyType>::search(KeyType key, BSNode<ItemType>* subtree) const {
//check for nullptr, check for empty
if(subtree==nullptr){
throw(std::runtime_error("Item not in tree\n"));
}
/*
below accesses entry in BSNode which in this case is Poke Object
and that is why the overload operator will take over and check if
m_id == key
*/
else if(subtree->getEntry() == key)
{
//remember that this returns the "ItemType",
//in this lab it returns a pokemon object.
return(subtree->getEntry());
}
else{
//check the rest of tree
//traverse down appropriate road
if(subtree->getEntry() > key){
return(search(key, subtree->getLeft()));
}
else{
return(search(key, subtree->getRight()));
}
}
}
POKEMON.H
#ifndef POKEMON_H
#define POKEMON_H
#include <string>
using namespace std;
class Pokemon
{
public:
Pokemon():US_name(""),m_id(0),JP_name(""){};
Pokemon(std::string name, int m_id, std::string jname);
/*
This is kept for notes, the issues with below is that Left Hand Side
is compared to Right Hand Side but the whole object is passed in to RHS,
it is much easier on the computer (takes less memory) to have a "KEY"
to pass along and compare each object KEY to. In this lab it is Poke ID number
*/
//bool operator==(const Pokemon& rhs) const;
//bool operator<(const Pokemon& rhs) const;
//bool operator>(const Pokemon& rhs) const;
bool operator==(int id) const;
bool operator<(int id) const;
bool operator>(int id) const;
string getUS(){return US_name;}
int getID(){return m_id;}
string getJP(){return JP_name;}
void setUS(string US){
US_name=US;
}
void setID(int id){
m_id=id;
}
void setJP(string JP){
JP_name=JP;
}
private:
//what data do Pokemon have?
//What are the related data?
std::string US_name;
int m_id;
std::string JP_name;
};
#endif
POKEMON.CPP
#include "Pokemon.h"
Pokemon::Pokemon(std::string name, int id, std::string jname)
{
US_name=name;
m_id = id;
JP_name=jname;
}
//bool Pokemon::operator==(const Pokemon& rhs) const
//{
//if they ids are the same, they're the same Pokemon
//return(m_id == rhs.m_id);
//}
bool Pokemon::operator==(int id) const
{
return(m_id == id);
}
bool Pokemon::operator<(int id) const
{
return(m_id < id);
}
bool Pokemon::operator>(int id) const
{
return(m_id > id);
}
EXECUTIVE.H
#ifndef EXECUTIVE_H
#define EXECUTIVE_H
#include <iostream>
#include <string>
#include <fstream>
#include "BST.h"
#include "Pokemon.h"
using namespace std;
class Executive{
private:
public:
/** These are to take in info from file **/
string tempUS;
int tempID;
string tempJP;
Executive(string filename);
~Executive(){
}
};
#endif
EXECUTIVE.CPP
#include "Executive.h"
using namespace std;
Executive::Executive(string filename){
ifstream fin;
fin.open(filename);
if(fin.fail()){
cout << "File not found";
}
else{
BST<Pokemon,int> Tree;
while(fin>> tempUS >> tempID >> tempJP){
Pokemon Poke;
Poke.setUS(tempUS);
Poke.setID(tempID);
Poke.setJP(tempJP);
try{
Tree.add(Poke);
}
catch(runtime_error& rte){
cout << rte.what() << endl;
}
}
int choice;
do{
cout << "Enter 0 to Exit\nEnter 1 to Add a pokemanz\nEnter 2 to Search for a pokemanz\n";
cin >> choice;
if(choice==1){
string tUS, tJP;
int tID;
cout << "US Name: ";
cin >> tUS;
cout << "ID: ";
cin >> tID;
cout << "JP Name: ";
cin >> tJP;
Pokemon Poke;
Poke.setUS(tUS);
Poke.setID(tID);
Poke.setJP(tJP);
try{
Tree.add(Poke);
}
catch(runtime_error& rte){
cout << rte.what() << endl;
}
}
if(choice==2){
int tID;
cout << "Enter Pokemon ID:";
cin >> tID;
try{
Pokemon Poke1 = (Tree.search(tID));
cout << "<" << Poke1.getUS() << ">" << " <" <<
Poke1.getID() << "> <" << Poke1.getJP() << ">\n";
cout << endl;
}
catch(runtime_error& rte){
cout << rte.what() << endl;
}
}
}while(choice!=0);
Tree.clear();
}
}
MAIN.CPP
#include <iostream>
#include "Executive.h"
using namespace std;
int main(int argc, char* argv[])
{
if(argc < 2)
{
cout << "Incorrect number of parameters!\n";
}
else
{
Executive exec(argv[1]);
}
return 0;
}
MAKEFILE
run: main.o Executive.o Pokemon.o
g++ -g -std=c++11 -g -Wall main.o Executive.o Pokemon.o -o run
main.o: main.cpp
g++ -g -std=c++11 -g -c -Wall main.cpp
Executive.o: Executive.h Executive.cpp BSTInterface.h BST.h BST.cpp BSNode.h BSNode.cpp
g++ -g -std=c++11 -g -c -Wall Executive.cpp
Pokemon.o: Pokemon.h Pokemon.cpp
g++ -g -std=c++11 -g -c -Wall Pokemon.cpp
clean:
rm *.o run
leak:
valgrind --tool=memcheck --leak-check=yes --show-reachable=yes --num-callers=20 --track-fds=yes ./run input.txt
INPUT.TXT
Abra 63 Casey
Aerodactyl 142 Ptera
Alakazam 65 Foodin
Arbok 24 Arbok
Arcanine 59 Windie
Articuno 144 Freezer
Beedrill 15 Spear
Bellsprout 69 Madatsubomi
Blastoise 9 Kamex
Bulbasaur 1 Fushigidane
在你的节点添加函数中
if(subtree->getEntry() > entry.getID()){
if(subtree->getRight()!=nullptr){
add(entry,subtree->getRight());
}
else{
BSNode<ItemType>* n= new BSNode<ItemType>(entry);
subtree->setRight(n);
}
}
else if(subtree->getEntry() < entry.getID()){
if(subtree->getLeft()!=nullptr){
add(entry, subtree->getLeft());
}
else{
BSNode<ItemType>* n= new BSNode<ItemType>(entry);
subtree->setLeft(n);
}
}
横向走 正确的 当要添加的ID小于当前节点的ID时。
另一方面，在你的节点搜索函数中，你的
if(subtree->getEntry() > key){
return(search(key, subtree->getLeft()));
}
else{
return(search(key, subtree->getRight()));
}
横向走 左边 当要搜索的ID小于当前节点的ID时。
这种不匹配使根节点（列表中的第1个）以外的节点的ID无法被找到。
你必须反过来选择其中一个选项来解决这个问题。