code_junkie

C++ I'm stuck filling this BST with its proper values

Nov 13th, 2011
97
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 12.73 KB | None | 0 0
  1. //--function for getting synonyms in a vector
  2. void pushSynonyms(string synline, BST <WordInfo> wordTree)
  3. {
  4. int lineSize = synline.size();
  5.  
  6. const char *aux;
  7.  
  8. aux=synline.data();
  9.  
  10. int index=0;
  11.  
  12. int searchedOne= aux[0];
  13. //wanting to find an element in the tree with this ID
  14.  
  15.  
  16. //lacking: search function
  17.  
  18. while (index<=lineSize){
  19. mySynonyms.push_back (aux[index]);
  20.  
  21. index++;
  22. }
  23.  
  24. }
  25.  
  26.  
  27.  
  28. #include <iostream>
  29. #include <fstream>
  30. #include <string>
  31.  
  32. #include <sstream>
  33. #include <stdlib.h>
  34. #include <vector>
  35.  
  36. #include "MiBST.h"
  37.  
  38. using namespace std;
  39.  
  40. class WordInfo {
  41.  
  42. public:
  43.  
  44. WordInfo() {
  45. // nothing to define?
  46. }
  47.  
  48. ~WordInfo() {
  49. //nothing to define?
  50. }
  51.  
  52. //--id accesor
  53. int id () const {return myId;}
  54.  
  55.  
  56. //--input function for filling Words
  57. void readWords (istream &in)
  58. {
  59. in>>myId>>word;
  60. }
  61.  
  62.  
  63.  
  64. //--function for getting synonyms in a vector
  65. void pushSynonyms(string synline, BST <WordInfo> wordTree)
  66. {
  67. int lineSize = synline.size();
  68.  
  69. const char *aux;
  70.  
  71. aux=synline.data();
  72.  
  73. int index=0;
  74.  
  75. int searchedOne= aux[0];
  76.  
  77.  
  78. //lacking: define search function
  79.  
  80. while (index<=lineSize){
  81. mySynonyms.push_back (aux[index]);
  82.  
  83. index++;
  84. }
  85.  
  86. }
  87.  
  88.  
  89.  
  90. //--function for getting antonyms in a vector
  91. void pushAntonyms(string synline, BST <WordInfo> wordTree )
  92. {
  93. int lineSize = synline.size();
  94.  
  95. const char *aux;
  96.  
  97. aux=synline.data();
  98.  
  99.  
  100.  
  101. int index=0;
  102.  
  103. // now I need fo find the right words to pair up
  104.  
  105.  
  106. while (index<=lineSize){
  107. myAntonyms.push_back (aux[index]);
  108.  
  109. index++;
  110. }
  111.  
  112. }
  113.  
  114. //--output function
  115. void printWords (ostream &out)
  116. {
  117. out<<myId<<" "<<word;
  118. }
  119.  
  120. //--equals operator
  121. bool operator == (const WordInfo &otherWordInfo) const
  122. { return myId == otherWordInfo.myId;}
  123.  
  124. //--equals operator for String
  125. bool operator == (const string & aString) const
  126. {return word ==aString;}
  127.  
  128. //--less than operator
  129. bool operator < (const WordInfo & otherWordInfo)const
  130. {return myId<otherWordInfo.myId;}
  131.  
  132. //--more than operator
  133. bool operator > (const WordInfo &otherWordInfo) const
  134. { return myId > otherWordInfo.myId;}
  135.  
  136.  
  137.  
  138. private:
  139. vector<int> mySynonyms;
  140. vector <int> myAntonyms;
  141. string word;
  142. int myId;
  143.  
  144. };
  145.  
  146.  
  147. //--- Definition of input operator
  148. istream & operator>>(istream & in, WordInfo & word)
  149. {
  150.  
  151.  
  152. word.readWords(in);
  153.  
  154. //I want to call word.readSyns(in) too, how?
  155. }
  156.  
  157.  
  158.  
  159.  
  160.  
  161. //---Definition of output operator
  162.  
  163. ostream & operator <<(ostream &out, WordInfo &word)
  164. {
  165. word.printWords(out);
  166. }
  167.  
  168. int main() {
  169.  
  170. //search each word by id and
  171. // define its synonyms
  172.  
  173. string wordFile;
  174.  
  175. cout<< "enter name of dictionary file: ";
  176. getline (cin,wordFile);
  177.  
  178. ifstream inStream(wordFile.data());
  179.  
  180. if(!inStream.is_open())
  181. {
  182. cerr<<"cannot open "<<wordFile<<"n";
  183. exit(1);
  184. }
  185.  
  186. //build the bst of word records
  187. BST <WordInfo> wordTree; //BST of word records
  188.  
  189. WordInfo aword; // a word record
  190.  
  191. //--loop that fills tree with words
  192. while((inStream>> aword && (!(aword=="synonyms"))))
  193. {
  194. wordTree.insert(aword);
  195. }
  196.  
  197. string line;
  198.  
  199. //--loop that takes synonyms
  200. while((inStream>>line)&& (line!="antonyms")){
  201.  
  202. aword.pushSynonyms(line, wordTree);
  203. }
  204.  
  205. //--loop that takes antonyms
  206. while(inStream >> line) {
  207.  
  208. if (inStream.eof())break;
  209. }
  210.  
  211. wordTree.graph(cout);
  212.  
  213. system("PAUSE");
  214.  
  215. return 0;
  216. }
  217.  
  218. #include <iostream>
  219. #include <iomanip>
  220.  
  221. #ifndef BINARY_SEARCH_TREE
  222. #define BINARY_SEARCH_TREE
  223.  
  224.  
  225.  
  226.  
  227. template <typename DataType>
  228. class BST
  229. {
  230. public:
  231. /***** Function Members *****/
  232. BST();
  233.  
  234. bool empty() const;
  235.  
  236. bool search(const DataType & item) const;
  237.  
  238. void insert(const DataType & item);
  239.  
  240. void remove(const DataType & item);
  241.  
  242. void inorder(std::ostream & out) const;
  243.  
  244. void graph(std::ostream & out) const;
  245.  
  246. private:
  247. /***** Node class *****/
  248. class BinNode
  249. {
  250. public:
  251. DataType data;
  252. BinNode * left;
  253. BinNode * right;
  254.  
  255. // BinNode constructors
  256. // Default -- data part is default DataType value; both links are null.
  257. BinNode()
  258. : left(0), right(0)
  259. {}
  260.  
  261. // Explicit Value -- data part contains item; both links are null.
  262. BinNode(DataType item)
  263. : data(item), left(0), right(0)
  264. {}
  265.  
  266.  
  267. }; //end inner class
  268.  
  269. typedef BinNode * BinNodePointer;
  270.  
  271. /***** Private Function Members *****/
  272. void search2(const DataType & item, bool & found,
  273. BinNodePointer & locptr, BinNodePointer & parent) const;
  274. /*------------------------------------------------------------------------
  275. Locate a node containing item and its parent.
  276.  
  277. Precondition: None.
  278. Postcondition: locptr points to node containing item or is null if
  279. not found, and parent points to its parent.#include <iostream>
  280. ------------------------------------------------------------------------*/
  281.  
  282. void inorderAux(std::ostream & out,
  283. BST<DataType>::BinNodePointer subtreePtr) const;
  284. /*------------------------------------------------------------------------
  285. Inorder traversal auxiliary function.
  286.  
  287. Precondition: ostream out is open; subtreePtr points to a subtree
  288. of this BST.
  289. Postcondition: Subtree with root pointed to by subtreePtr has been
  290. output to out.
  291. ------------------------------------------------------------------------*/
  292.  
  293. void graphAux(std::ostream & out, int indent,
  294. BST<DataType>::BinNodePointer subtreeRoot) const;
  295. /*------------------------------------------------------------------------
  296. Graph auxiliary function.
  297.  
  298. Precondition: ostream out is open; subtreePtr points to a subtree
  299. of this BST.
  300. Postcondition: Graphical representation of subtree with root pointed
  301. to by subtreePtr has been output to out, indented indent spaces.
  302. ------------------------------------------------------------------------*/
  303.  
  304. /***** Data Members *****/
  305. BinNodePointer myRoot;
  306.  
  307. }; // end of class template declaration
  308.  
  309. //--- Definition of constructor
  310. template <typename DataType>
  311. inline BST<DataType>::BST()
  312. : myRoot(0)
  313. {}
  314.  
  315. //--- Definition of empty()
  316. template <typename DataType>
  317. inline bool BST<DataType>::empty() const
  318. { return myRoot == 0; }
  319.  
  320. //--- Definition of search()
  321. template <typename DataType>
  322. bool BST<DataType>::search(const DataType & item) const
  323. {
  324. typename BST<DataType>::BinNodePointer locptr = myRoot;
  325.  
  326. typename BST<DataType>::BinNodePointer parent =0;
  327.  
  328. /* BST<DataType>::BinNodePointer locptr = myRoot;
  329. parent = 0; */ //falta el typename en la declaracion original
  330.  
  331. bool found = false;
  332. while (!found && locptr != 0)
  333. {
  334. if (item < locptr->data) // descend left
  335. locptr = locptr->left;
  336. else if (locptr->data < item) // descend right
  337. locptr = locptr->right;
  338. else // item found
  339. found = true;
  340. }
  341. return found;
  342. }
  343.  
  344. //--- Definition of insert()
  345. template <typename DataType>
  346. inline void BST<DataType>::insert(const DataType & item)
  347. {
  348. typename BST<DataType>::BinNodePointer
  349. locptr = myRoot, // search pointer
  350. parent = 0; // pointer to parent of current node
  351. bool found = false; // indicates if item already in BST
  352. while (!found && locptr != 0)
  353. {
  354. parent = locptr;
  355. if (item < locptr->data) // descend left
  356. locptr = locptr->left;
  357. else if (locptr->data < item) // descend right
  358. locptr = locptr->right;
  359. else // item found
  360. found = true;
  361. }
  362. if (!found)
  363. { // construct node containing item
  364.  
  365.  
  366. locptr = new typename BST<DataType>::BinNode(item);
  367. if (parent == 0) // empty tree
  368. myRoot = locptr;
  369. else if (item < parent->data ) // insert to left of parent
  370. parent->left = locptr;
  371. else // insert to right of parent
  372. parent->right = locptr;
  373. }
  374. else
  375. std::cout << "Item already in the treen";
  376. }
  377.  
  378. //--- Definition of remove()
  379. template <typename DataType>
  380. void BST<DataType>::remove(const DataType & item)
  381. {
  382. bool found; // signals if item is found
  383. typename BST<DataType>::BinNodePointer
  384. x, // points to node to be deleted
  385. parent; // " " parent of x and xSucc
  386. search2(item, found, x, parent);
  387.  
  388. if (!found)
  389. {
  390. std::cout << "Item not in the BSTn";
  391. return;
  392. }
  393. //else
  394. if (x->left != 0 && x->right != 0)
  395. { // node has 2 children
  396. // Find x's inorder successor and its parent
  397. typename BST<DataType>::BinNodePointer xSucc = x->right;
  398. parent = x;
  399. while (xSucc->left != 0) // descend left
  400. {
  401. parent = xSucc;
  402. xSucc = xSucc->left;
  403. }
  404.  
  405. // Move contents of xSucc to x and change x
  406. // to point to successor, which will be removed.
  407. x->data = xSucc->data;
  408. x = xSucc;
  409. } // end if node has 2 children
  410.  
  411. // Now proceed with case where node has 0 or 2 child
  412. typename BST<DataType>::BinNodePointer
  413. subtree = x->left; // pointer to a subtree of x
  414. if (subtree == 0)
  415. subtree = x->right;
  416. if (parent == 0) // root being removed
  417. myRoot = subtree;
  418. else if (parent->left == x) // left child of parent
  419. parent->left = subtree;
  420. else // right child of parent
  421. parent->right = subtree;
  422. delete x;
  423. }
  424.  
  425. //--- Definition of inorder()
  426. template <typename DataType>
  427. inline void BST<DataType>::inorder(std::ostream & out) const
  428. {
  429. inorderAux(out, myRoot);
  430. }
  431.  
  432. //--- Definition of graph()
  433. template <typename DataType>
  434. inline void BST<DataType>::graph(std::ostream & out) const
  435. { graphAux(out, 0, myRoot); }
  436.  
  437. //--- Definition of search2()
  438. template <typename DataType>
  439. void BST<DataType>::search2(const DataType & item, bool & found,
  440. BST<DataType>::BinNodePointer & locptr,
  441. BST<DataType>::BinNodePointer & parent) const
  442. {
  443. locptr = myRoot;
  444. parent = 0;
  445. found = false;
  446. while (!found && locptr != 0)
  447. {
  448. if (item < locptr->data) // descend left
  449. {
  450. parent = locptr;
  451. locptr = locptr->left;
  452. }
  453. else if (locptr->data < item) // descend right
  454. {
  455. parent = locptr;
  456. locptr = locptr->right;
  457. }
  458. else // item found
  459. found = true;
  460. }
  461. }
  462. //--- Definition of inorderAux()
  463. template <typename DataType>
  464. void BST<DataType>::inorderAux(std::ostream & out,
  465. BST<DataType>::BinNodePointer subtreeRoot) const
  466. {
  467. if (subtreeRoot != 0)
  468. {
  469. inorderAux(out, subtreeRoot->left); // L operation
  470. out << subtreeRoot->data << " "; // V operation
  471. inorderAux(out, subtreeRoot->right); // R operation
  472. }
  473. }
  474.  
  475.  
  476. //--- Definition of graphAux()
  477.  
  478.  
  479. template <typename DataType>
  480. void BST<DataType>::graphAux(std::ostream & out, int indent,
  481. BST<DataType>::BinNodePointer subtreeRoot) const
  482. {
  483. if (subtreeRoot != 0)
  484. {
  485. graphAux(out, indent + 8, subtreeRoot->right);
  486. out << std::setw(indent) << " " << subtreeRoot->data << std::endl;
  487. graphAux(out, indent + 8, subtreeRoot->left);
  488. }
  489. }
  490.  
  491.  
  492. #endif
  493.  
  494. 1 cute
  495. 2 hello
  496. 3 ugly
  497. 4 easy
  498. 5 difficult
  499. 6 tired
  500. 7 beautiful
  501. synonyms
  502. 1 7
  503. 7 1
  504. antonyms
  505. 1 3
  506. 3 1 7
  507. 4 5
  508. 5 4
  509. 7 3
  510.  
  511. //--- Definition of find()
  512. template <typename DataType>
  513. DataType& BST<DataType>::find(const int id ) const
  514. {
  515. typename BST<DataType>::BinNodePointer locptr = myRoot;
  516.  
  517. typename BST<DataType>::BinNodePointer parent =0;
  518.  
  519. bool found = false;
  520. while (!found && locptr != 0)
  521. {
  522. if (locptr->data > id) // descend left
  523. locptr = locptr->left;
  524. else if (locptr->data < id) // descend right
  525. locptr = locptr->right;
  526. else // item found
  527. found = true;
  528. }
  529. return found ? locptr->data : null;
  530. }
Add Comment
Please, Sign In to add comment