Tree traversal done in C++

It's not too bad since I worked it out in Java. I didn't use recursive
functions at all to avoid stack overflow issues. Instead, I worked it
out using loop with stacks and queues. Lots of fun!

2 files changed, 196 insertions, 97 deletions

diff --git a/.settings/language.settings.xml b/.settings/language.settings.xml
index 4e9d73d..e532fea 100644
--- a/.settings/language.settings.xml
+++ b/.settings/language.settings.xml
@@ -5,7 +5,7 @@
 			<provider copy-of="extension" id="org.eclipse.cdt.ui.UserLanguageSettingsProvider"/>
 			<provider-reference id="org.eclipse.cdt.core.ReferencedProjectsLanguageSettingsProvider" ref="shared-provider"/>
 			<provider-reference id="org.eclipse.cdt.managedbuilder.core.MBSLanguageSettingsProvider" ref="shared-provider"/>
-			<provider class="org.eclipse.cdt.managedbuilder.language.settings.providers.GCCBuiltinSpecsDetector" console="false" env-hash="-939090329124603581" id="org.eclipse.cdt.managedbuilder.core.GCCBuiltinSpecsDetector" keep-relative-paths="false" name="CDT GCC Built-in Compiler Settings" parameter="${COMMAND} ${FLAGS} -E -P -v -dD &quot;${INPUTS}&quot;" prefer-non-shared="true">
+			<provider class="org.eclipse.cdt.managedbuilder.language.settings.providers.GCCBuiltinSpecsDetector" console="false" env-hash="-938732924838427581" id="org.eclipse.cdt.managedbuilder.core.GCCBuiltinSpecsDetector" keep-relative-paths="false" name="CDT GCC Built-in Compiler Settings" parameter="${COMMAND} ${FLAGS} -E -P -v -dD &quot;${INPUTS}&quot;" prefer-non-shared="true">
 				<language-scope id="org.eclipse.cdt.core.gcc"/>
 				<language-scope id="org.eclipse.cdt.core.g++"/>
 			</provider>
@@ -16,7 +16,7 @@
 			<provider copy-of="extension" id="org.eclipse.cdt.ui.UserLanguageSettingsProvider"/>
 			<provider-reference id="org.eclipse.cdt.core.ReferencedProjectsLanguageSettingsProvider" ref="shared-provider"/>
 			<provider-reference id="org.eclipse.cdt.managedbuilder.core.MBSLanguageSettingsProvider" ref="shared-provider"/>
-			<provider class="org.eclipse.cdt.managedbuilder.language.settings.providers.GCCBuiltinSpecsDetector" console="false" env-hash="-939090329124603581" id="org.eclipse.cdt.managedbuilder.core.GCCBuiltinSpecsDetector" keep-relative-paths="false" name="CDT GCC Built-in Compiler Settings" parameter="${COMMAND} ${FLAGS} -E -P -v -dD &quot;${INPUTS}&quot;" prefer-non-shared="true">
+			<provider class="org.eclipse.cdt.managedbuilder.language.settings.providers.GCCBuiltinSpecsDetector" console="false" env-hash="-938732924838427581" id="org.eclipse.cdt.managedbuilder.core.GCCBuiltinSpecsDetector" keep-relative-paths="false" name="CDT GCC Built-in Compiler Settings" parameter="${COMMAND} ${FLAGS} -E -P -v -dD &quot;${INPUTS}&quot;" prefer-non-shared="true">
 				<language-scope id="org.eclipse.cdt.core.gcc"/>
 				<language-scope id="org.eclipse.cdt.core.g++"/>
 			</provider>
diff --git a/Sources/DataStructure.cpp b/Sources/DataStructure.cpp
index 5cfb53c..4c0379b 100644
--- a/Sources/DataStructure.cpp
+++ b/Sources/DataStructure.cpp
@@ -1,117 +1,216 @@
 #include <iostream>
-#include <string>
 #include <vector>
+#include <algorithm>
+#include <stack>
+#include <queue>
+#include <unordered_set>
 //#include <gtest/gtest.h>
+//#if defined(__unix__) || defined(__APPLE__)
+//#include <sys/resource.h>
+//#endif
 
-using std::string;
-typedef unsigned long long ull;
+using std::vector;
+using std::ios_base;
+using std::cin;
+using std::cout;
 
-struct Data {
-	string pattern, text;
-};
-
-Data read_input() {
-	Data data;
-	std::cin >> data.pattern >> data.text;
-	return data;
-}
-
-void print_occurrences(const std::vector<int>& output) {
-	for (size_t i = 0; i < output.size(); ++i)
-		std::cout << output[i] << " ";
-	std::cout << "\n";
-}
-
-std::vector<int> get_occurrences(const Data& input) {
-	const string& s = input.pattern, t = input.text;
-	std::vector<int> ans;
-	for (size_t i = 0; i + s.size() <= t.size(); ++i)
-		if (t.substr(i, s.size()) == s)
-			ans.push_back(i);
-	return ans;
-}
+class TreeOrders {
+public:
+	int n;
+	vector<int> key;
+	vector<int> left;
+	vector<int> right;
 
-ull poly_hash(string& S, int p, int x) {
-	ull hash = 0;
+	void read() {
+		cin >> n;
+		key.resize(n);
+		left.resize(n);
+		right.resize(n);
+		for (int i = 0; i < n; i++) {
+			cin >> key[i] >> left[i] >> right[i];
+		}
+	}
 
-	for (int i = S.size() - 1; i >= 0; --i)
-		hash = (hash * x + S[i]) % p;
-	return hash;
-}
+	vector<int> in_order() {
+		std::stack<int> keyIndexStack;
+		vector<int> result;
+		bool walkLeft = true;
+		int currentIndex = 0;
+		keyIndexStack.push(currentIndex);
+		while (!keyIndexStack.empty() || right[currentIndex] != -1) {
+			if (walkLeft) {
+				if (left[currentIndex] != -1) {
+					currentIndex = left[currentIndex];
+					keyIndexStack.push(currentIndex);
+				} else {
+					result.push_back(key[keyIndexStack.top()]);
+					keyIndexStack.pop();
+					walkLeft = false;
+				}
+			} else {
+				if (right[currentIndex] != -1) {
+					currentIndex = right[currentIndex];
+					keyIndexStack.push(currentIndex);
+					walkLeft = true;
+				} else {
+					if (!keyIndexStack.empty()) {
+						currentIndex = keyIndexStack.top();
+						keyIndexStack.pop();
+						result.push_back(key[currentIndex]);
+					}
+				}
+			}
+		}
+		return result;
+	}
 
-std::vector<ull> pre_compute_hashes(string& T, int pattenLength, int p, int x) {
-	std::vector<ull> H(T.size() - pattenLength + 1);
-	string S = T.substr(T.size() - pattenLength);
-	H[T.size() - pattenLength] = poly_hash(S, p, x);
-	ull y = 1;
-	for (int i = 0; i < pattenLength; i++) {
-		y = (y * x) % p;
+	vector<int> pre_order() {
+		vector<int> result;
+		std::stack<int> keyIndexStack;
+		std::queue<int> keyIndexQueue;
+		bool walkLeft = true;
+		int currentIndex = 0;
+		keyIndexStack.push(currentIndex);
+		keyIndexQueue.push(currentIndex);
+		while (!keyIndexStack.empty() || right[currentIndex] != -1) {
+			if (walkLeft) {
+				if (left[currentIndex] != -1) {
+					currentIndex = left[currentIndex];
+					keyIndexQueue.push(currentIndex);
+					keyIndexStack.push(currentIndex);
+				} else {
+					keyIndexStack.pop();
+					walkLeft = false;
+					result.push_back(key[keyIndexQueue.front()]);
+					keyIndexQueue.pop();
+				}
+			} else {
+				if (right[currentIndex] != -1) {
+					currentIndex = right[currentIndex];
+					keyIndexQueue.push(currentIndex);
+					keyIndexStack.push(currentIndex);
+					walkLeft = true;
+				} else {
+					if (!keyIndexStack.empty()) {
+						currentIndex = keyIndexStack.top();
+						keyIndexStack.pop();
+						result.push_back(key[keyIndexQueue.front()]);
+						keyIndexQueue.pop();
+					}
+				}
+			}
+		}
+		return result;
 	}
-	for (int i = T.size() - pattenLength - 1; i >= 0; --i) {
-		H[i] = (x * H[i + 1] + T[i] - y * T[i + pattenLength]) % p;
+
+	vector<int> post_order() {
+		vector<int> result;
+		std::stack<int> keyIndexStack;
+		std::unordered_set<int> peekedSet;
+		bool walkLeft = true;
+		int currentIndex = 0;
+		keyIndexStack.push(currentIndex);
+		while (!keyIndexStack.empty()) {
+			auto search = peekedSet.find(currentIndex);
+			if (search != peekedSet.end()) {
+				result.push_back(key[currentIndex]);
+				peekedSet.erase(currentIndex);
+				keyIndexStack.pop();
+				if (keyIndexStack.empty())
+					break;
+				currentIndex = keyIndexStack.top();
+				continue;
+			}
+			if (walkLeft) {
+				if (left[currentIndex] != -1) {
+					currentIndex = left[currentIndex];
+					keyIndexStack.push(currentIndex);
+				} else {
+					if (right[currentIndex] == -1) {
+						result.push_back(key[currentIndex]);
+						walkLeft = false;
+						keyIndexStack.pop();
+						currentIndex = keyIndexStack.top();
+					} else {
+						peekedSet.insert(currentIndex);
+						currentIndex = right[currentIndex];
+						keyIndexStack.push(currentIndex);
+					}
+				}
+			} else {
+				if (right[currentIndex] != -1) {
+					peekedSet.insert(currentIndex);
+					currentIndex = right[currentIndex];
+					keyIndexStack.push(currentIndex);
+					walkLeft = true;
+				} else {
+					result.push_back(key[currentIndex]);
+					int i = keyIndexStack.top();
+					keyIndexStack.pop();
+					if (i != currentIndex)
+						result.push_back(key[i]);
+					if (keyIndexStack.empty())
+						break;
+					currentIndex = keyIndexStack.top();
+				}
+			}
+		}
+		return result;
 	}
-	return H;
-}
+};
 
-std::vector<int> rabin_karp(const Data& input) {
-	string T = input.text;
-	string P = input.pattern;
-	int p = 1000000007;
-	int x = 1 + (rand() % static_cast<int>(1000000006));
-	std::vector<int> positions;
-	ull pHash = poly_hash(P, p, x);
-	std::vector<ull> H = pre_compute_hashes(T, P.size(), p, x);
-	for (size_t i = 0; i < T.size() - P.size() + 1; i++) {
-		if (pHash != H[i]) {
-			continue;
+void print(vector<int> a) {
+	for (size_t i = 0; i < a.size(); i++) {
+		if (i > 0) {
+			cout << ' ';
 		}
-		if (T.compare(i, P.size(), P) == 0)
-			positions.push_back(i);
+		cout << a[i];
 	}
-	return positions;
+	cout << '\n';
 }
-//TEST(RabinKarp, t) {
-//	Data data;
-//	data.pattern = "a";
-//	data.text = "ab";
-//	std::vector<int> results = rabin_karp(data);
-//
-//	ASSERT_EQ(1, results.size());
-//	ASSERT_EQ(0, results[0]);
-//
-//	data.pattern = "aba";
-//	data.text = "abacaba";
-//	results = rabin_karp(data);
-//
-//	ASSERT_EQ(2, results.size());
-//	ASSERT_EQ(0, results[0]);
-//	ASSERT_EQ(4, results[1]);
-//}
+
+//TEST(TreeTraversal, t) {
+//	TreeOrders t;
+//	t.key = {4, 2, 5, 1, 3};
+//	t.left = {1, 3, -1, -1, -1};
+//	t.right = {2, 4, -1, -1, -1};
 //
-//TEST(RabinKarp, t1) {
-//	Data data;
-//	data.pattern = "Test";
-//	data.text = "testTesttesT";
-//	std::vector<int> results = rabin_karp(data);
+//	vector<int> results = t.in_order();
+//	ASSERT_EQ(5, results.size());
+//	ASSERT_EQ(1, results[0]);
+//	ASSERT_EQ(2, results[1]);
+//	ASSERT_EQ(3, results[2]);
+//	ASSERT_EQ(4, results[3]);
+//	ASSERT_EQ(5, results[4]);
 //
-//	ASSERT_EQ(1, results.size());
+//	results = t.pre_order();
+//	ASSERT_EQ(5, results.size());
 //	ASSERT_EQ(4, results[0]);
-//}
-//
-//TEST(RabinKarp, t2) {
-//	Data data;
-//	data.pattern = "aaaaa";
-//	data.text = "baaaaaaa";
-//	std::vector<int> results = rabin_karp(data);
+//	ASSERT_EQ(2, results[1]);
+//	ASSERT_EQ(1, results[2]);
+//	ASSERT_EQ(3, results[3]);
+//	ASSERT_EQ(5, results[4]);
 //
-//	ASSERT_EQ(3, results.size());
+//	results = t.post_order();
+//	ASSERT_EQ(5, results.size());
 //	ASSERT_EQ(1, results[0]);
-//	ASSERT_EQ(2, results[1]);
-//	ASSERT_EQ(3, results[2]);
+//	ASSERT_EQ(3, results[1]);
+//	ASSERT_EQ(2, results[2]);
+//	ASSERT_EQ(5, results[3]);
+//	ASSERT_EQ(4, results[4]);
 //}
 
-int main() {
-    std::ios_base::sync_with_stdio(false);
-    print_occurrences(rabin_karp(read_input()));
-    return 0;
+int main_with_large_stack_space() {
+	ios_base::sync_with_stdio(0);
+	TreeOrders t;
+	t.read();
+	print(t.in_order());
+	print(t.pre_order());
+	print(t.post_order());
+	return 0;
+}
+
+int main (int argc, char **argv)
+{
+  return main_with_large_stack_space();
 }