fork(1) download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. class Entry {
  6.   public:
  7. 	long long phone_number;
  8. 	string name;
  9.     Entry(string, long long);
  10.     Entry(){};
  11. };
  12.  
  13. Entry::Entry (string fname, long long p_number){
  14. 	name = fname;
  15. 	phone_number = p_number;
  16. };
  17.  
  18. template<class T>
  19. class Tree {
  20.   public: 
  21.     T data;
  22.     Tree* left;
  23.     Tree* right;
  24.     Tree* parent;
  25.     Tree(T);
  26.     void insert(T, Tree*);
  27.     Tree<T>* search(string);
  28.     Tree<T>* min();
  29.     Tree<T>* max();
  30.     Tree<T>* traverse();
  31.     Tree<T>* successor();
  32.     Tree<T>* predecessor();
  33. };
  34.  
  35. template <class T>
  36. Tree<T>::Tree (T node_data){
  37. 	left = NULL;
  38. 	right = NULL;
  39. 	parent = NULL;
  40. 	data = node_data;
  41. };
  42.  
  43. template <class T>
  44. Tree<T>* Tree<T>::traverse(){
  45. 	if (left != NULL){
  46. 		left->traverse();
  47. 	}
  48. 	cout << "Data: " << data.name << " : " << data.phone_number << endl;
  49. 	if (right != NULL){
  50. 		right->traverse();
  51. 	}
  52. }
  53.  
  54.  
  55. template <class T>
  56. Tree<T>* Tree<T>::min(){
  57. 	if (left == NULL){
  58. 		return this;
  59. 	}
  60. 	return left->min();
  61. }
  62.  
  63. template <class T>
  64. Tree<T>* Tree<T>::successor(){
  65.     if (right != NULL){
  66.     	return right->min();
  67.     }
  68.     Tree<T>* up_one = parent;
  69.     Tree<T>* proxy = this;
  70.     while ((up_one != NULL) and (proxy == up_one->right)){
  71.     	proxy = up_one;
  72.     	up_one = up_one->parent;
  73.     }
  74.     return up_one;
  75. }
  76.  
  77. template <class T>
  78. Tree<T>* Tree<T>::predecessor(){
  79.     if (left != NULL){
  80.     	return left->max();
  81.     }
  82.     Tree<T>* up_one = parent;
  83.     Tree<T>* proxy = this;
  84.     while ((up_one != NULL) and (proxy == up_one->left)){
  85.     	proxy = up_one;
  86.     	up_one = up_one->parent;
  87.     }
  88.     return up_one;
  89. }
  90.  
  91. template <class T>
  92. Tree<T>* Tree<T>::max(){
  93. 	if (right == NULL){
  94. 		return this;
  95. 	}
  96. 	return right->max();
  97. }
  98.  
  99. template <class T>
  100. Tree<T>* Tree<T>::search(string fname){
  101. 	if (data.name == fname){
  102. 		return this;
  103. 	}
  104. 	if (data.name < fname){
  105. 		if (right == NULL){
  106. 			return right;
  107. 		}
  108. 		return right->search(fname);
  109. 	}
  110. 	if (data.name > fname){
  111. 		if (left == NULL){
  112. 			return left;
  113. 		}
  114. 		return left->search(fname);
  115. 	}
  116. }
  117.  
  118. template <class T>
  119. void Tree<T>::insert(T node_data, Tree * t_parent){
  120. 	if (data.name < node_data.name){
  121. 		if (right == NULL){
  122. 			right = new Tree<T> (node_data);
  123. 			right->parent = this;
  124. 			return;
  125. 		} 
  126. 		right->insert(node_data, this);
  127. 		return;
  128. 	}; 
  129.  
  130. 	if (left == NULL){
  131. 		left = new Tree<T> (node_data);
  132. 		left->parent = this;
  133. 		return;
  134. 	};
  135. 	left->insert(node_data, this);
  136. 	return;
  137. };
  138.  
  139. void load_n_phone_numbers(int n, Tree<Entry>*& myTree){
  140.   int i;
  141.   long long p_number;
  142.   string fname;
  143.   for (i = 0; i < n; i++){
  144.   	cin >> fname >> p_number;
  145.     if (myTree == NULL) {
  146.     	myTree = new Tree<Entry>(Entry(fname, p_number));
  147.     } else {
  148.     	myTree->insert(Entry(fname, p_number), NULL);
  149.     }
  150.   }
  151.   return;
  152. }; 
  153.  
  154. int main() {
  155. 	int n;
  156. 	Tree<Entry>* myTree = NULL;
  157. 	Tree<Entry>* result;
  158. 	Tree<Entry>* next_result;
  159. 	scanf("%d", &n);
  160.     load_n_phone_numbers(n, myTree);
  161.     result = myTree->search("andy");
  162.     cout << "Andy's number is: ";
  163.     if (result == NULL){
  164.     	cout << "No such string" << endl;
  165.     } else {
  166.     	cout << result->data.phone_number << endl;
  167.     }
  168.     cout << "Person after Andy is: " << endl;
  169.     next_result = result->successor();
  170.     if (next_result == NULL){
  171.     	cout << "No one " << endl;
  172.     }
  173.     else {
  174.     	cout << " named : " << next_result->data.name << endl;
  175.     }
  176.     myTree->traverse();
  177. 	return 0;
  178. };
Success #stdin #stdout 0s 3484KB
comments (?)
stdin
copy 
8
simone 8005733505
cindy 3024441111
andy 3028411895
dave 9042621100
bill 3025551111
elaine 8503211234
zelda 1234567890
john 6412481632
stdout
copy 
Andy's number is: 3028411895
Person after Andy is: 
 named : bill
Data: andy : 3028411895
Data: bill : 3025551111
Data: cindy : 3024441111
Data: dave : 9042621100
Data: elaine : 8503211234
Data: john : 6412481632
Data: simone : 8005733505
Data: zelda : 1234567890
https://ideone.com/NRKz5N
Basic Binary Search Tree!
language:
C++14 (gcc 8.3)
created:
9 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!