Posted By

FuadMunzerinHossain on 01/14/15


Tagged

search tree Objects binary of Multi-member


Versions (?)

Binary Search Tree of Multi-member Objects


 / Published in: C++
 

Functions include: insert, find, remove, printall, printprobes, removeall, countactive, updatestatus. These functions take in various arguments. The functions and their commands are inserted by the user.

  1. FILE Main.cpp BEGINS
  2.  
  3. /*
  4.  * Name: Fuad Munzerin Hossain
  5.  * 1 Nov 2014
  6.  */
  7.  
  8. #include "TreeNode.h"
  9. #include <iostream>
  10. #include <sstream>
  11. #include <string>
  12. #include <vector>
  13. #include <iomanip>
  14.  
  15. using namespace std;
  16.  
  17. /*
  18.  * Returns the pointer to the largest node in a tree given a pointer to its root.
  19.  * This function is called when trying to remove a node which has 2 children.
  20.  * A return by reference is necessary here because I want to change the value of the pointer in the function that calls this one.
  21.  */
  22. TreeNode* & returnLargestNodeInThisTree (TreeNode* & previousRoot, TreeNode* & root)
  23. {
  24. if (root != NULL)
  25. {
  26. return(returnLargestNodeInThisTree(root,root->getRight())); //Recursive implementation to get to the largest node.
  27. }
  28.  
  29. //Basis case. (Recursive implementation stops when the root becomes NULL)
  30. else if (root == NULL)
  31. {
  32. return previousRoot; //At this point, root is NOT the pointer to the largest node. (previousRoot is)
  33. }
  34. }
  35.  
  36. /*
  37.  * This is a secondary function for deleting a node, which gets called by the main delete function when the largest node in a tree
  38.  * is to be deleted. (In the case of a node having 2 children) Works similarly to the main function for removing a node, except
  39.  * that it does not print "Success" every time something is deleted successfully, and does not consider the case of the node
  40.  * having two children, because this function is called only to delete the largest node in a tree. (The largest node in a tree
  41.  * cannot have 2 children)
  42.  */
  43. void deleteTreeNodeInTheBackground (string tempName, TreeNode* & previousRoot, TreeNode* & root)
  44. {
  45. if (root != NULL)
  46. {
  47. //Find and delete the node in the left subtree.
  48. deleteTreeNodeInTheBackground(tempName,root,root->getLeft());
  49. //Node to be deleted is found if the following evaluates to true, proceed to appropriately delete.
  50. if (root->getEntry()->getName() == tempName)
  51. {
  52. //Condition to check if this is a leaf node.
  53. if ((root->getLeft() == NULL) && (root->getRight() == NULL))
  54. {
  55. delete root;
  56. root = NULL;
  57. return;
  58. }
  59.  
  60. //Condition to check if this node only has 1 subtree.
  61. else if(((root->getLeft() != NULL) && (root->getRight() == NULL)) || ((root->getRight() != NULL) && (root->getLeft() == NULL)))
  62. {
  63. //Condition to check whether that 1 subtree is a left subtree
  64. if ((root->getLeft() != NULL) && (root->getRight() == NULL))
  65. {
  66. TreeNode* toBeDeleted = root;
  67. root = root->getLeft();
  68. delete toBeDeleted;
  69. return;
  70. }
  71.  
  72. //Condition to check whether that 1 subtree is a right subtree
  73. else if ((root->getRight() != NULL) && (root->getLeft() == NULL))
  74. {
  75. TreeNode* toBeDeleted = root;
  76. root = root->getRight();
  77. delete toBeDeleted;
  78. return;
  79. }
  80. }
  81. //Note: no need to check here if node has 2 subtrees, because the largest node in any tree cannot have 2 children.
  82. }
  83. //Find and delete the node in the right subtree.
  84. deleteTreeNodeInTheBackground(tempName,root,root->getRight());
  85. }
  86. return;
  87. }
  88.  
  89. /*
  90.  * This is the main function for removing a node from the tree.
  91.  */
  92. void deleteTreeNode (string tempName, TreeNode* & previousRoot, TreeNode* & root)
  93. {
  94. if (root != NULL)
  95. {
  96. //Find and delete the node in the left subtree
  97. deleteTreeNode(tempName,root,root->getLeft());
  98. //Node to be deleted is found if the following evaluates to true, proceed to appropriately delete.
  99. if (root->getEntry()->getName() == tempName)
  100. {
  101. //Condition to check if this is a leaf node.
  102. if ((root->getLeft() == NULL) && (root->getRight() == NULL))
  103. {
  104. delete root;
  105. root = NULL;
  106. cout<<"Success\n";
  107. return;
  108. }
  109. //Condition to check if this node only has 1 subtree.
  110. else if(((root->getLeft() != NULL) && (root->getRight() == NULL)) || ((root->getRight() != NULL) && (root->getLeft() == NULL)))
  111. {
  112. if ((root->getLeft() != NULL) && (root->getRight() == NULL))
  113. {
  114. TreeNode* toBeDeleted = root;
  115. root = root->getLeft();
  116. delete toBeDeleted;
  117. cout<<"Success\n";
  118. return;
  119. }
  120.  
  121. else if ((root->getRight() != NULL) && (root->getLeft() == NULL))
  122. {
  123. TreeNode* toBeDeleted = root;
  124. root = root->getRight();
  125. delete toBeDeleted;
  126. cout<<"Success\n";
  127. return;
  128. }
  129. }
  130. //Condition to check if this node has 2 children
  131. else if ((root->getLeft() != NULL) && (root->getRight() != NULL))
  132. {
  133. //Make of copy of the fields of the largest node in the left subtree of the node that is to be deleted.
  134. string pivotName = ((returnLargestNodeInThisTree(root->getLeft(),root->getLeft()))->getEntry()->getName());
  135. unsigned int pivotIPaddress = ((returnLargestNodeInThisTree(root->getLeft(),root->getLeft()))->getEntry()->getIPaddress());
  136. bool pivotActive = ((returnLargestNodeInThisTree(root->getLeft(),root->getLeft()))->getEntry()->getActive());
  137.  
  138. //Delete the node which was copied from.
  139. deleteTreeNodeInTheBackground(pivotName,root->getLeft(),root->getLeft());
  140.  
  141. //Create new TreeNode object based on the field which were copied.
  142. TreeNode* rootNew = new TreeNode();
  143. rootNew->getEntry()->setName(pivotName);
  144. rootNew->getEntry()->setIPaddress(pivotIPaddress);
  145. rootNew->getEntry()->setActive(pivotActive);
  146. //Make the new TreeNode point to the same left and right trees which the "to be deleted" node is pointing to.
  147. rootNew->setLeft(root->getLeft());
  148. rootNew->setRight(root->getRight());
  149. //Make this pointer to point to the node to be deleted, so it can be deleted.
  150. TreeNode* rootPrime = root;
  151. //Make root point to the new node (The copied node)
  152. root = rootNew;
  153. //Deletes what root was originally pointing to. (The node that was intended to be deleted)
  154. delete rootPrime;
  155. cout<<"Success\n";
  156. return;
  157. }
  158. }
  159. //Find and delete the node in the right subtree
  160. deleteTreeNode(tempName,root,root->getRight());
  161. }
  162. return;
  163. }
  164.  
  165. //Finds a node given a name, and sets its active status.
  166. void updateActive (string tempName, bool active, TreeNode* root)
  167. {
  168. if (root != NULL)
  169. {
  170. //Find the node in the left subtree
  171. updateActive(tempName,active,root->getLeft());
  172. //Node is found. Set its active status.
  173. if (root->getEntry()->getName() == tempName)
  174. {
  175. root->getEntry()->setActive(active);
  176. return;
  177. }
  178. //Find the node in the right subtree
  179. updateActive(tempName,active,root->getRight());
  180. }
  181. return;
  182. }
  183.  
  184. /*
  185.  * This function is called for the removeall command and at the end of main() to delete the entire tree to avoid memory leaks.
  186.  */
  187. void masterDelete (TreeNode* & root)
  188. {
  189. if (root == NULL)
  190. {
  191. return; //Tree is empty.
  192. }
  193.  
  194. else if (root != NULL)
  195. {
  196. masterDelete(root->getLeft()); //Delete left subtree.
  197. masterDelete(root->getRight()); //Delete right subtree.
  198. delete root;
  199. root = NULL; //To indicate an empty tree.
  200. return;
  201. }
  202. }
  203.  
  204. //Examines all nodes in the tree, and increases a counter every time a node has its active status as true.
  205. void countActiveTreeNodes(int & activeCount,TreeNode* root)
  206. {
  207. if (root != NULL)
  208. {
  209. countActiveTreeNodes(activeCount,root->getLeft()); //Count in the left subtree
  210. if (root->getEntry()->getActive() == true) //increase counter if the node that is examined has its active status as true.
  211. {
  212. activeCount = activeCount + 1;
  213. }
  214. countActiveTreeNodes(activeCount,root->getRight()); //Count in the right subtree
  215. }
  216. return;
  217. }
  218.  
  219. /*
  220.  * Finds a node given a name, and increases a counter every time any node is examined.
  221.  * This function is invoked only after checking that the node with such a name already exists.
  222.  * The counter is passed by reference because the increments in each recursive call must be combined.
  223.  */
  224. void printProbes (string tempName, int & probeCount, TreeNode* root)
  225. {
  226. if (root == NULL)
  227. {
  228. return; //No node examined, so just return.
  229. }
  230.  
  231. //Node with given name is found, increase the count then print the total count, then return.
  232. if (root->getEntry()->getName()==tempName)
  233. {
  234. probeCount = probeCount + 1;
  235. cout<<probeCount<<"\n";
  236. return;
  237. }
  238.  
  239. //Node with given name is not found, but counter needs to be increased. Now check in the appropriate subtree.
  240. else if ((root->getEntry()->getName())<tempName)
  241. {
  242. probeCount = probeCount + 1;
  243. printProbes(tempName,probeCount,root->getRight());
  244. }
  245.  
  246. else
  247. {
  248. probeCount = probeCount + 1;
  249. printProbes(tempName,probeCount,root->getLeft());
  250. }
  251. }
  252.  
  253. //Finds a node given a name, already checked for existence using another function.
  254. void printTreeNode (string tempName, TreeNode* root)
  255. {
  256. if (root != NULL)
  257. {
  258. printTreeNode(tempName,root->getLeft()); //Find node in the left subtree
  259. if (root->getEntry()->getName() == tempName) //Node is found. Print the fields.
  260. {
  261. cout<<root->getEntry()->getName()<<" : "<<root->getEntry()->getIPaddress()<<" : ";
  262. if (root->getEntry()->getActive() == true)
  263. {
  264. cout<<"active\n";
  265. }
  266. else
  267. {
  268. cout<<"inactive\n";
  269. }
  270. }
  271. printTreeNode(tempName,root->getRight()); //Find node in the right subtree
  272. }
  273. return;
  274. }
  275.  
  276. //Function for printing every node in the tree, starting with the smallest (left most) node.
  277. void printTree (TreeNode* root)
  278. {
  279. if (root != NULL)
  280. {
  281. printTree(root->getLeft()); //Print the left subtree.
  282. //Print the fields of the current node.
  283. cout<<root->getEntry()->getName()<<" : "<<root->getEntry()->getIPaddress()<<" : ";
  284. if (root->getEntry()->getActive() == true)
  285. {
  286. cout<<"active\n";
  287. }
  288. else
  289. {
  290. cout<<"inactive\n";
  291. }
  292. printTree(root->getRight()); //Print the right subtree.
  293. }
  294. return;
  295. }
  296.  
  297. //Goes through the entire tree to check if a node if a given name exists. Returns true if yes.
  298. bool doesTreeNodeExist (string tempName, TreeNode* root)
  299. {
  300. if (root == NULL) //Empty tree, return false.
  301. {
  302. return false;
  303. }
  304.  
  305. if (root->getEntry()->getName()==tempName) //Found the node. Return true.
  306. {
  307. return true;
  308. }
  309.  
  310. else if ((root->getEntry()->getName())<tempName) //Find the node in the appropriate subtree.
  311. {
  312. return doesTreeNodeExist(tempName,root->getRight());
  313. }
  314.  
  315. else
  316. {
  317. return doesTreeNodeExist(tempName,root->getLeft());
  318. }
  319. }
  320.  
  321. //Function for inserting a new node in a tree. This function gets called only if a node with this name does not exist.
  322. void masterInsert (string tempName, unsigned int tempIPaddress, bool active, TreeNode* & root)
  323. {
  324. if (root == NULL) //If tree is empty.
  325. {
  326. root = new TreeNode(); //Create the new node object, then set the fields.
  327. root->getEntry()->setName(tempName);
  328. root->getEntry()->setIPaddress(tempIPaddress);
  329. root->getEntry()->setActive(active);
  330. cout<<"Success\n";
  331. return;
  332. }
  333.  
  334. else if ((root->getEntry()->getName())<tempName) //Insert the node into the appropriate subtree.
  335. {
  336. masterInsert(tempName,tempIPaddress,active,root->getRight());
  337. return;
  338. }
  339.  
  340. else
  341. {
  342. masterInsert(tempName,tempIPaddress,active,root->getLeft());
  343. return;
  344. }
  345. }
  346.  
  347. //The main function
  348. int main ()
  349. {
  350. //Make the most important and most used pointer in the entire program. (The top node in the tree)
  351. TreeNode* root = NULL;
  352.  
  353. string command; //String to hold the command argument entered by the user.
  354. string tempName=""; //String to hold the name argument entered by the user.
  355. unsigned int tempIPaddress; //Variable to hold the IP Address entered by the user.
  356. string tempActive=""; //Helper variable to hold the active status entered by the user.
  357. string line; //String for the string stream.
  358. cout<<"> ";
  359. getline(cin,line); //Gets a single line from the user.
  360.  
  361. //starts the loop and continues looping until user enters the EOF
  362. while(!cin.eof())
  363. {
  364. command="";
  365. tempName="";
  366. tempActive="";
  367.  
  368. stringstream myStream(line);
  369. myStream>>command; //Main Stream
  370.  
  371. //This layer of if and else statements covers the commands
  372. if (command == "insert")
  373. {
  374. myStream>>tempName;
  375. myStream>>tempIPaddress;
  376. myStream>>tempActive;
  377.  
  378. bool active; //Boolean to pass into a function to set the active status of a node.
  379.  
  380. if (tempActive == "active")
  381. {
  382. active = true;
  383. }
  384.  
  385. else if (tempActive == "inactive")
  386. {
  387. active = false;
  388. }
  389.  
  390. //Checks if node with given name exists already.
  391. if (doesTreeNodeExist(tempName,root) == true)
  392. {
  393. cout<<"Error: entry already exists\n";
  394. }
  395.  
  396. //All clear. Insert the node.
  397. else
  398. {
  399. masterInsert(tempName,tempIPaddress,active,root);
  400. }
  401.  
  402. }
  403.  
  404. else if (command == "find")
  405. {
  406. myStream>>tempName;
  407.  
  408. //Checks if a node with the given name exists.
  409. if(doesTreeNodeExist(tempName,root) == false)
  410. {
  411. cout<<"Error: entry does not exist\n";
  412. }
  413.  
  414. //If the node with the given name exists, print the details of the node.
  415. else
  416. {
  417. printTreeNode(tempName,root);
  418. }
  419. }
  420.  
  421. else if (command == "remove")
  422. {
  423. myStream>>tempName;
  424.  
  425. //Checks if a node with the given name exists.
  426. if(doesTreeNodeExist(tempName,root) == false)
  427. {
  428. cout<<"Error: entry does not exist\n";
  429. }
  430.  
  431. //If the node with the given name exists, delete the node.
  432. else
  433. {
  434. deleteTreeNode(tempName,root,root);
  435. }
  436. }
  437.  
  438. else if (command == "printall")
  439. {
  440. //Print the entire tree.
  441. printTree(root);
  442. }
  443.  
  444. else if (command == "printprobes")
  445. {
  446. myStream>>tempName;
  447.  
  448. int probeCount = 0;
  449.  
  450. //Checks if a node with the given name exists.
  451. if(doesTreeNodeExist(tempName,root) == false)
  452. {
  453. cout<<"Error: entry does not exist\n";
  454. }
  455.  
  456. //If the node with the given name exists, count the number of nodes examined to get to that node from the top of the tree.
  457. else
  458. {
  459. printProbes(tempName,probeCount,root);
  460. }
  461.  
  462. }
  463.  
  464. else if (command == "removeall")
  465. {
  466. //Delete the entire tree. Root is then set to NULL in this function.
  467. masterDelete(root);
  468. cout<<"Success\n";
  469. }
  470.  
  471. else if (command == "countactive")
  472. {
  473. int activeCount = 0; //Count starts at 0.
  474. //Examine every node and increment the counter if the node has its active status set as true.
  475. countActiveTreeNodes(activeCount,root);
  476. cout<<activeCount<<"\n";
  477. }
  478.  
  479. else if (command == "updatestatus")
  480. {
  481. myStream>>tempName;
  482. myStream>>tempActive;
  483.  
  484. bool active; //Boolean to pass into the updateActive function.
  485.  
  486. if (tempActive == "active")
  487. {
  488. active = true;
  489. }
  490.  
  491. else if (tempActive == "inactive")
  492. {
  493. active = false;
  494. }
  495.  
  496. //Checks if a node with the given name exists.
  497. if(doesTreeNodeExist(tempName,root) == false)
  498. {
  499. cout<<"Error: entry does not exist\n";
  500. }
  501.  
  502. //Go find the node and update its status.
  503. else
  504. {
  505. updateActive(tempName,active,root);
  506. cout<<"Success\n";
  507. }
  508. }
  509.  
  510. //so that user sees the prompt for next input
  511. cout<<"> ";
  512. getline(cin,line);
  513. }
  514.  
  515. //Deletes every node in the tree to avoid any memory leaks
  516. masterDelete(root);
  517. return 0;
  518. }
  519.  
  520. FILE Main.cpp ENDS
  521.  
  522. ----------------------------------------------------------------------------------------
  523. FILE DBentry.cpp BEGIN
  524.  
  525. #include "DBentry.h"
  526.  
  527. // the default constructor
  528. DBentry::DBentry()
  529. {
  530. ;
  531. }
  532. DBentry::DBentry (string _name, unsigned int _IPaddress, bool _active)
  533. {
  534. name = _name;
  535. IPaddress = _IPaddress;
  536. active = _active;
  537. }
  538.  
  539. // the destructor
  540. DBentry::~DBentry()
  541. {
  542. ;
  543. }
  544.  
  545. // sets the domain name, which we will use as a key.
  546. void DBentry::setName(string _name)
  547. {
  548. name = _name;
  549. return;
  550. }
  551.  
  552. // sets the IPaddress data.
  553. void DBentry::setIPaddress(unsigned int _IPaddress)
  554. {
  555. IPaddress = _IPaddress;
  556. return;
  557. }
  558.  
  559. // sets whether or not this entry is active.
  560. void DBentry::setActive (bool _active)
  561. {
  562. active = _active;
  563. return;
  564. }
  565.  
  566. // returns the name.
  567. string DBentry::getName() const
  568. {
  569. return name;
  570. }
  571.  
  572. // returns the IPaddress data.
  573. unsigned int DBentry::getIPaddress() const
  574. {
  575. return IPaddress;
  576. }
  577.  
  578. // returns whether or not this entry is active.
  579. bool DBentry::getActive() const
  580. {
  581. return active;
  582. }
  583.  
  584. File DBentry.cpp ENDS
  585. ----------------------------------------------------------------------------------------
  586. FILE DBentry.h BEGINS
  587.  
  588. #ifndef _DBENTRY_H
  589. #define _DBENTRY_H
  590.  
  591. #include <string>
  592. using namespace std;
  593.  
  594. class DBentry {
  595. private:
  596. string name;
  597. unsigned int IPaddress;
  598. bool active;
  599.  
  600. public:
  601. // the default constructor
  602. DBentry();
  603. DBentry (string _name, unsigned int _IPaddress, bool _active);
  604.  
  605. // the destructor
  606. ~DBentry();
  607.  
  608. // sets the domain name, which we will use as a key.
  609. void setName(string _name);
  610.  
  611. // sets the IPaddress data.
  612. void setIPaddress(unsigned int _IPaddress);
  613.  
  614. // sets whether or not this entry is active.
  615. void setActive (bool _active);
  616.  
  617. // returns the name.
  618. string getName() const;
  619.  
  620. // returns the IPaddress data.
  621. unsigned int getIPaddress() const;
  622.  
  623. // returns whether or not this entry is active.
  624. bool getActive() const;
  625. };
  626.  
  627. #endif
  628.  
  629. FILE DBentry.h ENDS
  630. ----------------------------------------------------------------------------------------
  631. FILE TreeNode.cpp BEGINS
  632.  
  633. #include "TreeNode.h"
  634. #include <iostream>
  635. #include <string>
  636.  
  637. // Default constructor
  638. TreeNode::TreeNode()
  639. {
  640. entryPtr = new DBentry();
  641. left = NULL;
  642. right = NULL;
  643. }
  644.  
  645. // A useful constructor
  646. TreeNode::TreeNode(DBentry* _entryPtr)
  647. {
  648. entryPtr = _entryPtr;
  649. }
  650.  
  651. // The destructor
  652. TreeNode::~TreeNode()
  653. {
  654. delete entryPtr;
  655. }
  656.  
  657. // Sets the left child of the TreeNode.
  658. void TreeNode::setLeft(TreeNode* newLeft)
  659. {
  660. left = newLeft;
  661. return;
  662. }
  663.  
  664. // Sets the right child of the TreeNode.
  665. void TreeNode::setRight(TreeNode* newRight)
  666. {
  667. right = newRight;
  668. return;
  669. }
  670.  
  671. /*
  672.  * Gets the left child of the TreeNode.
  673.  * Return type must be passed by reference as this pointer will be altered in some functions that call this function.
  674.  */
  675. TreeNode* & TreeNode::getLeft()
  676. {
  677. return left;
  678. }
  679.  
  680. /*
  681.  * Gets the right child of the TreeNode.
  682.  * Return type must be passed by reference as this pointer will be altered in some functions that call this function.
  683.  */
  684. TreeNode* & TreeNode::getRight()
  685. {
  686. return right;
  687. }
  688.  
  689. /*
  690.  * Returns the entryPtr of the TreeNode.
  691.  * Return type must be passed by reference as this pointer will be altered in some functions that call this function.
  692.  */
  693. DBentry* & TreeNode::getEntry()
  694. {
  695. return entryPtr;
  696. }
  697.  
  698. FILE TreeNode.cpp ENDS
  699. ----------------------------------------------------------------------------------------
  700. FILE TreeNode.h BEGINS
  701.  
  702. #ifndef _TREENODE_H
  703. #define _TREENODE_H
  704.  
  705. #include "DBentry.h"
  706.  
  707. class TreeNode {
  708. private:
  709. DBentry* entryPtr;
  710. TreeNode* left;
  711. TreeNode* right;
  712.  
  713. public:
  714. // default constructor
  715. TreeNode();
  716.  
  717. // A useful constructor
  718. TreeNode(DBentry* _entryPtr);
  719.  
  720. // the destructor
  721. ~TreeNode();
  722.  
  723. // Sets the left child of the TreeNode.
  724. void setLeft(TreeNode* newLeft);
  725.  
  726. // Sets the right child of the TreeNode
  727. void setRight(TreeNode* newRight);
  728.  
  729. /*
  730.   * Gets the left child of the TreeNode.
  731.   * Return type must be passed by reference as this pointer will be altered in some functions that call this function.
  732.   */
  733. TreeNode* & getLeft();
  734.  
  735. /*
  736.   * Gets the right child of the TreeNode.
  737.   * Return type must be passed by reference as this pointer will be altered in some functions that call this function.
  738.   */
  739. TreeNode* & getRight();
  740.  
  741. /*
  742.   * Returns the entryPtr of the TreeNode.
  743.   * Return type must be passed by reference as this pointer will be altered in some functions that call this function.
  744.   */
  745. DBentry* & getEntry();
  746. };
  747.  
  748. #endif
  749.  
  750. FILE TreeNode.h ENDS
  751. ------------------------------------------------------------------------------------------

Report this snippet  

You need to login to post a comment.