C ++ I am stuck filling this BST with my correct values
I created a BST full of WordInfo objects that have a vector that indicates which of the other WordInfo objects is synonymous or antonym. Each word is identified by an integer in its source file, dictionary.txt. BST has gotten a list of their words so far, but I'm having a hard time filling out synonyms. To be honest, I'm pretty confused about how to make my objects interact the way I want them.
Here's where I think the core of my problem is:
//--function for getting synonyms in a vector
void pushSynonyms(string synline, BST <WordInfo> wordTree)
{
int lineSize = synline.size();
const char *aux;
aux=synline.data();
int index=0;
int searchedOne= aux[0];
//wanting to find an element in the tree with this ID
//lacking: search function
while (index<=lineSize){
mySynonyms.push_back (aux[index]);
index++;
}
}
#include <iostream>
#include <fstream>
#include <string>
#include <sstream>
#include <stdlib.h>
#include <vector>
#include "MiBST.h"
using namespace std;
class WordInfo {
public:
WordInfo() {
// nothing to define?
}
~WordInfo() {
//nothing to define?
}
//--id accesor
int id () const {return myId;}
//--input function for filling Words
void readWords (istream &in)
{
in>>myId>>word;
}
//--function for getting synonyms in a vector
void pushSynonyms(string synline, BST <WordInfo> wordTree)
{
int lineSize = synline.size();
const char *aux;
aux=synline.data();
int index=0;
int searchedOne= aux[0];
//lacking: define search function
while (index<=lineSize){
mySynonyms.push_back (aux[index]);
index++;
}
}
//--function for getting antonyms in a vector
void pushAntonyms(string synline, BST <WordInfo> wordTree )
{
int lineSize = synline.size();
const char *aux;
aux=synline.data();
int index=0;
// now I need fo find the right words to pair up
while (index<=lineSize){
myAntonyms.push_back (aux[index]);
index++;
}
}
//--output function
void printWords (ostream &out)
{
out<<myId<<" "<<word;
}
//--equals operator
bool operator == (const WordInfo &otherWordInfo) const
{ return myId == otherWordInfo.myId;}
//--equals operator for String
bool operator == (const string & aString) const
{return word ==aString;}
//--less than operator
bool operator < (const WordInfo & otherWordInfo)const
{return myId<otherWordInfo.myId;}
//--more than operator
bool operator > (const WordInfo &otherWordInfo) const
{ return myId > otherWordInfo.myId;}
private:
vector<int> mySynonyms;
vector <int> myAntonyms;
string word;
int myId;
};
//--- Definition of input operator
istream & operator>>(istream & in, WordInfo & word)
{
word.readWords(in);
//I want to call word.readSyns(in) too, how?
}
//---Definition of output operator
ostream & operator <<(ostream &out, WordInfo &word)
{
word.printWords(out);
}
int main() {
//search each word by id and
// define its synonyms
string wordFile;
cout<< "enter name of dictionary file: ";
getline (cin,wordFile);
ifstream inStream(wordFile.data());
if(!inStream.is_open())
{
cerr<<"cannot open "<<wordFile<<"\n";
exit(1);
}
//build the bst of word records
BST <WordInfo> wordTree; //BST of word records
WordInfo aword; // a word record
//--loop that fills tree with words
while((inStream>> aword && (!(aword=="synonyms"))))
{
wordTree.insert(aword);
}
string line;
//--loop that takes synonyms
while((inStream>>line)&& (line!="antonyms")){
aword.pushSynonyms(line, wordTree);
}
//--loop that takes antonyms
while(inStream >> line) {
if (inStream.eof())break;
}
wordTree.graph(cout);
system("PAUSE");
return 0;
}
header file:
#include <iostream>
#include <iomanip>
#ifndef BINARY_SEARCH_TREE
#define BINARY_SEARCH_TREE
template <typename DataType>
class BST
{
public:
/***** Function Members *****/
BST();
bool empty() const;
bool search(const DataType & item) const;
void insert(const DataType & item);
void remove(const DataType & item);
void inorder(std::ostream & out) const;
void graph(std::ostream & out) const;
private:
/***** Node class *****/
class BinNode
{
public:
DataType data;
BinNode * left;
BinNode * right;
// BinNode constructors
// Default -- data part is default DataType value; both links are null.
BinNode()
: left(0), right(0)
{}
// Explicit Value -- data part contains item; both links are null.
BinNode(DataType item)
: data(item), left(0), right(0)
{}
}; //end inner class
typedef BinNode * BinNodePointer;
/***** Private Function Members *****/
void search2(const DataType & item, bool & found,
BinNodePointer & locptr, BinNodePointer & parent) const;
/*------------------------------------------------------------------------
Locate a node containing item and its parent.
Precondition: None.
Postcondition: locptr points to node containing item or is null if
not found, and parent points to its parent.#include <iostream>
------------------------------------------------------------------------*/
void inorderAux(std::ostream & out,
BST<DataType>::BinNodePointer subtreePtr) const;
/*------------------------------------------------------------------------
Inorder traversal auxiliary function.
Precondition: ostream out is open; subtreePtr points to a subtree
of this BST.
Postcondition: Subtree with root pointed to by subtreePtr has been
output to out.
------------------------------------------------------------------------*/
void graphAux(std::ostream & out, int indent,
BST<DataType>::BinNodePointer subtreeRoot) const;
/*------------------------------------------------------------------------
Graph auxiliary function.
Precondition: ostream out is open; subtreePtr points to a subtree
of this BST.
Postcondition: Graphical representation of subtree with root pointed
to by subtreePtr has been output to out, indented indent spaces.
------------------------------------------------------------------------*/
/***** Data Members *****/
BinNodePointer myRoot;
}; // end of class template declaration
//--- Definition of constructor
template <typename DataType>
inline BST<DataType>::BST()
: myRoot(0)
{}
//--- Definition of empty()
template <typename DataType>
inline bool BST<DataType>::empty() const
{ return myRoot == 0; }
//--- Definition of search()
template <typename DataType>
bool BST<DataType>::search(const DataType & item) const
{
typename BST<DataType>::BinNodePointer locptr = myRoot;
typename BST<DataType>::BinNodePointer parent =0;
/* BST<DataType>::BinNodePointer locptr = myRoot;
parent = 0; */ //falta el typename en la declaracion original
bool found = false;
while (!found && locptr != 0)
{
if (item < locptr->data) // descend left
locptr = locptr->left;
else if (locptr->data < item) // descend right
locptr = locptr->right;
else // item found
found = true;
}
return found;
}
//--- Definition of insert()
template <typename DataType>
inline void BST<DataType>::insert(const DataType & item)
{
typename BST<DataType>::BinNodePointer
locptr = myRoot, // search pointer
parent = 0; // pointer to parent of current node
bool found = false; // indicates if item already in BST
while (!found && locptr != 0)
{
parent = locptr;
if (item < locptr->data) // descend left
locptr = locptr->left;
else if (locptr->data < item) // descend right
locptr = locptr->right;
else // item found
found = true;
}
if (!found)
{ // construct node containing item
locptr = new typename BST<DataType>::BinNode(item);
if (parent == 0) // empty tree
myRoot = locptr;
else if (item < parent->data ) // insert to left of parent
parent->left = locptr;
else // insert to right of parent
parent->right = locptr;
}
else
std::cout << "Item already in the tree\n";
}
//--- Definition of remove()
template <typename DataType>
void BST<DataType>::remove(const DataType & item)
{
bool found; // signals if item is found
typename BST<DataType>::BinNodePointer
x, // points to node to be deleted
parent; // " " parent of x and xSucc
search2(item, found, x, parent);
if (!found)
{
std::cout << "Item not in the BST\n";
return;
}
//else
if (x->left != 0 && x->right != 0)
{ // node has 2 children
// Find x inorder successor and its parent
typename BST<DataType>::BinNodePointer xSucc = x->right;
parent = x;
while (xSucc->left != 0) // descend left
{
parent = xSucc;
xSucc = xSucc->left;
}
// Move contents of xSucc to x and change x
// to point to successor, which will be removed.
x->data = xSucc->data;
x = xSucc;
} // end if node has 2 children
// Now proceed with case where node has 0 or 2 child
typename BST<DataType>::BinNodePointer
subtree = x->left; // pointer to a subtree of x
if (subtree == 0)
subtree = x->right;
if (parent == 0) // root being removed
myRoot = subtree;
else if (parent->left == x) // left child of parent
parent->left = subtree;
else // right child of parent
parent->right = subtree;
delete x;
}
//--- Definition of inorder()
template <typename DataType>
inline void BST<DataType>::inorder(std::ostream & out) const
{
inorderAux(out, myRoot);
}
//--- Definition of graph()
template <typename DataType>
inline void BST<DataType>::graph(std::ostream & out) const
{ graphAux(out, 0, myRoot); }
//--- Definition of search2()
template <typename DataType>
void BST<DataType>::search2(const DataType & item, bool & found,
BST<DataType>::BinNodePointer & locptr,
BST<DataType>::BinNodePointer & parent) const
{
locptr = myRoot;
parent = 0;
found = false;
while (!found && locptr != 0)
{
if (item < locptr->data) // descend left
{
parent = locptr;
locptr = locptr->left;
}
else if (locptr->data < item) // descend right
{
parent = locptr;
locptr = locptr->right;
}
else // item found
found = true;
}
}
//--- Definition of inorderAux()
template <typename DataType>
void BST<DataType>::inorderAux(std::ostream & out,
BST<DataType>::BinNodePointer subtreeRoot) const
{
if (subtreeRoot != 0)
{
inorderAux(out, subtreeRoot->left); // L operation
out << subtreeRoot->data << " "; // V operation
inorderAux(out, subtreeRoot->right); // R operation
}
}
//--- Definition of graphAux()
template <typename DataType>
void BST<DataType>::graphAux(std::ostream & out, int indent,
BST<DataType>::BinNodePointer subtreeRoot) const
{
if (subtreeRoot != 0)
{
graphAux(out, indent + 8, subtreeRoot->right);
out << std::setw(indent) << " " << subtreeRoot->data << std::endl;
graphAux(out, indent + 8, subtreeRoot->left);
}
}
#endif
dictionary.txt
1 cute
2 hello
3 ugly
4 easy
5 difficult
6 tired
7 beautiful
synonyms
1 7
7 1
antonyms
1 3
3 1 7
4 5
5 4
7 3
-2
source to share
1 answer
Leaving aside the comments made by others, I admit there is more code in this example than I am willing to look at - I think the main problem you are having is that your existing search function is searching on an object, then as you need the one that looks for by id. Create a new lookup function that takes an ID as a parameter and loops through your tree comparing the ID of the current WordInfo object with the ID passed in. When you find one that has a matching ID, return it (instead of returning true / false that it was found). If you don't find an object with a match ID, return null. You will need to compare id (int) with the WordInfo object. My C ++ is a little rusty, so the syntax may be slightly different.
//--- Definition of find()
template <typename DataType>
DataType& BST<DataType>::find(const int id ) const
{
typename BST<DataType>::BinNodePointer locptr = myRoot;
typename BST<DataType>::BinNodePointer parent =0;
bool found = false;
while (!found && locptr != 0)
{
if (locptr->data > id) // descend left
locptr = locptr->left;
else if (locptr->data < id) // descend right
locptr = locptr->right;
else // item found
found = true;
}
return found ? locptr->data : null;
}
Note: this requires implementing operator>(const int id)
and operator<(const int id)
.
+1
source to share