Run Code
|
API
|
Code Wall
|
Misc
|
Feedback
|
Login
|
Theme
|
Privacy
|
Patreon
Balanced Insert Example
// Balanced 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) { 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 main() { cout << "*** Tree Example Program for ECE 2574 ***\n\n"; TreeNode<char> node0; node0.setItem('*'); TreeNode<char> node10; node10.setItem('+'); node0.setLeft(&node10); TreeNode<char> node11; node11.setItem('-'); node0.setRight(&node11); TreeNode<char> node20; node20.setItem('a'); node10.setLeft(&node20); TreeNode<char> node21; node21.setItem('b'); node10.setRight(&node21); TreeNode<char> node22; node22.setItem('c'); node11.setLeft(&node22); TreeNode<char> node23; node23.setItem('d'); node11.setRight(&node23); // set root and search tree TreeNode<char> *root = &node0; preorderSearch(root); cout << endl; // set height int height = setHeight(root); cout << "Height of tree is " << height << endl << endl; // add nodes using insert for (char x = 'A'; x < 'Z'; x++) { insert(root,x); height = setHeight(root); cout << "Inserted value " << x << " and new height = " << height << endl; } cout << endl; preorderSearch(root); cout << endl; cout << "Height of tree is " << height << endl; return 0; }
run
|
edit
|
history
|
help
0
1337
user defined exception
pointer to complete array does not convert implicitly to pointer to array of unknown bound
Magic, why 1 2?
Thread-safe Interval Average Calculator
hw1 Os
appliWall
back_inserter example
vector destruction - clang
C++ Template