fork(3) download
copy 
  1. #include <iostream>
  2. #include <stack>
  3. #include <memory>
  4. #include <queue>
  5. #include <limits>
  6.  
  7. using namespace std;
  8.  
  9. template<typename T>
  10. struct Node{
  11. 	T data;
  12. 	typedef shared_ptr<Node<T>> nodeptr;
  13. 	nodeptr left, right;
  14. 	Node(const T &t, const nodeptr &l = nullptr, const nodeptr &r = nullptr) : 
  15. 	  data(t), left(l), right(r){}
  16. };
  17.  
  18. template<typename T>
  19. void visit(const typename Node<T>::nodeptr &r){
  20. 	cout << r->data << ", ";
  21. }
  22.  
  23. template<typename T>
  24. void inorder_traversal_rec(const typename Node<T>::nodeptr &r){
  25. 	if (r){
  26. 		inorder_traversal_rec<T>(r->left);
  27. 		visit<char>(r);
  28. 		inorder_traversal_rec<T>(r->right);
  29. 	}
  30. }
  31.  
  32. template<typename T>
  33. void inorder_traversal_itr(const typename Node<T>::nodeptr &r){
  34.     stack<typename Node<T>::nodeptr> st;
  35.     typename Node<T>::nodeptr n = r;
  36.  
  37.     while(n || !st.empty()){
  38.     	if (n){
  39.     		st.push(n);
  40. 			n = n->left;
  41.     	}
  42.     	else{
  43.     	    n = st.top(); st.pop();
  44.     	    visit<char>(n);
  45.     	    n = n->right;
  46.     	}
  47.     }
  48. }
  49.  
  50. template<typename T>
  51. void inorder_morris(const typename Node<T>::nodeptr &r){
  52. 	typename Node<T>::nodeptr c = r;
  53.  
  54. 	while(c){
  55. 		// if there is a left subtree
  56. 		if (c->left){
  57. 			// make b the predecessor of c but stop the alg if p already points c
  58. 			typename Node<T>::nodeptr p = c->left;
  59. 			while(p->right && p->right != c){
  60. 				p = p->right;
  61. 			}
  62. 			// now: p may be the leaf or p was already visited before and need fix
  63. 			if (!p->right){
  64. 				p->right = c; // it will be used later...
  65. 				// keep going with c
  66. 				c = c->left; // we need to get the first element in the tree
  67. 			}
  68. 			// element was already visited so right points to the next and
  69. 			// it means that everything on the left from c was visited
  70. 			// also we need to fix the link of p
  71. 			else{
  72. 				p->right = nullptr;
  73. 				visit<char>(c);
  74. 				c = c->right; // no matter it exists or not
  75. 			}
  76. 		}
  77. 		// no left subtree => print the element and switch to the right subtree
  78. 		else{
  79. 			visit<char>(c);
  80. 			c = c->right;
  81. 		}
  82. 	}
  83. }
  84.  
  85.  
  86.  
  87. template<typename T>
  88. void preorder_traversal_rec(const typename Node<T>::nodeptr &r){
  89. 	if (r){
  90. 		visit<char>(r);
  91. 		preorder_traversal_rec<T>(r->left);
  92. 		preorder_traversal_rec<T>(r->right);
  93. 	}
  94. }
  95.  
  96. template<typename T>
  97. void preorder_traversal_itr(const typename Node<T>::nodeptr &r){
  98.     stack<typename Node<T>::nodeptr> st;
  99.     typename Node<T>::nodeptr n = r;
  100.  
  101.     while(n || !st.empty()){
  102.     	if (n){
  103.     		visit<char>(n);
  104.     		st.push(n);
  105. 			n = n->left;
  106.     	}
  107.     	else{
  108.     	    n = st.top(); st.pop();
  109.     	    n = n->right;
  110.     	}
  111.     }
  112. }
  113.  
  114. template<typename T>
  115. void postorder_traversal_rec(const typename Node<T>::nodeptr &r){
  116. 	if (r){
  117. 		postorder_traversal_rec<T>(r->left);
  118. 		postorder_traversal_rec<T>(r->right);
  119. 		visit<char>(r);
  120. 	}
  121. }
  122.  
  123. template<typename T>
  124. void postorder_traversal_itr(const typename Node<T>::nodeptr &r){
  125.     stack<typename Node<T>::nodeptr> st;
  126.     typename Node<T>::nodeptr n = r;
  127.     typename Node<T>::nodeptr last;
  128.  
  129.     while(n || !st.empty()){
  130.     	if (n){
  131.     		st.push(n);
  132. 			if (n->left){
  133. 				n = n->left;
  134. 			}
  135. 			else{
  136. 				n = n->right;
  137. 			}
  138.     	}
  139.     	else{
  140.     	    last = st.top(); st.pop();
  141.     	    visit<char>(last);
  142.     	    if (!st.empty() && st.top()->right && st.top()->right != last){
  143.     	    	n = st.top()->right;
  144.     	    }
  145.     	    else{
  146.     	    	n = nullptr;
  147.     	    }
  148.     	}
  149.     }
  150. }
  151.  
  152.  
  153. template<typename T>
  154. void breadth_traversal(const typename Node<T>::nodeptr &r){
  155. 	queue<typename Node<T>::nodeptr> q;
  156. 	q.emplace(r);
  157.  
  158. 	while(!q.empty()){
  159. 	  visit<char>(q.front());
  160. 	  if (q.front()->left)  q.emplace(q.front()->left);
  161. 	  if (q.front()->right) q.emplace(q.front()->right);
  162. 	  q.pop();
  163. 	}
  164. }
  165.  
  166. template<typename T>
  167. bool isBST(const typename Node<T>::nodeptr &r, T left = numeric_limits<T>::min(), T right = numeric_limits<T>::max()){
  168. 	// no tree is valid
  169. 	if (!r){
  170. 		return true;
  171. 	}
  172. 	// if value is not in ranges it is invalid
  173. 	if (!(left <= r->data && r->data < right)){
  174. 		return false;
  175. 	}
  176. 	// but if it is in a valid range, we need to check subtrees
  177. 	else{
  178. 		return isBST(r->left, left, r->data) && isBST(r->right, r->data, right);
  179. 	}
  180. }
  181.  
  182. int main() {
  183.  
  184.     Node<char>::nodeptr binary_tree =
  185.     make_shared<Node<char>>('F', 
  186.       make_shared<Node<char>>('B', 
  187.         make_shared<Node<char>>('A'), 
  188.           make_shared<Node<char>>('D', 
  189.           make_shared<Node<char>>('C'), 
  190.           make_shared<Node<char>>('E'))),
  191.       make_shared<Node<char>>('G',
  192.           nullptr,
  193.           make_shared<Node<char>>('I',
  194.           make_shared<Node<char>>('H')))
  195.     );
  196.  
  197.     cout << "inorder" << endl;
  198.     inorder_traversal_rec<char>(binary_tree);
  199.     cout << endl;
  200.     inorder_traversal_itr<char>(binary_tree);
  201.     cout << endl;
  202.     inorder_morris<char>(binary_tree);
  203.     cout << endl << "preorder" << endl;
  204.     preorder_traversal_rec<char>(binary_tree);
  205.     cout << endl;
  206.     preorder_traversal_itr<char>(binary_tree);
  207.     cout << endl << "postorder" << endl;
  208.     postorder_traversal_rec<char>(binary_tree);
  209.     cout << endl;
  210.     postorder_traversal_itr<char>(binary_tree);    
  211.     cout << endl << "breadth first traversal" << endl;
  212.     breadth_traversal<char>(binary_tree);
  213.     cout << endl << "is valid BST? " <<
  214.     (isBST<char>(binary_tree) ? "yes" : "no") << endl;
  215.  
  216.  
  217. }
Success #stdin #stdout 0s 3448KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
inorder
A, B, C, D, E, F, G, H, I, 
A, B, C, D, E, F, G, H, I, 
A, B, C, D, E, F, G, H, I, 
preorder
F, B, A, D, C, E, G, I, H, 
F, B, A, D, C, E, G, I, H, 
postorder
A, C, E, D, B, H, I, G, F, 
A, C, E, D, B, H, I, G, F, 
breadth first traversal
F, B, G, A, D, I, C, E, H, 
is valid BST? yes
https://ideone.com/Y34M6q
language:
C++14 (gcc 8.3)
created:
10 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!