summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorHaidong Ji2019-06-12 11:33:33 -0500
committerHaidong Ji2019-06-12 11:33:33 -0500
commit36d6a0c2b7c63d52f50e1509deed1f96ff1435d0 (patch)
tree5480bb365b2061a5dbef194d86d1bea6a857b2fe
parent1d2b8a1f4184569e166cc7cab0316bb0259c86d6 (diff)
Binary Serach Tree check done!
I was lazy and didn't write test cases for this, because it's more or less a straight copy from Java code, with minor modifications. In the process I forgot to check 0 sized vector, and got "unknown signal 11" segmentation fault error. Easy fix :)
-rw-r--r--Sources/DataStructure.cpp126
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;
}