Balanced Insert Example, C++ (clang)

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