fork download
copy 
  1. #include <iostream>
  2. #include <string>
  3. #include <stack>
  4.  
  5.  
  6. class BST
  7. {
  8. private:
  9. 	typedef struct structNode
  10. 	{
  11. 		std::string mData;
  12. 		structNode *mLeft;
  13. 		structNode *mRight;
  14.  
  15. 		structNode(std::string&& data, structNode* left = nullptr, structNode* right = nullptr) : mData(data), mLeft{ left }, mRight{ right }
  16. 		{
  17. 		}
  18.  
  19. 	}Node;
  20.  
  21. 	Node* mRoot;
  22.  
  23. public:
  24.  
  25. 	BST() : mRoot(nullptr) {}
  26.  
  27. 	void Insert(std::string&& data)
  28. 	{
  29. 		Node **ptr = &mRoot;
  30.  
  31. 		while (*ptr != nullptr)
  32. 		{
  33. 			if ((*ptr)->mData.compare(data) >= 0)
  34. 				ptr = &((*ptr)->mLeft);
  35. 			else
  36. 				ptr = &((*ptr)->mRight);
  37. 		}
  38.  
  39. 		*ptr = new Node(std::move(data));
  40. 		return;
  41. 	}
  42.  
  43. 	void PrintPostOrder()
  44. 	{
  45. 		std::stack<Node*> stack{};
  46. 		Node* iter = mRoot;
  47. 		Node* pIter = nullptr;
  48.  
  49. 		while (iter || !stack.empty())
  50. 		{
  51. 			if (iter && iter != pIter)
  52. 			{
  53. 				stack.push(iter);
  54. 				iter = iter->mLeft;
  55. 			}
  56. 			else
  57. 			{
  58. 				if (stack.top()->mRight && stack.top()->mRight != pIter)
  59. 				{
  60. 					iter = stack.top()->mRight;
  61. 				}
  62. 				else
  63. 				{
  64. 					pIter = stack.top();
  65. 					std::cout << "[ " << stack.top()->mData << " ], ";
  66. 					stack.pop();
  67. 					iter = nullptr;
  68.  
  69. 					if (!stack.empty())
  70. 						iter = stack.top()->mRight;
  71. 				}
  72. 			}
  73. 		}
  74. 	}
  75.  
  76. };
  77.  
  78.  
  79. int main() {
  80. 		BST bst3{};
  81.  
  82. 	bst3.Insert(std::string("f"));
  83. 	bst3.Insert(std::string("d"));
  84. 	bst3.Insert(std::string("j"));
  85. 	bst3.Insert(std::string("b"));
  86. 	bst3.Insert(std::string("e"));
  87. 	bst3.Insert(std::string("g"));
  88. 	bst3.Insert(std::string("l"));
  89. 	bst3.Insert(std::string("k"));
  90. 	bst3.Insert(std::string("m"));
  91. 	bst3.Insert(std::string("a"));
  92. 	bst3.Insert(std::string("c"));
  93. 	bst3.Insert(std::string("i"));
  94. 	bst3.Insert(std::string("h"));
  95.  
  96. 	bst3.PrintPostOrder();
  97. 	return 0;
  98. }
Success #stdin #stdout 0s 3276KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
[ a ], [ c ], [ b ], [ e ], [ d ], [ h ], [ i ], [ g ], [ k ], [ m ], [ l ], [ j ], [ f ],
https://ideone.com/8eU1gk
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!