Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //--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;
- }
- #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 treen";
- }
- //--- 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 BSTn";
- return;
- }
- //else
- if (x->left != 0 && x->right != 0)
- { // node has 2 children
- // Find x's 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
- 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
- //--- 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;
- }
Add Comment
Please, Sign In to add comment