Untitled
unknown
plain_text
2 years ago
4.7 kB
3
Indexable
#include <iostream> using namespace std; struct node { int value; node* left; node* right; }; bool isMinHeapUtil(node* T) { if (T == nullptr) return true; if (T->left == nullptr && T->right == nullptr) return true; if (T->left == nullptr) return (T->value <= T->right->value) && isMinHeapUtil(T->right); if (T->right == nullptr) return (T->value <= T->left->value) && isMinHeapUtil(T->left); return (T->value <= T->left->value) && (T->value <= T->right->value) && isMinHeapUtil(T->left) && isMinHeapUtil(T->right); } bool isMinHeap(node* T) { return isMinHeapUtil(T); } //1a int biggestMinHeap(node* T) { if (T == nullptr) return 0; int left = biggestMinHeap(T->left); int right = biggestMinHeap(T->right); if (T->left != nullptr && T->value > T->left->value) return max(left, right); if (T->right != nullptr && T->value > T->right->value) return max(left, right); return 1 + left + right; } //1b bool biggestMinBinaryHeap(node* T, int &maxSize) { if (T == nullptr) return true; bool leftIsMinHeap = biggestMinBinaryHeap(T->left, maxSize); bool rightIsMinHeap = biggestMinBinaryHeap(T->right, maxSize); if (!leftIsMinHeap || !rightIsMinHeap) return false; int leftSize = 0; int rightSize = 0; if (T->left != nullptr) { if (T->value > T->left->value) return false; leftSize = 1 + biggestMinBinaryHeap(T->left->left, maxSize) + biggestMinBinaryHeap(T->left->right, maxSize); } if (T->right != nullptr) { if (T->value > T->right->value) return false; rightSize = 1 + biggestMinBinaryHeap(T->right->left, maxSize) + biggestMinBinaryHeap(T->right->right, maxSize); } int size = 1 + leftSize + rightSize; if (size > maxSize) maxSize = size; return size == (1 << int(log2(size) + 1)) - 1; } int biggestMinBinaryHeap(node* T) { int maxSize = 0; biggestMinBinaryHeap(T, maxSize); return maxSize; } //1c bool isBoth(node* T, int minValue, int maxValue) { if (T == nullptr) return true; if (T->value < minValue || T->value > maxValue) return false; bool leftIsValid = isBoth(T->left, minValue, T->value); bool rightIsValid = isBoth(T->right, T->value, maxValue); return leftIsValid && rightIsValid; } bool isBoth(node* T) { return false // deoarece nu poate sa fie si BST si min-heap } //1d node *createNode(int i) { node *p = new node; p->value = i; p->left = nullptr; p->right = nullptr; return p; } int main() { node* T = createNode(19); T->left = createNode(5); T->right = createNode(15); T->left->left = createNode(1); T->left->right = createNode(7); T->right->left = createNode(12); T->right->right = createNode(20); if (isBoth(T)) { std::cout << "The binary tree is both a min-heap and a binary search tree." << std::endl; } else { std::cout << "The binary tree is not both a min-heap and a binary search tree." << std::endl; } return 0; } bool isTree(vector<int> &v) { // if parent doesnt exist int n = v.size(); for (int i = 0; i < n; i++) { if (v[i] < -1 || v[i] >= n) return false; } // check that it can reach root for (int i = 0; i < n; i++) { if (v[i] == -1) continue; int j = v[i]; while (j != -1) { if (j == i) return false; j = v[j]; } } return true; } // 2b bool isBinHeap(vector<int> arr) { int n = arr.size() for (int i=0; i<=(n-2)/2; i++) { // If left child is greater, return false if (arr[2*i +1] > arr[i]) return false; // If right child is greater, return false if (2*i+2 < n && arr[2*i+2] > arr[i]) return false; } return true; } // 2c bool isPreorder(const vector<int>& p) { // ascending sequences int n = p.size(); int i = 0; while (i < n) { int right = i + 1; while (right < n && p[right] > p[i]) { right++; } for (int j = i + 1; j < right; j++) { if (p[j] < p[i]) { return false; } } i = right; } return true; } int main() { vector<int> v = {-1, 0, 1, 2, 3}; cout << isTree(v); cout << isBinHeap(v); cout << isPreorder(v); return 0; }
Editor is loading...