From 1d2b8a1f4184569e166cc7cab0316bb0259c86d6 Mon Sep 17 00:00:00 2001 From: Haidong Ji Date: Sun, 9 Jun 2019 22:04:26 -0500 Subject: 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!--- .settings/language.settings.xml | 4 +- Sources/DataStructure.cpp | 289 +++++++++++++++++++++++++++------------- 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 @@ - + @@ -16,7 +16,7 @@ - + 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 -#include #include +#include +#include +#include +#include //#include +//#if defined(__unix__) || defined(__APPLE__) +//#include +//#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& output) { - for (size_t i = 0; i < output.size(); ++i) - std::cout << output[i] << " "; - std::cout << "\n"; -} - -std::vector get_occurrences(const Data& input) { - const string& s = input.pattern, t = input.text; - std::vector 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 key; + vector left; + vector 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 in_order() { + std::stack keyIndexStack; + vector 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 pre_compute_hashes(string& T, int pattenLength, int p, int x) { - std::vector 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 pre_order() { + vector result; + std::stack keyIndexStack; + std::queue 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 post_order() { + vector result; + std::stack keyIndexStack; + std::unordered_set 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 rabin_karp(const Data& input) { - string T = input.text; - string P = input.pattern; - int p = 1000000007; - int x = 1 + (rand() % static_cast(1000000006)); - std::vector positions; - ull pHash = poly_hash(P, p, x); - std::vector 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 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 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 results = rabin_karp(data); +// vector 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 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(); } -- cgit v1.2.3