fork(1) download
copy 
  1. #include <iostream>
  2. #include <string>
  3. #include <memory>
  4. #include <functional>
  5.  
  6. template <typename T, typename Comparator>
  7. class BinaryTree {
  8. public:
  9. 	enum TreeTraversal {Preorder, Postorder, Inorder};
  10. private:
  11. 	class Node : public std::enable_shared_from_this<Node> {
  12. 		private:
  13. 			BinaryTree& binaryTree;  // Reference data member because every BinaryTree::Node belongs to a BinaryTree.
  14. 			T value;
  15. 			std::shared_ptr<Node> left = nullptr, right = nullptr, parent = nullptr;
  16. 			std::size_t subtreeSize, subtreeHeight, depthFromRoot;
  17. 			friend class BinaryTree;
  18. 		public:
  19. 			Node (BinaryTree& tree, const T& t, std::size_t size = 1, std::size_t height = 0, std::size_t depth = 0) : binaryTree(tree), value(t), subtreeSize(size), subtreeHeight(height), depthFromRoot(depth) {}
  20. 			Comparator getComparator() const {return binaryTree.comparator;}
  21. 		private:
  22. 			Node (const Node&);
  23. 			Node (Node&&);
  24. 			Node& operator= (const Node&);
  25. 			Node& operator= (Node&&);
  26. 			inline std::shared_ptr<Node> insert (BinaryTree&, const T&, std::shared_ptr<Node>&);
  27. 			inline std::shared_ptr<Node> search (const T&, std::shared_ptr<Node>&);
  28. 			inline std::shared_ptr<Node> remove (const T&, std::shared_ptr<Node>&);
  29. 			inline std::shared_ptr<Node> findMaxNode (const std::shared_ptr<Node>&) const;
  30. 			inline std::shared_ptr<Node> removeMaxNode (std::shared_ptr<Node>&, std::shared_ptr<Node>&); 
  31. 			bool isRoot() const {return parent == nullptr;}
  32. 			inline void setLeft (std::shared_ptr<Node>&);
  33. 			inline void setRight (std::shared_ptr<Node>&);
  34. 			inline void setLeftMinus (std::shared_ptr<Node>&);
  35. 			inline void setRightMinus (std::shared_ptr<Node>&);
  36. 			void setLeftSimple (std::shared_ptr<Node>& node) {left = node;  if (node) node->parent = this->shared_from_this();}
  37. 			void setRightSimple (std::shared_ptr<Node>& node) {right = node;  if (node) node->parent = this->shared_from_this();}
  38. 	};
  39. 	template <TreeTraversal, typename = void> struct ExecuteActionHelper;
  40. private:
  41. 	std::shared_ptr<Node> root;
  42. 	const Comparator comparator;
  43. public:
  44. 	BinaryTree (const Comparator& comp = Comparator()) : root(nullptr), comparator(comp) {}
  45. 	BinaryTree (const BinaryTree<T, Comparator>& other) : root(std::shared_ptr<Node>(new Node(*other.root))), comparator(other.comparator) {}  // 'root(std::shared_ptr<Node>(other.root))' would also copy the entire tree, but it would be a shallow copy (no new nodes are being instantiated).
  46. 	BinaryTree (BinaryTree<T, Comparator>&& other) : root(other.root), comparator(other.comparator) {other.root = nullptr;}
  47. 	BinaryTree& operator= (const BinaryTree&);
  48. 	BinaryTree& operator= (BinaryTree&&);
  49. 	std::shared_ptr<Node> insert (const T& t) {return root->insert(*this, t, root);}
  50. 	std::shared_ptr<Node> remove (const T& t) {return root->remove(t, root);}
  51. 	std::shared_ptr<Node> search (const T& t) {std::shared_ptr<Node> node = root->search (t, root);  std::cout << node->value << " found.\n";  return node;}
  52. 	template <TreeTraversal Tr = Preorder, typename F = std::function<void(T)>> void executeAction (const F& f, std::shared_ptr<Node> startingNode) const {executeActionHelper<Tr> (startingNode, f);}
  53. 	template <TreeTraversal Tr = Preorder, typename F = std::function<void(T)>> void executeAction (const F& f) const {executeAction<Tr> (f, root);}
  54. 	inline void display() const;
  55. 	void replaceRoot (std::shared_ptr<Node> node) {root = node;  root->parent = nullptr;}
  56. 	void rotateLeft (std::shared_ptr<Node>&);
  57. 	void rotateRight (std::shared_ptr<Node>&);
  58. 	inline void decreaseDepthFromRoot (std::shared_ptr<Node>& node) {adjustDepthFromRoot(node, -1);}
  59. 	inline void increaseDepthFromRoot (std::shared_ptr<Node>& node) {adjustDepthFromRoot(node, 1);}
  60. private:
  61. 	inline void displayNodeAndChildren (const std::shared_ptr<Node>&) const;
  62. 	template <TreeTraversal Tr, typename F> void executeActionHelper (const std::shared_ptr<Node>& node, const F& f) const {ExecuteActionHelper<Tr>::template execute(node, f);}
  63. 	inline void adjustDepthFromRoot (std::shared_ptr<Node>&, int);
  64. };
  65.  
  66. template <typename T, typename Comparator>
  67. template <typename P>
  68. struct BinaryTree<T, Comparator>::ExecuteActionHelper<BinaryTree<T, Comparator>::Preorder, P> {
  69. 	template <typename F>
  70. 	static void execute (const std::shared_ptr<BinaryTree<T, Comparator>::Node>& node, const F& f) {
  71. 		if (!node)
  72. 			return;
  73. 		f(node->value);
  74. 		execute (node->left, f);
  75. 		execute (node->right, f);
  76. 	}
  77. };
  78.  
  79. template <typename T, typename Comparator>
  80. template <typename P>
  81. struct BinaryTree<T, Comparator>::ExecuteActionHelper<BinaryTree<T, Comparator>::Postorder, P> {
  82. 	template <typename F>
  83. 	static void execute (const std::shared_ptr<BinaryTree<T, Comparator>::Node>& node, const F& f) {
  84. 		if (!node)
  85. 			return;
  86. 		execute (node->left, f);
  87. 		execute (node->right, f);
  88. 		f(node->value);
  89. 	}
  90. };
  91.  
  92. template <typename T, typename Comparator>
  93. template <typename P>
  94. struct BinaryTree<T, Comparator>::ExecuteActionHelper<BinaryTree<T, Comparator>::Inorder, P> {
  95. 	template <typename F>
  96. 	static void execute (const std::shared_ptr<BinaryTree<T, Comparator>::Node>& node, const F& f) {
  97. 		if (!node)
  98. 			return;
  99. 		execute (node->left, f);
  100. 		f(node->value);
  101. 		execute (node->right, f);
  102. 	}
  103. };
  104.  
  105. template <typename T, typename Comparator>
  106. inline std::shared_ptr<typename BinaryTree<T, Comparator>::Node>
  107. BinaryTree<T, Comparator>::Node::insert (BinaryTree& tree, const T& t, std::shared_ptr<Node>& node) {
  108. 	if (!node) {
  109. 		std::shared_ptr<Node> newNode = std::make_shared<Node>(tree, t);
  110. 		node = newNode;
  111. 		return newNode;
  112. 	}
  113. 	if (getComparator()(t, node->value)) {
  114. 		std::shared_ptr<Node> newLeft = insert(tree, t, node->left);
  115. 		node->setLeft(newLeft);
  116. 	}
  117. 	else {
  118. 		std::shared_ptr<Node> newRight = insert(tree, t, node->right);
  119. 		node->setRight(newRight);
  120. 	}
  121. 	return node;
  122. }
  123.  
  124. template <typename T, typename Comparator>
  125. inline std::shared_ptr<typename BinaryTree<T, Comparator>::Node> BinaryTree<T, Comparator>::Node::search (const T& t, std::shared_ptr<Node>& node) {
  126. 	if (getComparator()(t, node->value))
  127. 		return search (t, node->left);
  128. 	else if (getComparator()(node->value, t))
  129. 		return search (t, node->right);
  130. 	else  // Match is found.
  131. 		return node;
  132. }
  133.  
  134. template <typename T, typename Comparator>
  135. inline std::shared_ptr<typename BinaryTree<T, Comparator>::Node> BinaryTree<T, Comparator>::Node::findMaxNode (const std::shared_ptr<Node>& node) const {
  136. 	if (!node)
  137. 		return nullptr;
  138. 	if (!node->right)
  139. 		return node;  // If node has a central node, then return node will still give a node with maximal value since the central node has compares equal to it.
  140. 	return (findMaxNode(node->right));
  141. }
  142.  
  143. template <typename T, typename Comparator>
  144. inline std::shared_ptr<typename BinaryTree<T, Comparator>::Node> BinaryTree<T, Comparator>::Node::removeMaxNode (std::shared_ptr<Node>& node, std::shared_ptr<Node>& maxNode) {
  145. 	if (node == maxNode) {
  146. 		if (maxNode->left)
  147. 			maxNode->left->parent = node;
  148. 		return maxNode->left;
  149. 	}
  150. 	std::shared_ptr<Node> newRight = removeMaxNode (node->right, maxNode);
  151. 	node->setRightMinus(newRight);
  152. 	return node;
  153. }
  154.  
  155. template <typename T, typename Comparator>
  156. inline void BinaryTree<T, Comparator>::adjustDepthFromRoot (std::shared_ptr<Node>& node, int adjustment) {
  157. 	if (!node)
  158. 		return;
  159. 	node->depthFromRoot += adjustment;
  160. 	adjustDepthFromRoot (node->left, adjustment);
  161. 	adjustDepthFromRoot (node->right, adjustment);
  162. }
  163.  
  164. template <typename T, typename Comparator>
  165. inline std::shared_ptr<typename BinaryTree<T, Comparator>::Node> BinaryTree<T, Comparator>::Node::remove (const T& t, std::shared_ptr<Node>& node) {
  166. 	if (getComparator()(t, node->value)) {
  167. 		std::shared_ptr<Node> newLeft = remove(t, node->left);
  168. 		node->setLeftMinus(newLeft);
  169. 	}
  170. 	else if (getComparator()(node->value, t)) {
  171. 		std::shared_ptr<Node> newRight = remove(t, node->right);
  172. 		node->setRightMinus(newRight);
  173. 	}
  174. 	else {  // Match is found.
  175. 		if (!node->left) {  // node has only the right child, or no child.  This might return nullptr if there is no child, but that is what we want anyway.
  176. 			if (node->isRoot())
  177. 				binaryTree.replaceRoot(node->right);
  178. 			binaryTree.decreaseDepthFromRoot(node->right);  // Recursive call for the entire subtree rooted at node->right.
  179. 			return node->right;
  180. 		}
  181. 		if (!node->right) {  // node has only one child, namely a left child (due to the previous if statement).  This this will always return a valid node.
  182. 			if (node->isRoot())
  183. 				binaryTree.replaceRoot(node->left);
  184. 			binaryTree.decreaseDepthFromRoot(node->left);  // Recursive call for the entire subtree rooted at node->left.
  185. 			return node->left;
  186. 		}
  187. 		// Node has two children.
  188. 		std::shared_ptr<Node> maxNode = findMaxNode(node->left),   r = removeMaxNode(node->left, maxNode);
  189. 		maxNode->depthFromRoot = node->depthFromRoot;
  190. 		binaryTree.decreaseDepthFromRoot(maxNode->left);  // Recursive call for the entire subtree rooted at maxNode->left (note that maxNode->right must be nullptr by definition of maxNode).
  191. 		maxNode->setLeftSimple(r);
  192. 		maxNode->setRightMinus(node->right);
  193. 		maxNode->subtreeSize = node->subtreeSize - 1;  // Since maxNode is replacing node's position and hence becomes the new root of the subtree that was rooted at 'node' (with maxNode no longer in that subtree, of course).
  194. 		if (node->isRoot())
  195. 			binaryTree.replaceRoot(maxNode);
  196. 		return maxNode;
  197. 	}
  198. 	return node;
  199. }
  200.  
  201. template <typename T, typename Comparator>
  202. inline void BinaryTree<T, Comparator>::display() const {
  203. 	displayNodeAndChildren(root);  
  204. 	if (root) 
  205. 		std::cout << "Tree Root = " << root->value << "\n\n";
  206. 	else
  207. 		std::cout << "There is no root.\n";
  208. }
  209.  
  210. template <typename T, typename Comparator>
  211. inline void BinaryTree<T, Comparator>::displayNodeAndChildren (const std::shared_ptr<Node>& node) const {
  212. 	if (!node) {
  213. 		std::cout << '\n';
  214. 		return;
  215. 	}
  216. 	const T& t = node->value;
  217. 	std::cout << t << ", subtreeSize = " << node->subtreeSize << ", subtreeHeight = " << node->subtreeHeight << ", depthFromRoot = " << node->depthFromRoot << '\n';
  218. 	if (node->parent) std::cout << t << "'s parent = " << node->parent->value << '\n';  else std::cout << t << "'s parent = nullptr\n";
  219. 	std::cout << t << "'s left = "; 
  220. 	displayNodeAndChildren (node->left);
  221. 	std::cout << t << "'s right = "; 
  222. 	displayNodeAndChildren (node->right);
  223. }
  224.  
  225. template <typename T, typename Comparator>
  226. BinaryTree<T, Comparator>& BinaryTree<T, Comparator>::operator= (const BinaryTree<T, Comparator>& other) {  // BinaryTree assignment operator.
  227. 	std::cout << "BinaryTree assignment operator called.\n";
  228. 	if (this == &other)
  229. 		return *this;
  230. 	root = std::shared_ptr<Node>(new Node(*other.root));
  231. 	return *this;
  232. }
  233.  
  234. template <typename T, typename Comparator>
  235. BinaryTree<T, Comparator>& BinaryTree<T, Comparator>::operator= (BinaryTree<T, Comparator>&& other) {  // BinaryTree move assignment operator.
  236. 	std::cout << "\nBinaryTree move assignment operator called.\n";
  237. 	if (this == &other)
  238. 		return *this;
  239. 	root = other.root;
  240. 	other.root = nullptr;
  241. 	return *this;
  242. }
  243.  
  244. template <typename T, typename Comparator>
  245. BinaryTree<T, Comparator>::Node::Node (const BinaryTree<T, Comparator>::Node& other) : std::enable_shared_from_this<Node>(), binaryTree(other.binaryTree), value(other.value) {  // Node copy constructor.
  246. 	if (other.left) left = std::shared_ptr<Node>(new Node(*other.left));  // Each child invokes the Node copy constructor recursively.  New shared_ptrs are created, thereby resulting in a deep BinaryTree copy, rather than a shallow copy.
  247. 	if (other.right) right = std::shared_ptr<Node>(new Node(*other.right));
  248. }
  249.  
  250. template <typename T, typename Comparator>
  251. typename BinaryTree<T, Comparator>::Node& BinaryTree<T, Comparator>::Node::operator= (const BinaryTree<T, Comparator>::Node& other) {  // Node assignment operator.
  252. 	if (this == &other)
  253. 		return *this;
  254. 	value = other.value;
  255. 	if (other.left) left = std::shared_ptr<Node>(new Node(*other.left));  // Node copy constructor called.  Previously owned node is deleted automatically.
  256. 	if (other.right) right = std::shared_ptr<Node>(new Node(*other.right));
  257. 	return *this;
  258. }
  259.  
  260. template <typename T, typename Comparator>
  261. BinaryTree<T, Comparator>::Node::Node (BinaryTree<T, Comparator>::Node&& other) : std::enable_shared_from_this<Node>(), binaryTree(other.binaryTree), value(other.value),
  262. 		left(std::shared_ptr<Node>(new Node(*other.left))), right(std::shared_ptr<Node>(new Node(*other.right))) {  // Node move constructor.
  263. 	other.left = nullptr;
  264. 	other.right = nullptr;
  265. }
  266.  
  267. template <typename T, typename Comparator>
  268. typename BinaryTree<T, Comparator>::Node& BinaryTree<T, Comparator>::Node::operator= (BinaryTree<T, Comparator>::Node&& other) {  // Node move assignment operator.
  269. 	if (this == &other)
  270. 		return *this;
  271. 	value = other.value;
  272. 	left = std::shared_ptr<Node>(new Node(*other.left));
  273. 	right = std::shared_ptr<Node>(new Node(*other.right));
  274. 	other.left = nullptr;
  275. 	other.right = nullptr;
  276. 	return *this;
  277. }
  278.  
  279. template <typename T, typename Comparator>
  280. inline void BinaryTree<T, Comparator>::Node::setLeft (std::shared_ptr<Node>& node) {
  281. 	const std::size_t formerLeftSubtreeSize = left ? left->subtreeSize : 0;
  282. 	left = node;
  283. 	if (node) {
  284. 		node->parent = this->shared_from_this();
  285. 		subtreeSize++;
  286. 		node->depthFromRoot = depthFromRoot + 1;  // This line does not appear in Node::setLeftMinus.
  287. 		const std::size_t h = node->subtreeHeight;
  288. 		if (right)
  289. 			subtreeHeight = std::max (right->subtreeHeight, h) + 1;
  290. 		else
  291. 			subtreeHeight = h + 1;
  292. 	}
  293. 	else {
  294. 		subtreeSize -= formerLeftSubtreeSize;
  295. 		subtreeHeight = right ? right->subtreeHeight + 1 : 0;
  296. 	}
  297. }
  298.  
  299. template <typename T, typename Comparator>
  300. inline void BinaryTree<T, Comparator>::Node::setRight (std::shared_ptr<Node>& node) {
  301. 	const std::size_t formerRightSubtreeSize = right ? right->subtreeSize : 0;
  302. 	right = node;
  303. 	if (node) {
  304. 		node->parent = this->shared_from_this();
  305. 		subtreeSize++;
  306. 		node->depthFromRoot = depthFromRoot + 1;  // This line does not appear in Node::setRightMinus.
  307. 		const std::size_t h = node->subtreeHeight;
  308. 		if (left)
  309. 			subtreeHeight = std::max (left->subtreeHeight, h) + 1;
  310. 		else
  311. 			subtreeHeight = h + 1;
  312. 	}
  313. 	else {
  314. 		subtreeSize -= formerRightSubtreeSize;
  315. 		subtreeHeight = left ? left->subtreeHeight + 1 : 0;
  316. 	}
  317. }
  318.  
  319. template <typename T, typename Comparator>
  320. inline void BinaryTree<T, Comparator>::Node::setLeftMinus (std::shared_ptr<Node>& node) {
  321. 	const std::size_t formerLeftSubtreeSize = left ? left->subtreeSize : 0;
  322. 	left = node;
  323. 	if (node) {
  324. 		node->parent = this->shared_from_this();
  325. 		subtreeSize--;
  326. 		const std::size_t h = node->subtreeHeight;
  327. 		if (right)
  328. 			subtreeHeight = std::max (right->subtreeHeight, h) + 1;
  329. 		else
  330. 			subtreeHeight = h + 1;
  331. 	}
  332. 	else {
  333. 		subtreeSize -= formerLeftSubtreeSize;
  334. 		subtreeHeight = right ? right->subtreeHeight + 1 : 0;
  335. 	}
  336. }
  337.  
  338. template <typename T, typename Comparator>
  339. inline void BinaryTree<T, Comparator>::Node::setRightMinus (std::shared_ptr<Node>& node) {
  340. 	const std::size_t formerRightSubtreeSize = right ? right->subtreeSize : 0;
  341. 	right = node;
  342. 	if (node) {
  343. 		node->parent = this->shared_from_this();
  344. 		subtreeSize--;
  345. 		const std::size_t h = node->subtreeHeight;
  346. 		if (left)
  347. 			subtreeHeight = std::max (left->subtreeHeight, h) + 1;
  348. 		else
  349. 			subtreeHeight = h + 1;
  350. 	}
  351. 	else {
  352. 		subtreeSize -= formerRightSubtreeSize;
  353. 		subtreeHeight = left ? left->subtreeHeight + 1 : 0;
  354. 	}
  355. }
  356.  
  357. template <typename T, typename Comparator>
  358. void BinaryTree<T, Comparator>::rotateLeft (std::shared_ptr<Node>& node) {  // The root of the rotation is 'node', and its right child is the pivot of the rotation.  The pivot will rotate counter-clockwise and become the new parent of 'node'.
  359. 	std::shared_ptr<Node> pivot = node->right;
  360. 	pivot->subtreeSize = node->subtreeSize;
  361. 	pivot->depthFromRoot--;
  362. 	node->subtreeSize--;  // Since 'pivot' will no longer be in the subtree rooted at 'node'.
  363. 	const std::size_t a = pivot->left ? pivot->left->subtreeHeight + 1 : 0;  // Need to establish node->heightOfSubtree before pivot->heightOfSubtree is established, since pivot->heightOfSubtree depends on it.
  364. 	node->subtreeHeight = node->left ? std::max(a, node->left->subtreeHeight + 1) : std::max<std::size_t>(a,1);
  365. 	if (pivot->right) {
  366. 		node->subtreeSize -= pivot->right->subtreeSize;  // The subtree rooted at 'node' loses the subtree rooted at pivot->right.
  367. 		pivot->subtreeHeight = std::max (pivot->right->subtreeHeight, node->subtreeHeight) + 1;
  368. 	}
  369. 	else
  370. 		pivot->subtreeHeight = node->subtreeHeight + 1;
  371. 	node->depthFromRoot++;
  372. 	decreaseDepthFromRoot(pivot->right);  // Recursive call for the entire subtree rooted at pivot->right.
  373. 	increaseDepthFromRoot(node->left);  // Recursive call for the entire subtree rooted at node->left.
  374. 	pivot->parent = node->parent;
  375. 	if (pivot->parent) {  // pivot's new parent will be its former grandparent, which is not nullptr, so the grandparent must be updated with a new left or right child (depending on whether 'node' was its left or right child).
  376. 		if (pivot->parent->left == node)
  377. 			pivot->parent->left = pivot;
  378. 		else
  379. 			pivot->parent->right = pivot;
  380. 	}
  381. 	node->setRightSimple(pivot->left);  // Since pivot->left->value is less than pivot->value but greater than node->value.  We use the NoSizeAdjustment version because the 'subtreeSize' values of 'node' and 'pivot' are correct already.
  382. 	pivot->setLeftSimple(node);
  383. 	if (node == root) {
  384. 		root = pivot;
  385. 		root->parent = nullptr;	
  386. 	}
  387. }
  388.  
  389. template <typename T, typename Comparator>
  390. void BinaryTree<T, Comparator>::rotateRight (std::shared_ptr<Node>& node) {  // The root of the rotation is 'node', and its left child is the pivot of the rotation.  The pivot will rotate clockwise and become the new parent of 'node'.
  391. 	std::shared_ptr<Node> pivot = node->left;
  392. 	pivot->subtreeSize = node->subtreeSize;
  393. 	pivot->depthFromRoot--;
  394. 	node->subtreeSize--;  // Since 'pivot' will no longer be in the subtree rooted at 'node'.
  395. 	const std::size_t a = pivot->right ? pivot->right->subtreeHeight + 1 : 0;  // Need to establish node->heightOfSubtree before pivot->heightOfSubtree is established, since pivot->heightOfSubtree depends on it.
  396. 	node->subtreeHeight = node->right ? std::max(a, node->right->subtreeHeight + 1) : std::max<std::size_t>(a,1);
  397. 	if (pivot->left) {
  398. 		node->subtreeSize -= pivot->left->subtreeSize;  // The subtree rooted at 'node' loses the subtree rooted at pivot->left.
  399. 		pivot->subtreeHeight = std::max (pivot->left->subtreeHeight, node->subtreeHeight) + 1;
  400. 	}
  401. 	else
  402. 		pivot->subtreeHeight = node->subtreeHeight + 1;
  403. 	node->depthFromRoot++;
  404. 	decreaseDepthFromRoot(pivot->left);  // Recursive call for the entire subtree rooted at pivot->left.
  405. 	increaseDepthFromRoot(node->right);  // Recursive call for the entire subtree rooted at node->right.
  406. 	pivot->parent = node->parent;
  407. 	if (pivot->parent) {  // pivot's new parent will be its former grandparent, which is not nullptr, so the grandparent must be updated with a new left or right child (depending on whether 'node' was its left or right child).
  408. 		if (pivot->parent->left == node)
  409. 			pivot->parent->left = pivot;
  410. 		else
  411. 			pivot->parent->right = pivot;
  412. 	}
  413. 	node->setLeftSimple(pivot->right);  // Since pivot->right->value is greater than pivot->value but less than node->value.
  414. 	pivot->setRightSimple(node);
  415. 	if (node == root) {
  416. 		root = pivot;
  417. 		root->parent = nullptr;	
  418. 	}
  419. }
  420.  
  421. // Testing
  422. struct StringComparator {
  423. 	bool operator ()(const std::string& a, const std::string& b) const {return a.compare(b) < 0;}
  424. };
  425.  
  426. const std::string names[] = {"Mahnoor", "Aiman", "Zarish", "Ifrah", "Zumer", "Theebika", "Zoya", "Nabela", "Afrah", "Ashna", "Saleha", "Bapisha"};
  427.  
  428. BinaryTree<std::string, StringComparator> makeBinaryTree() {
  429. 	BinaryTree<std::string, StringComparator> tree;
  430. 	for (const std::string& s : names)
  431. 		tree.insert(s);
  432. 	return tree;
  433. }
  434.  
  435. template <typename Tree>
  436. void rotateRightTest (Tree& tree, const std::string& name) {
  437. 	auto node = tree.search(name);
  438. 	tree.rotateRight(node);
  439. 	std::cout << "\n'tree.rotateRight(" << name << ");' called.\n\n";
  440. 	tree.display();
  441. }
  442.  
  443. template <typename Tree>
  444. void rotateLeftTest (Tree& tree, const std::string& name) {
  445. 	auto node = tree.search(name);
  446. 	tree.rotateLeft(node);
  447. 	std::cout << "\n'tree.rotateLeft(" << name << ");' called.\n\n";
  448. 	tree.display();
  449. }
  450.  
  451. int main() {
  452. 	BinaryTree<std::string, StringComparator> tree = makeBinaryTree();
  453. 	tree.display();
  454.  
  455. //	tree.remove("Zoya");  std::cout << "\n\nZoya removed:\n";  tree.display();  // Removing a node with no children (everything passed).
  456. //	tree.remove("Saleha");  std::cout << "\n\nSaleha removed:\n";  tree.display();  // Removing a node with no children (everything passed).
  457. //	tree.remove("Theebika");  std::cout << "\n\nTheebika removed:\n";  tree.display();  // Removing a node with one child (everything passed).
  458. //	tree.remove("Aiman");  std::cout << "\n\nAiman removed:\n";  tree.display();  // Removing a node with two children (everything passed).
  459. //	tree.remove("Zarish");  std::cout << "\n\nZarish removed:\n";  tree.display();  // Removing a node with two children (everything passed).
  460. //	tree.remove("Mahnoor");  std::cout << "\n\nMahnoor removed:\n";   tree.display();  // Removing the root of the tree (everything passed).
  461.  
  462. //	rotateRightTest (tree, "Zarish");  // Everything passed.
  463. //	rotateRightTest (tree, "Mahnoor");  // Everything passed.
  464. //	rotateLeftTest (tree, "Aiman");  // Everything passed.
  465. 	rotateLeftTest (tree, "Mahnoor");  // Everything passed.
  466. }
Success #stdin #stdout 0s 3484KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Mahnoor, subtreeSize = 12, subtreeHeight = 4, depthFromRoot = 0
Mahnoor's parent = nullptr
Mahnoor's left = Aiman, subtreeSize = 5, subtreeHeight = 3, depthFromRoot = 1
Aiman's parent = Mahnoor
Aiman's left = Afrah, subtreeSize = 1, subtreeHeight = 0, depthFromRoot = 2
Afrah's parent = Aiman
Afrah's left = 
Afrah's right = 
Aiman's right = Ifrah, subtreeSize = 3, subtreeHeight = 2, depthFromRoot = 2
Ifrah's parent = Aiman
Ifrah's left = Ashna, subtreeSize = 2, subtreeHeight = 1, depthFromRoot = 3
Ashna's parent = Ifrah
Ashna's left = 
Ashna's right = Bapisha, subtreeSize = 1, subtreeHeight = 0, depthFromRoot = 4
Bapisha's parent = Ashna
Bapisha's left = 
Bapisha's right = 
Ifrah's right = 
Mahnoor's right = Zarish, subtreeSize = 6, subtreeHeight = 3, depthFromRoot = 1
Zarish's parent = Mahnoor
Zarish's left = Theebika, subtreeSize = 3, subtreeHeight = 2, depthFromRoot = 2
Theebika's parent = Zarish
Theebika's left = Nabela, subtreeSize = 2, subtreeHeight = 1, depthFromRoot = 3
Nabela's parent = Theebika
Nabela's left = 
Nabela's right = Saleha, subtreeSize = 1, subtreeHeight = 0, depthFromRoot = 4
Saleha's parent = Nabela
Saleha's left = 
Saleha's right = 
Theebika's right = 
Zarish's right = Zumer, subtreeSize = 2, subtreeHeight = 1, depthFromRoot = 2
Zumer's parent = Zarish
Zumer's left = Zoya, subtreeSize = 1, subtreeHeight = 0, depthFromRoot = 3
Zoya's parent = Zumer
Zoya's left = 
Zoya's right = 
Zumer's right = 
Tree Root = Mahnoor

Mahnoor found.

'tree.rotateLeft(Mahnoor);' called.

Zarish, subtreeSize = 12, subtreeHeight = 5, depthFromRoot = 0
Zarish's parent = nullptr
Zarish's left = Mahnoor, subtreeSize = 9, subtreeHeight = 4, depthFromRoot = 1
Mahnoor's parent = Zarish
Mahnoor's left = Aiman, subtreeSize = 5, subtreeHeight = 3, depthFromRoot = 2
Aiman's parent = Mahnoor
Aiman's left = Afrah, subtreeSize = 1, subtreeHeight = 0, depthFromRoot = 3
Afrah's parent = Aiman
Afrah's left = 
Afrah's right = 
Aiman's right = Ifrah, subtreeSize = 3, subtreeHeight = 2, depthFromRoot = 3
Ifrah's parent = Aiman
Ifrah's left = Ashna, subtreeSize = 2, subtreeHeight = 1, depthFromRoot = 4
Ashna's parent = Ifrah
Ashna's left = 
Ashna's right = Bapisha, subtreeSize = 1, subtreeHeight = 0, depthFromRoot = 5
Bapisha's parent = Ashna
Bapisha's left = 
Bapisha's right = 
Ifrah's right = 
Mahnoor's right = Theebika, subtreeSize = 3, subtreeHeight = 2, depthFromRoot = 2
Theebika's parent = Mahnoor
Theebika's left = Nabela, subtreeSize = 2, subtreeHeight = 1, depthFromRoot = 3
Nabela's parent = Theebika
Nabela's left = 
Nabela's right = Saleha, subtreeSize = 1, subtreeHeight = 0, depthFromRoot = 4
Saleha's parent = Nabela
Saleha's left = 
Saleha's right = 
Theebika's right = 
Zarish's right = Zumer, subtreeSize = 2, subtreeHeight = 1, depthFromRoot = 1
Zumer's parent = Zarish
Zumer's left = Zoya, subtreeSize = 1, subtreeHeight = 0, depthFromRoot = 2
Zoya's parent = Zumer
Zoya's left = 
Zoya's right = 
Zumer's right = 
Tree Root = Zarish
https://ideone.com/d6arrv
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!