fork download
copy 
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. #include <utility>
  5. #include <string>
  6. #include <vector>
  7.  
  8. class bintree {
  9.  
  10. // A binary search tree for locations in Lineland.
  11.  
  12. // Notes: 
  13. // - Assume a flat, one-dimensional world with locations from -180 to 180.
  14. // - All locations and distances are measured in the same units (degrees).
  15.  
  16. public:
  17. // Default constructor
  18. bintree() {
  19.    this->root = NULL;
  20. }
  21.  
  22. // Copy constructor
  23. bintree(const bintree &t) {
  24.   this -> root = NULL;
  25. *this = t;
  26.  }
  27.  
  28. // Destructor
  29. ~bintree() {
  30.  
  31. }
  32.  
  33.  
  34.  // Copy assignment is implemented using the copy-swap idiom
  35.  
  36.  friend void swap(bintree &t1, bintree &t2) {
  37.  using std::swap;
  38.  // Swap all data members here, e.g.,
  39.  // swap(t1.foo, t2.foo);
  40.  // Pointers should be swapped -- but not the things they point to.
  41.  }
  42.  bintree &operator= (bintree other) {
  43.  // You don't need to modify this function.
  44.  swap(*this, other);
  45.  return *this;
  46.  }
  47.  
  48. void insert(const std::string& name, double p) {
  49.    node *n = new node;       // create a new node
  50.    n->name=name; n->p=p;     // intialise the data payload
  51.    n->left=n->right=nullptr; // and make it a leaf.
  52.  
  53.    if (root==nullptr)        // if tree is empty, 
  54.       root = n;                   // add the new node. 
  55.  
  56.    else {                    // else find where to insert it
  57.       node* t=root; 
  58.       while (true) {
  59.           if (t->name > n->name) {     // go to left
  60.               if (t->left==nullptr) {
  61.                  t->left = n;     
  62.                  break;  
  63.               }
  64.               else t=t->left; 
  65.           }
  66.           else if (t->name == n->name) { // insert between current and next
  67.               n->right = t->right; 
  68.               t->right = n; 
  69.               break; 
  70.           }
  71.           else {                         // go to right 
  72.               if (t->right==nullptr) {
  73.                  t->right = n;     
  74.                  break;  
  75.               }
  76.               else t=t->right; 
  77.           }
  78.        }
  79.     }
  80.  }
  81.  void within_radius(double p, double r, std::vector<std::string> &result) const {
  82.   // Search for elements within the range `p` plus or minus `r`.
  83.   // Clears `result` and puts the elements in `result`.
  84.   // Postcondition: `result` contains all (and only) elements of the
  85.   // tree, in any order, that lie within the range `p` plus or minus
  86.   // `r`.
  87.   }
  88.  
  89.  
  90. private:
  91.  
  92.     struct node
  93.     {
  94.      node *left;
  95.      node *right;
  96.      std::string name;  // This is the key for your reasearch
  97.      double p;          // followed by other data 
  98.     };
  99.  
  100. node* root; 
  101.  
  102. public: 
  103.   void print (node *n=nullptr, int o=0) {
  104.   	  if (root==nullptr)
  105.   	      cout << "Empty"<<endl; 
  106.   	  else if (n==nullptr && o==0)
  107.   	     print (root, 0);
  108.   	  else if (n==nullptr) {
  109.   	    	  	 for (int i=0; i<o; i++) cout<<" ";
  110.   	     cout << "x"<<endl; 
  111.   	  }
  112.   	  else {
  113.   	  	 for (int i=0; i<o; i++) cout<<" ";
  114.   	     cout << n->name << " "<<n->p<<endl; 
  115.   	     print (n->left,o+1);
  116.   	     print (n->right,o+1);
  117.   	  }
  118.   }
  119. };
  120.  
  121. int main() {
  122. 	// your code goes here
  123. 	bintree b; 
  124.  
  125. 	b.insert ("B", 1);
  126. 	b.insert ("A", 2);
  127. 	b.insert ("C", 3);
  128. 	b.insert ("D", 4);
  129. 	b.insert ("C", 5);
  130.  
  131.     b.print(); 
  132. 	return 0;
  133. }
Success #stdin #stdout 0s 3464KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
B 1
 A 2
  x
  x
 C 3
  x
  C 5
   x
   D 4
    x
    x
https://ideone.com/cqXI1j
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!