Run Code
|
API
|
Code Wall
|
Misc
|
Feedback
|
Login
|
Theme
|
Privacy
|
Patreon
Balanced Insert Heap Example
// Balanced Heap Insert Example program using TreeNode #include <algorithm> #include <iostream> using namespace std; template<class ItemType> class TreeNode { private: ItemType item; // A data item int height; // height of node in tree, a leaf has height 1 TreeNode<ItemType>* leftChild; // Pointer to left child TreeNode<ItemType>* rightChild; // Pointer to left child public: TreeNode() {leftChild = nullptr; rightChild = nullptr; height = 1;}; void setItem(const ItemType& anItem) {item = anItem;}; void setHeight(int h) {height = h;}; void setLeft(TreeNode<ItemType>* treeNodePtr) {leftChild = treeNodePtr;}; void setRight(TreeNode<ItemType>* treeNodePtr) {rightChild = treeNodePtr;}; ItemType getItem() const {return item;}; int getHeight() const {return height;}; TreeNode<ItemType>* getLeft() const {return leftChild;}; TreeNode<ItemType>* getRight() const {return rightChild;}; }; // end TreeNode template<class ItemType> void preorderSearch(TreeNode<ItemType> *node) { if (node == nullptr) return; cout << node->getItem() << " "; preorderSearch(node->getLeft()); preorderSearch(node->getRight()); } template<class ItemType> int setHeight(TreeNode<ItemType> *node) { if (node == nullptr) return 0; int leftHeight = setHeight(node->getLeft()); int rightHeight = setHeight(node->getRight()); int height = std::max(leftHeight,rightHeight) + 1; node->setHeight(height); return height; } template<class ItemType> void insert(TreeNode<ItemType>* node, ItemType value) { // swap value based on minHeap criteria if (value < node->getItem()) { ItemType temp = node->getItem(); node->setItem(value); value = temp; } if (node->getHeight() == 1) // leaf, insert on left { TreeNode<ItemType> *newNode = new TreeNode<ItemType>; newNode->setItem(value); node->setLeft(newNode); return; } if (node->getRight()==nullptr) // insert on right if not leaf and right is nullptr { TreeNode<ItemType> *newNode = new TreeNode<ItemType>; newNode->setItem(value); node->setRight(newNode); return; } if (node->getLeft()->getHeight() <= node->getRight()->getHeight()) // insert on left if height <= right height { insert(node->getLeft(),value); } else // otherwise right { insert(node->getRight(),value); } return; } int log2func(int x) { int returnValue = 0; while (x > 0) { x = x >> 1; returnValue++; } return returnValue; } int main() { cout << "*** Tree Example Program for ECE 2574 ***\n\n"; int testSize = 2; // set root and search tree TreeNode<int> rootNode; rootNode.setItem(testSize + 1); TreeNode<int> *root = &rootNode; int treeSize = 1; int height = setHeight(root);; // add nodes using insert float maxRatio = 1.0; for (int i = 1; i <= testSize; i++) { insert(root,i); height = setHeight(root); treeSize++; int optimalHeight = log2func(treeSize); float ratio = (float)height/(float)optimalHeight; if (ratio > maxRatio) maxRatio = ratio; cout << "Inserted value " << i << " and new height = " << height << " Optimal Tree Height = " << optimalHeight << " Tree size = " << treeSize << " Ratio = " << (float)height/(float)optimalHeight << endl; } cout << endl; cout << "Max ratio of tree height to optimal tree height = " << maxRatio; cout << endl; //preorderSearch(root); cout << endl; cout << "Height of tree is " << height << endl; return 0; }
run
|
edit
|
history
|
help
0
hello,world !ssn2019
Fun with Pointers #1
virtual members
user defined exception
general
Tilted uniform distribution random number generator over min/max range
Program to Time Difference
Code Rush Game Group 1
Rounding float to nearest 1000
bank queue