diff options
| -rw-r--r-- | Sources/DataStructure.cpp | 126 |
1 files changed, 20 insertions, 106 deletions
diff --git a/Sources/DataStructure.cpp b/Sources/DataStructure.cpp index 4c0379b..ebb4c2e 100644 --- a/Sources/DataStructure.cpp +++ b/Sources/DataStructure.cpp @@ -2,17 +2,13 @@ #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::vector; using std::ios_base; using std::cin; using std::cout; +using std::endl; class TreeOrders { public: @@ -31,7 +27,8 @@ public: } } - vector<int> in_order() { + bool is_Bst() { + if (key.size()==0) return true; std::stack<int> keyIndexStack; vector<int> result; bool walkLeft = true; @@ -40,15 +37,21 @@ public: while (!keyIndexStack.empty() || right[currentIndex] != -1) { if (walkLeft) { if (left[currentIndex] != -1) { + if (key[left[currentIndex]] >= key[currentIndex]) return false; currentIndex = left[currentIndex]; keyIndexStack.push(currentIndex); } else { - result.push_back(key[keyIndexStack.top()]); - keyIndexStack.pop(); - walkLeft = false; + int i = keyIndexStack.top(); + keyIndexStack.pop(); + if (result.size() > 0) { + if (key[i] <= result[(result.size()-1)]) return false; + } + result.push_back(key[i]); + walkLeft = false; } } else { if (right[currentIndex] != -1) { + if (key[right[currentIndex]] <= key[currentIndex]) return false; currentIndex = right[currentIndex]; keyIndexStack.push(currentIndex); walkLeft = true; @@ -56,107 +59,17 @@ public: if (!keyIndexStack.empty()) { currentIndex = keyIndexStack.top(); keyIndexStack.pop(); + if (result.size() > 0) { + if (key[currentIndex] <= result[(result.size()-1)]) return false; + } result.push_back(key[currentIndex]); } } } } - return result; + return true; } - 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; - } - - 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; - } }; void print(vector<int> a) { @@ -204,9 +117,10 @@ 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()); + if (t.is_Bst()) + cout << "CORRECT" << endl; + else + cout << "INCORRECT" << endl; return 0; } |