tree output c++

Question

LibraryCode 0 Junior Poster in Training

8 Years Ago

Hi,i have a code like this in .h file:

#pragma once
#include "stdafx.h"
#include"iostream"

using namespace std;

// balance factor enum
enum BalanceFactor { LH, RH, EH };

// treenode struct
template<class T>
struct TreeNode
{
    T info;
    TreeNode<T>* left;
    TreeNode<T>* right;
    BalanceFactor bf;
};

template<typename ItemType>
class TreeType
{
private:
    TreeNode<ItemType>* root;
public:
    TreeType();
    void RotateLeft(TreeNode<ItemType> * & tree);
    void RotateRight(TreeNode<ItemType> * & tree);
    void InsertItem(ItemType item);
    void Insert(TreeNode<ItemType>*& tree, ItemType item, bool & taller);
    void RightBalance(TreeNode<ItemType> *& tree, bool & taller);
    void LeftBalance(TreeNode<ItemType> *& tree, bool & taller);
    void Print(TreeNode<ItemType>* tree);
    void PrintTree();
};

template<class T>
TreeType<T>::TreeType()
{
    root = nullptr;
}

template <class ItemType>
void TreeType<ItemType>::RotateLeft(TreeNode<ItemType> * & tree)
{
    TreeNode<ItemType> * rs;
    if (tree == NULL)
        cerr << "It is impossible to rotate an empty tree in RotateLeft"
        << endl;
    else if (tree->right == NULL)
        cerr << "It is impossible to make an empty subtree the root in RotateLeft" << endl;
    else
    {
        rs = tree->right;
        tree->right = rs->left;
        rs->left = tree;
        tree = rs;
    }
}

template <class ItemType>
void TreeType<ItemType>::RotateRight(TreeNode<ItemType> * & tree)
{
    TreeNode<ItemType> * ls;
    if (tree == NULL)
        cerr << "It is impossible to rotate an empty tree in RotateRight"
        << endl;
    else if (tree->left == NULL)
        cerr << "It is impossible to make an empty subtree the root in RotateRight" << endl;
    else
    {
        ls = tree->left;
        tree->left = ls->right;
        ls->right = tree;
        tree = ls;
    }
}

template <class ItemType>
void TreeType<ItemType>::InsertItem(ItemType item)
{
    bool taller = false;
    Insert(root, item, taller);
}

template<class ItemType>
void TreeType<ItemType>::Insert(TreeNode<ItemType>*& tree, ItemType item, bool & taller)
{
    if (tree == NULL)
    {   // Insertion place found.
        tree = new TreeNode<ItemType>;
        tree->left = NULL;
        tree->right = NULL;
        tree->info = item;
        tree->bf = EH;
        taller = true;
    }
    else if (item == tree->info)
        cerr << "Duplicate key is not allowed in AVL tree." << endl;
    else if (item < tree->info)
    {
        Insert(tree->left, item, taller);       // Insert into left subtree 
        if (taller)
            switch (tree->bf)
            {
            case LH:
                LeftBalance(tree, taller);
                break;
            case EH:
                tree->bf = LH;
                break;
            case RH:
                tree->bf = EH;
                taller = false;
                break;
            }
    }
    else
    {
        Insert(tree->right, item, taller);
        if (taller)
            switch (tree->bf)
            {
            case RH:
                RightBalance(tree, taller);
                break;
            case EH:
                tree->bf = RH;
                break;
            case LH:
                tree->bf = EH;
                taller = false;
                break;
            }
    }

}

template <class ItemType>
void TreeType<ItemType>::RightBalance(TreeNode<ItemType> *& tree, bool & taller)
{
    TreeNode<ItemType> * rs = tree->right;
    TreeNode<ItemType> * ls;

    switch (rs->bf)
    {
    case RH:
        tree->bf = rs->bf = EH;
        RotateLeft(tree);
        taller = false;
        break;
    case EH:
        cerr << "Tree already balanced " << endl;
        break;
    case LH:
        ls = rs->left;
        switch (ls->bf)
        {
        case RH:    tree->bf = LH;
            rs->bf = EH;
            break;
        case EH:    tree->bf = rs->bf = EH;
            break;
        case LH:    tree->bf = EH;
            rs->bf = RH;
            break;
        }
        ls->bf = EH;
        RotateRight(tree->right);
        RotateLeft(tree);
        taller = false;
    }
}
template <class ItemType>
void TreeType<ItemType>::LeftBalance(TreeNode<ItemType> *& tree, bool & taller)
{
    TreeNode<ItemType> * ls = tree->left;
    TreeNode<ItemType> * rs;

    switch (ls->bf)
    {
    case LH:
        tree->bf = ls->bf = EH;
        RotateRight(tree);
        taller = false;
        break;
    case EH:
        cerr << "Tree already balanced " << endl;
        break;
    case RH:
        rs = ls->left;
        switch (rs->bf)
        {
        case LH:    tree->bf = RH;
            ls->bf = EH;
            break;
        case EH:    tree->bf = ls->bf = EH;
            break;
        case RH:    tree->bf = EH;
            ls->bf = LH;
            break;
        }
        rs->bf = EH;
        RotateLeft(tree->left);
        RotateRight(tree);
        taller = false;
    }
}

template <class ItemType>
void TreeType<ItemType>::PrintTree()
{
    Print(root);
}

template <class ItemType>
void TreeType<ItemType>::Print(TreeNode<ItemType>* tree)
{
    if (tree != nullptr)
    {
        // print left tree
        Print(tree->left);
        // print current node (inorder)
        cout << "Item: " << tree->info << " , BF: ";
        switch (tree->bf)
        {
        case LH:
            cout << "left high ";
            break;
        case RH:
            cout << "right high ";
            break;
        case EH:
            cout << "equal ";
            break;
        }
        if (tree->left != nullptr)
        {
            cout << ", Left: " << tree->left->info;
        }
        if (tree->right != nullptr)
            cout << ", Right: " << tree->right->info;
        if (tree->left == nullptr && tree->right == nullptr)
            cout << ", Leaf";
        cout << endl;
        // print right tree
        Print(tree->right);
    }
}

And this is the main .cpp:

#include "stdafx.h"
#include "TreeType.h"


using namespace std;

// menu helpers
int ShowMenu(void);

template<class T>
void ProcessMenu(TreeType<T>& tree);

// callbacks
template<class T>
void InsertItem(TreeType<T>& tree);
template<class T>
void PrintTree(TreeType<T>& tree);

int _tmain(int argc, _TCHAR* argv[])
{

        typedef TreeType<int> tree_type;
    tree_type tree;
    ProcessMenu(tree);
    return 0;
}

int ShowMenu(void)
{
    int option;
    cout << "\n\t" << endl;
    cout << "\t\t===============================" << endl;
    cout << "\t\t1. Insert into tree" << endl;
    cout << "\t\t2. Print tree" << endl;
    cin >> option;
    return option;



}
template<class T>

void ProcessMenu(TreeType<T>& tree)
{
    bool quit = false;
    switch (ShowMenu())
    {
    case1:
        InsertItem(tree);
        break;
    }while (!quit);

}


template<class T>
void InsertItem(TreeType<T>& tree)
 {
    cout << "Enter number: ";
    int num;
    cin >> num;
    tree.InsertItem(num);
    cout << "Number inserted:" + num;
    }

template<class T>
void PrintTree(TreeType<T>& tree)
 {
    tree.PrintTree();
    }

The problem is: the insertion does not work,once run the program all i see is my menu and once try to insert nothing happens.Can someone help please.

binary-tree c++ insert

Edited 8 Years Ago by LibraryCode

2 Contributors
3 Replies
290 Views
3 Days Discussion Span
Latest Post 8 Years Ago Latest Post by LibraryCode

All 3 Replies

cgeier 187 Junior Poster

8 Years Ago

In "Main.cpp", line 63 should be cout << "Number inserted:" << num << endl;

In "Main.cpp", there are multiple problems with "ProcessMenu".

No "do" for the while statement
case1 should be case 1 (you need a space between the word "case" and the number 1)
In "ShowMenu" you offer an option to print, but don't have a case statement for it in "ProcessMenu"
You don't offer an option to quit

Try the following for ShowMenu:

int ShowMenu(void)
{
    int option;
    cout << "\n\t" << endl;
    cout << "\t\t===============================" << endl;
    cout << "\t\t1. Insert into tree" << endl;
    cout << "\t\t2. Print tree" << endl;
    cout << "\t\t3. Quit" << endl;
    cout << "\t\t===============================" << endl;
    cout << endl;

    cout << "Choose an option: ";

    cin >> option;
    return option;
}//ShowMenu

Try the following for "ProcessMenu":

void ProcessMenu(TreeType<T>& tree)
{
    bool quit = false;
    do{
        switch (ShowMenu())
        {
            case 1:
                InsertItem(tree);
                break;
            case 2: 
                PrintTree(tree);
                break;
            case 3:
                quit = true;
                break;
            default:
                cout << "Error: Invalid option. Try again." << endl;
        }//switch
    } while (!quit);

}//ProcessMenu

Reply to this topic

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.

LibraryCode 0 Junior Poster in Training · Answer 1 · 2015-09-23T16:01:18+00:00

LibraryCode 0 Junior Poster in Training

8 Years Ago

Thank you kindly.

LibraryCode 0 Junior Poster in Training · Answer 2 · 2015-09-26T09:13:55+00:00

I add to it the delete function,but it does not delete:

#include "stdafx.h"
#include "TreeType.h"


using namespace std;

// menu helpers
int ShowMenu(void);

template<class T>
void ProcessMenu(TreeType<T>& tree);

// callbacks
template<class T>
void InsertItem(TreeType<T>& tree);

template<class T>
void DeleteItem(TreeType<T>& tree);

template<class T>
void PrintTree(TreeType<T>& tree);

int _tmain(int argc, _TCHAR* argv[])
{

        typedef TreeType<int> tree_type;
    tree_type tree;
    ProcessMenu(tree);
    return 0;
}

int ShowMenu(void)
{
    int option;
    cout << "\n\t" << endl;
    cout << "\t\t===============================" << endl;
    cout << "\t\t1. Insert into tree" << endl;
    cout << "\t\t2. Print tree" << endl;
    cout << "\t\t3. Delete tree" << endl;
    cout << "\t\t4. Quit" << endl;
    cout << "\t\t===============================" << endl;
    cout << endl;
    cout << "Choose an option: ";
    cin >> option;
    return option;
}//ShowMenu
template<class T>

void ProcessMenu(TreeType<T>& tree)
{
    bool quit = false;
    do {
        switch (ShowMenu())
        {
        case 1:
            InsertItem(tree);
            break;
        case 2:
            PrintTree(tree);
            break;
        case 3:
            DeleteItem(tree);
            break;
        case 4:
            quit = true;
            break;
        default:
            cout << "Error: Invalid option. Try again." << endl;
        }//switch
    } while (!quit);
}//ProcessMenu


template<class T>
void InsertItem(TreeType<T>& tree)
 {
    cout << "Enter number: ";
    int num;
    cin >> num;
    tree.InsertItem(num);
    cout << "Number inserted:" << num;
    }

template<class T>
void PrintTree(TreeType<T>& tree)
 {
    tree.PrintTree();
    }

template<class T>
void DeleteItem(TreeType<T>& tree)
{
    cout << "Enter number: ";
    int num;
    cin >> num;
    TreeNode<T>ItemToDelete(num);
    tree.DeleteItem(num);
    cout << "\n\n\t.................Done!\n";
}

And here the.h :

#pragma once
#include "stdafx.h"
#include"iostream"

using namespace std;

// balance factor enum
enum BalanceFactor { LH, RH, EH };

// treenode struct
template<class T>
struct TreeNode
{
    T info;
    TreeNode<T>* left;
    TreeNode<T>* right;
    BalanceFactor bf;
};

template<typename ItemType>
class TreeType
{
private:
    TreeNode<ItemType>* root;
public:
    TreeType();
    void RotateLeft(TreeNode<ItemType> * & tree);
    void RotateRight(TreeNode<ItemType> * & tree);
    void InsertItem(ItemType item);
    void Insert(TreeNode<ItemType>*& tree, ItemType item, bool & taller);
    void DeleteItem(ItemType item);
    void Delete(TreeNode<ItemType>*& tree, ItemType item, bool & shorter);
    void RightBalance(TreeNode<ItemType> *& tree, bool & taller);
    void LeftBalance(TreeNode<ItemType> *& tree, bool & taller);
    void Print(TreeNode<ItemType>* tree);
    void PrintTree();
};

template <class ItemType>
void TreeType<ItemType> :: DeleteItem (ItemType item)
// Calls recursive function Delete to delete item from tree.
{
    bool shorter;
    Delete (root, item, shorter);
}

template <class ItemType>
void TreeType<ItemType>::Delete(TreeNode<ItemType>*& tree, ItemType item, bool & shorter)
// Deletes item from tree.
// Post:    item is not in tree.
{
    if (tree != NULL)
    {
        if (item < tree->info)
        {
            Delete(tree->left, item, shorter);
            // Look in left subtree.
            if (shorter)
                switch (tree->bf)
                {
                case LH: tree->bf = EH; break;
                case EH: tree->bf = RH; shorter = false;
                    break;
                case RH: DelRightBalance(tree, shorter);
                }
        }

        else if (item > tree->info)
        {
            Delete(tree->right, item, shorter);
            // Look in right subtree.
            if (shorter)
                switch (tree->bf)
                {
                case LH: DelLeftBalance(tree, shorter);
                    break;
                case EH: tree->bf = LH; shorter = false;                            break;
                case RH: tree->bf = EH; break;
                }
        }
        else
            DeleteNode(tree, shorter);
        // Node found; call DeleteNode.
    }
    else
    {
        cout << "\nNOTE: " << item << " not in the tree so cannot be                  deleted.";
    }
}


template<class T>
TreeType<T>::TreeType()
{
    root = nullptr;
}

template <class ItemType>
void TreeType<ItemType>::RotateLeft(TreeNode<ItemType> * & tree)
{
    TreeNode<ItemType> * rs;
    if (tree == NULL)
        cerr << "It is impossible to rotate an empty tree in RotateLeft"
        << endl;
    else if (tree->right == NULL)
        cerr << "It is impossible to make an empty subtree the root in RotateLeft" << endl;
    else
    {
        rs = tree->right;
        tree->right = rs->left;
        rs->left = tree;
        tree = rs;
    }
}

template <class ItemType>
void TreeType<ItemType>::RotateRight(TreeNode<ItemType> * & tree)
{
    TreeNode<ItemType> * ls;
    if (tree == NULL)
        cerr << "It is impossible to rotate an empty tree in RotateRight"
        << endl;
    else if (tree->left == NULL)
        cerr << "It is impossible to make an empty subtree the root in RotateRight" << endl;
    else
    {
        ls = tree->left;
        tree->left = ls->right;
        ls->right = tree;
        tree = ls;
    }
}

template <class ItemType>
void TreeType<ItemType>::InsertItem(ItemType item)
{
    bool taller = false;
    Insert(root, item, taller);
}

template<class ItemType>
void TreeType<ItemType>::Insert(TreeNode<ItemType>*& tree, ItemType item, bool & taller)
{
    if (tree == NULL)
    {   // Insertion place found.
        tree = new TreeNode<ItemType>;
        tree->left = NULL;
        tree->right = NULL;
        tree->info = item;
        tree->bf = EH;
        taller = true;
    }
    else if (item == tree->info)
        cerr << "Duplicate key is not allowed in AVL tree." << endl;
    else if (item < tree->info)
    {
        Insert(tree->left, item, taller);       // Insert into left subtree 
        if (taller)
            switch (tree->bf)
            {
            case LH:
                LeftBalance(tree, taller);
                break;
            case EH:
                tree->bf = LH;
                break;
            case RH:
                tree->bf = EH;
                taller = false;
                break;
            }
    }
    else
    {
        Insert(tree->right, item, taller);
        if (taller)
            switch (tree->bf)
            {
            case RH:
                RightBalance(tree, taller);
                break;
            case EH:
                tree->bf = RH;
                break;
            case LH:
                tree->bf = EH;
                taller = false;
                break;
            }
    }

}

template <class ItemType>
void TreeType<ItemType>::RightBalance(TreeNode<ItemType> *& tree, bool & taller)
{
    TreeNode<ItemType> * rs = tree->right;
    TreeNode<ItemType> * ls;

    switch (rs->bf)
    {
    case RH:
        tree->bf = rs->bf = EH;
        RotateLeft(tree);
        taller = false;
        break;
    case EH:
        cerr << "Tree already balanced " << endl;
        break;
    case LH:
        ls = rs->left;
        switch (ls->bf)
        {
        case RH:    tree->bf = LH;
            rs->bf = EH;
            break;
        case EH:    tree->bf = rs->bf = EH;
            break;
        case LH:    tree->bf = EH;
            rs->bf = RH;
            break;
        }
        ls->bf = EH;
        RotateRight(tree->right);
        RotateLeft(tree);
        taller = false;
    }
}
template <class ItemType>
void TreeType<ItemType>::LeftBalance(TreeNode<ItemType> *& tree, bool & taller)
{
    TreeNode<ItemType> * ls = tree->left;
    TreeNode<ItemType> * rs;

    switch (ls->bf)
    {
    case LH:
        tree->bf = ls->bf = EH;
        RotateRight(tree);
        taller = false;
        break;
    case EH:
        cerr << "Tree already balanced " << endl;
        break;
    case RH:
        rs = ls->left;
        switch (rs->bf)
        {
        case LH:    tree->bf = RH;
            ls->bf = EH;
            break;
        case EH:    tree->bf = ls->bf = EH;
            break;
        case RH:    tree->bf = EH;
            ls->bf = LH;
            break;
        }
        rs->bf = EH;
        RotateLeft(tree->left);
        RotateRight(tree);
        taller = false;
    }
}

template <class ItemType>
void TreeType<ItemType>::PrintTree()
{
    Print(root);
}

template <class ItemType>
void TreeType<ItemType>::Print(TreeNode<ItemType>* tree)
{
    if (tree != nullptr)
    {
        // print left tree
        Print(tree->left);
        // print current node (inorder)
        cout << "Item: " << tree->info << " , BF: ";
        switch (tree->bf)
        {
        case LH:
            cout << "left high ";
            break;
        case RH:
            cout << "right high ";
            break;
        case EH:
            cout << "equal ";
            break;
        }
        if (tree->left != nullptr)
        {
            cout << ", Left: " << tree->left->info;
        }
        if (tree->right != nullptr)
            cout << ", Right: " << tree->right->info;
        if (tree->left == nullptr && tree->right == nullptr)
            cout << ", Leaf";
        cout << endl;
        // print right tree
        Print(tree->right);
    }
}

tree output c++

Recommended Answers Collapse Answers

All 3 Replies

Recommended Answers