Koenrad

BSTT.cpp

Jun 1st, 2013
131
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.77 KB | None | 0 0
  1. #include <iostream>
  2. #include "BSTT.h"
  3.  
  4. using namespace std;
  5.  
  6. BSTT::~BSTT() {
  7.     DeleteTree(root);
  8. }
  9.  
  10. // Returns true if a node in the tree contains the integer n, false otherwise.  Nonrecursive version.
  11. bool BSTT::IsPresent(int n) const {
  12.     TreeNode* p = root;
  13.     while ( p !=NULL ) {
  14.         if (p->num == n)
  15.             return true;
  16.         p = ( (n < p->num) ? (p->left) : (p->right) );
  17.     }
  18.     // if p is ever NULL, we know the item was not in the tree
  19.     return false;
  20. }
  21.  
  22. void BSTT::Insert(int n) {
  23.     Insert(n, root);
  24. }
  25.  
  26. void BSTT::Delete(int n) {
  27.     Delete(n, root);
  28. }
  29.  
  30. ostream& operator<<(ostream& out, const BSTT& b) {
  31.     b.PrintTree(out, b.root);
  32.     return out;
  33. }
  34.  
  35. void BSTT::PrintTree(ostream& out, TreeNode* p) const {
  36.     // inorder traversal so elements are printed in ascending order
  37.     if (p != NULL) {
  38.         PrintTree(out, p->left);  // prints nodes in left subtree
  39.         out << p->num << "\n";   // prints data in current node
  40.         PrintTree(out, p->right);  // prints nodes in right subtree
  41.     }
  42. }
  43.  
  44. void BSTT::DeleteTree(TreeNode* p) {
  45.     // deletes the entire tree that p points to
  46.     if ( p != NULL ) {
  47.         // Do recursive call to delete the left and right subtrees of p, then delete the node that p points to
  48.         DeleteTree(p->left);  
  49.         DeleteTree(p->right);
  50.         delete p;
  51.     }
  52. }
  53.  
  54. void BSTT::Insert(int n, TreeNode*& p)  {
  55.     if ( p == NULL) {
  56.         p = new TreeNode(n);
  57.     } else if (n < p->num) {
  58.         Insert(n, p->left);
  59.     } else {
  60.         Insert(n, p->right);
  61.     }
  62. }
  63.  
  64. void BSTT::Delete(int n, TreeNode*& p) {
  65.     // Note that p can never be NULL, by precondition on the public Delete
  66.     if (n < p->num) {
  67.         Delete(n, p->left);
  68.     } else if (n > p->num) {
  69.         Delete(n, p->right);
  70.     } else if (p->left == NULL  &&  p->right == NULL) {
  71.         // Leaf - although this case can be ommitted, since next case covers it
  72.         delete p;
  73.         p = NULL;
  74.     } else if (p->left == NULL) {
  75.         // p has a right child but no left child
  76.         TreeNode* q = p;  // create temp pointer
  77.         p = p->right;
  78.         delete q;
  79.     } else if (p->right == NULL) {
  80.         // p has a left child but no right child
  81.         TreeNode* q = p;
  82.         p = p->left;
  83.         delete q;
  84.     } else {
  85.         // p has both a left and a right child.
  86.         // replace p->num with the successor of num in the tree, and then
  87.         // delete the node that held this number.
  88.         p->num = DeleteSmallest(p->right);
  89.     }
  90. }
  91.  
  92.  
  93. // Delete the smallest element in the tree pointed to by p, and return the value it stored
  94. int BSTT::DeleteSmallest(TreeNode*& p) {
  95.     if (p->left != NULL) {
  96.         // There is a smaller element in the tree.  Make a recursive call.
  97.         return DeleteSmallest(p->left);
  98.     } else {
  99.         // no left child, so there is no smaller element in the tree
  100.         int n = p->num;  // save the number stored in p
  101.         TreeNode* q = p;  // save address of node so we can delete it
  102.         p = p->right;  
  103.         delete q;
  104.         return n;
  105.     }
  106. }
Advertisement
Add Comment
Please, Sign In to add comment