SHARE
TWEET

C++ BST Help Needed

a guest Dec 14th, 2019 100 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1.  
  2. using namespace std;
  3.  
  4. struct Treenode
  5. {
  6.     int nodeValue;
  7.     int bf;
  8.     Treenode * Lchild;
  9.     Treenode * Rchild;
  10. };
  11.  
  12. class BST
  13. {
  14. private:
  15.     Treenode * root;
  16.  
  17.     void traverseInOrderInternal(Treenode *);       // internal functions - all by subtree
  18.     void traversePreOrderInternal(Treenode *);
  19.     void traversePostOrderInternal(Treenode *);
  20.     bool traverseLevelOrderInternal(Treenode *, int);
  21.     void print2DInternal(Treenode *, int);
  22.  
  23.     void deleteInternal (Treenode * &);             // internal delete function
  24.  
  25.     int heightInternal(Treenode *);                 // internal BF functions
  26.     void setallBFInternal(Treenode *);
  27.     int getLargestBFInternal(Treenode *);
  28.  
  29. public:
  30.     BST();
  31.     void insert (int &);                // user functions - all whole tree
  32.     bool search (int &);
  33.     void udelete (int &);
  34.  
  35.     void setallBF();                    // sets BF for whole tree
  36.     int height();                       // height of whole tree
  37.     int getLargestBF();                 // largest BF in whole tree
  38.  
  39.     void traverseLevelOrder();          // traversal functions
  40.     void print2D();
  41.     void traverseInOrder();
  42.     void traversePreOrder();
  43.     void traversePostOrder();
  44. };
  45.  
  46. BST::BST()
  47. {
  48.     root = nullptr;
  49. }
  50. //********************************************************
  51. // user search - search, given a value
  52. //********************************************************
  53. bool BST::search(int & value)
  54. {
  55.     Treenode *current;
  56.     bool found = false;
  57.     if (root == nullptr)
  58.     {
  59.         cout << "search: tree is empty" << endl;
  60.         exit (1);
  61.     }
  62.     else
  63.     {
  64.         current = root;
  65.         while (current != nullptr && !found)
  66.         {
  67.             if (current->nodeValue == value)
  68.             {
  69.                 found = true;
  70.             }
  71.             else if (current->nodeValue > value)
  72.             {
  73.                 current = current->Lchild;
  74.             }
  75.             else
  76.             {
  77.                 current = current->Rchild;
  78.             }
  79.         }
  80.     }
  81.     return found;
  82. }
  83. //********************************************************
  84. // user insert - insert, given a value
  85. //********************************************************
  86. //  ----- insert goes here -----
  87. //********************************************************
  88. // user delete - delete, given a value
  89. //********************************************************
  90. void BST::udelete(int & value)
  91. {
  92.     Treenode * current;         // pointer to node we're looking at
  93.     Treenode * trailing;        // trailing pointer to parent
  94.  
  95.     bool found = false;
  96.     if (root == NULL)
  97.     {
  98.         cout << "udelete:  empty tree" << endl;
  99.         exit (1);
  100.     }
  101.     else
  102.     {
  103.         current = root;
  104.         trailing = root;
  105.         while (current != nullptr && !found)
  106.         {
  107.             if (current->nodeValue == value)
  108.             {
  109.                 found = true;
  110.             }
  111.             else
  112.             {
  113.                 trailing = current;
  114.                 if (current->nodeValue > value)
  115.                 {
  116.                     current = current->Lchild;
  117.                 }
  118.                 else
  119.                 {
  120.                     current = current->Rchild;
  121.                 }
  122.             }
  123.         }
  124.         if (current == nullptr)
  125.         {
  126.             cout << "udelete:  not found" << endl;
  127.         }
  128.         else if (found)
  129.         {
  130.             if (current == root)
  131.             {
  132.                 deleteInternal(root);
  133.             }
  134.             else if (trailing->nodeValue > value)
  135.             {
  136.                 deleteInternal(trailing->Lchild);
  137.             }
  138.             else
  139.             {
  140.                 deleteInternal(trailing->Rchild);
  141.             }
  142.         }
  143.     }
  144. }
  145. //********************************************************
  146. // internal delete - delete, given the pointer to node to delete that is physically
  147. // located in the node's parent as Lchild or Rchild
  148. //********************************************************
  149. void BST::deleteInternal (Treenode * &p)
  150. {
  151.     Treenode * current;         // pointer to node we're looking at
  152.     Treenode * trailing;        // trailing pointer to parent
  153.     Treenode * temp;            // temp pointer for delete
  154.  
  155.     if (p == nullptr)
  156.     {
  157.         cout << "delete: null node" << endl;
  158.         exit(1);
  159.     }
  160.     else if(p->Lchild == nullptr && p->Rchild == nullptr)
  161.     {
  162.         temp = p;
  163.         p = nullptr;
  164.         delete temp;
  165.     }
  166.     else if(p->Lchild == nullptr)
  167.     {
  168.         temp = p;
  169.         p = temp->Rchild;
  170.         delete temp;
  171.     }
  172.     else if(p->Rchild == nullptr)
  173.     {
  174.         temp = p;
  175.         p = temp->Lchild;
  176.         delete temp;
  177.     }
  178.     else
  179.     {
  180.         current = p->Lchild;
  181.         trailing = nullptr;
  182.         while (current->Rchild != nullptr)
  183.         {
  184.             trailing = current;
  185.             current = current->Rchild;
  186.         }
  187.         p->nodeValue = current->nodeValue;
  188.         if (trailing == NULL)
  189.         {
  190.             p->Lchild = current->Lchild;
  191.         }
  192.         else
  193.         {
  194.             trailing->Rchild = current->Lchild;
  195.         }
  196.         delete current;
  197.  
  198.     }
  199. }
  200. //********************************************************
  201. // user traversal functions
  202. //********************************************************
  203. void BST::traverseInOrder()
  204. {
  205.     traverseInOrderInternal(root);
  206. }
  207. void BST::traversePreOrder()
  208. {
  209.     traversePreOrderInternal(root);
  210. }
  211. void BST::traversePostOrder()
  212. {
  213.     traversePostOrderInternal(root);
  214. }
  215. void BST::print2D()
  216. {
  217.     print2DInternal(root, 0);
  218. }
  219. void BST::traverseLevelOrder()
  220. {
  221.     int level = 1;
  222.     while (traverseLevelOrderInternal(root,level))
  223.     {
  224.         cout << endl;
  225.         level++;
  226.     }
  227. }
  228. //********************************************************
  229. // internal traversal functions
  230. //********************************************************
  231. void BST::traverseInOrderInternal(Treenode * p)
  232. {
  233.     if (p == nullptr)
  234.     {
  235. //      cout << "enter inorder with null" << endl;
  236.     }
  237.     else
  238.     {
  239. //      cout << "enter inorder " << p ->nodeValue << endl;
  240.     }
  241.     if (p != nullptr)
  242.     {
  243.         traverseInOrderInternal(p->Lchild);
  244.         cout << p->nodeValue << endl;
  245.         traverseInOrderInternal(p->Rchild);
  246.     }
  247. }
  248.  
  249. void BST::traversePreOrderInternal(Treenode * p)
  250. {
  251.     if (p != nullptr)
  252.     {
  253.         cout << p->nodeValue << endl;
  254.         traversePreOrderInternal(p->Lchild);
  255.         traversePreOrderInternal(p->Rchild);
  256.     }
  257. }
  258.  
  259. void BST::traversePostOrderInternal(Treenode * p)
  260. {
  261.     if (p != nullptr)
  262.     {
  263.         traversePostOrderInternal(p->Lchild);
  264.         traversePostOrderInternal(p->Rchild);
  265.         cout << p->nodeValue << endl;
  266.     }
  267. }
  268.  
  269. bool BST::traverseLevelOrderInternal(Treenode * p, int level)
  270. {
  271.     if (p == nullptr)
  272.         return false;
  273.     if (level == 1)
  274.     {
  275.         cout << p->nodeValue << "   ";
  276.         return true;
  277.     }
  278.     bool l = traverseLevelOrderInternal(p->Lchild, level-1);
  279.     bool r = traverseLevelOrderInternal(p->Rchild, level-1);
  280.     return l || r;
  281. }
  282. // internal recursive function, called by print2D
  283. // does a reverse inorder traversal to display top to bottom
  284. void BST::print2DInternal(Treenode *root, int space)
  285. {
  286.     int count=8;
  287.     if (root == NULL)
  288.         return;
  289.     space += count;
  290.     print2DInternal(root->Rchild, space);   // process right (top of page)
  291.     cout<<endl;                             // display node after spacing
  292.     for (int i = count; i < space; i++)
  293.         cout<<" ";
  294.     cout<<root->nodeValue<<"("<<root->bf<<")"<<"\n";
  295.     print2DInternal(root->Lchild, space);   // process left (bottom of page)
  296. }
  297. //********************************************************
  298. // user BF functions
  299. //********************************************************
  300. // user height - sets the BF for each node
  301.  
  302. int BST::height()
  303. {
  304.     return heightInternal(root);
  305. }
  306. // user setallBF - sets the BF for all nodes in the tree
  307. //  ----- setallBF goes here -----
  308.  
  309. // user BF - returns the largest balance factor in the tree
  310. //  ----- getLargestBF goes here -----
  311. //********************************************************
  312. // internal BF functions
  313. //********************************************************
  314. // heightInternal - recursive function,
  315. // returns height of a subtree given its root
  316.  
  317. int BST::heightInternal(Treenode* p)
  318. {
  319.     if (p != nullptr)
  320.     {
  321.         int lh, rh;
  322.         lh = heightInternal(p->Lchild);
  323.         rh = heightInternal(p->Rchild);
  324.         if (lh > rh)
  325.         {
  326.             lh++;
  327.             return lh;
  328.         }
  329.         else
  330.         {
  331.             rh++;
  332.             return rh;
  333.         }
  334.     }
  335.     else
  336.     {
  337.         return -1;
  338.     }
  339. }
  340.  
  341. // setallBFinternal - recursive function,
  342. // calculates the bf of a node and its subtrees
  343. //  ----- setallBFinternal goes here -----
  344. // getlargestBFInternal - resursive function,
  345. // returns largest BF in the given subtree
  346. //  ----- getLargestBFInternal goes here -----
  347.  
  348.  
  349. int main() {
  350.     return 0;
  351. }
  352.  
  353.  
  354.  
  355.  
  356.  
  357.  
  358.  
  359. //Main 1:
  360.  
  361. int main() {
  362.     BST mytree;
  363.     int i;
  364.     bool b;
  365.  
  366. // start with this small tree and test code
  367. // will be easier to debug
  368.     i=5;
  369.     mytree.insert(i);
  370.     i=8;
  371.     mytree.insert(i);
  372.     i=3;
  373.     mytree.insert(i);
  374.     i=12;
  375.     mytree.insert(i);
  376.     i=9;
  377.     mytree.insert(i);
  378.     mytree.print2D();
  379.     cout << "-------------------------------------------" << endl;
  380.     mytree.print2D();
  381.     i = 9;
  382.     b = mytree.search(i);
  383.     if (b)
  384.         cout << "search for 9 successful" << endl;
  385.     else
  386.         cout << "search for 9 not successful" << endl;
  387.     return 0;
  388.  
  389.  
  390. //Main 2:
  391.  
  392. int main() {
  393.     BST mytree;
  394.     int i;
  395.     bool b;
  396.  
  397. /* start with this small tree and test code
  398. // will be easier to debug
  399.     i=5;
  400.     mytree.insert(i);
  401.     i=8;
  402.     mytree.insert(i);
  403.     i=3;
  404.     mytree.insert(i);
  405.     i=12;
  406.     mytree.insert(i);
  407.     i=9;
  408.     mytree.insert(i);
  409.     mytree.print2D();
  410.     mytree.setallBF();
  411.     cout << "-------------------------------------------" << endl;
  412.     mytree.print2D();
  413.     cout <<" largest BF " << mytree.getLargestBF() << endl;
  414.     i = 9;
  415.     b = mytree.search(i);
  416.     if (b)
  417.         cout << "search for 9 successful" << endl;
  418.     else
  419.         cout << "search for 9 not successful" << endl;
  420.     return 0;
  421. */
  422.  
  423. // use this code and tree when the small tree is working
  424.     int array[14] = {60,50,70,30,53,80,35,57,75,32,40,77,48,45};
  425.     for (int i=0;i<14;i++)
  426.     {
  427.         mytree.insert(array[i]);
  428.     }
  429.  
  430.  
  431.  
  432. /*
  433.     cout << "traverse inorder" << endl;
  434.     mytree.traverseInOrder();
  435.     cout << "traverse preorder" << endl;
  436.     mytree.traversePreOrder();
  437.     cout << "traverse postorder" << endl;
  438.     mytree.traversePostOrder();
  439. */
  440.     mytree.print2D();
  441.     cout << "-------------------------------------------" << endl;
  442.     mytree.setallBF();
  443.     mytree.print2D();
  444.     cout <<" largest BF " << mytree.getLargestBF() << endl;
  445.     cout << "-------------------------------------------" << endl;
  446.     i = 46;
  447.     mytree.insert(i);
  448.     i = 47;
  449.     mytree.insert(i);
  450.     mytree.setallBF();
  451.     mytree.print2D();
  452.     cout <<" largest BF " << mytree.getLargestBF() << endl;
  453.     cout << "-------------------------------------------" << endl;
  454.     i=45;
  455.     mytree.udelete(i);
  456.     mytree.setallBF();
  457.     mytree.print2D();
  458.     i = 53;
  459.     b = mytree.search(i);
  460.     if (b)
  461.         cout << "search for 53 successful" << endl;
  462.     else
  463.         cout << "search for 53 not successful" << endl;
  464.     return 0;
  465.  
  466. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top