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.


Copy this code and paste it in your HTML
  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


Comments

RSS Icon Subscribe to comments

You need to login to post a comment.