Thread: Binary sort number arranging tree

  1. #1
    Registered User
    Join Date
    Nov 2006
    Posts
    13

    Question Binary sort number arranging tree

    I am having trouble with this. I believe I have found where the problem is with the random couts in the functions. When a node is added it keeps getting added to root node. It won't become a new node. What am I doing wrong? Thanks for any help offered.

    Code:
    #include <iostream>
    
    using namespace std;
    
    class Node
    {
        public:
            Node(int v);
            ~Node();
                   
            int value;
            
            Node* left;
            Node *right;
    };
    
    Node::Node(int v)
    {
        value = v;
        left = NULL;
        right = NULL;
    }
    
    Node::~Node() {}
    
    
    class BinaryTree
    {
        public:
            BinaryTree();
            ~BinaryTree();
            
            void add(int i);
            void display();
            
            void clear();
            
        private:
            Node* root;
            
            void removeNode(Node* n);
            void displayValue(Node* n);
            void insertNode(Node* n, int v);
    };
    
    BinaryTree::BinaryTree()
    {
        root = NULL;
    }
    
    BinaryTree::~BinaryTree() 
    {
        removeNode(root);
    }
    
    void BinaryTree::removeNode(Node* n)
    {
        if (n)
        {
            removeNode(n->left);
            removeNode(n->right);
            delete n;
        }
    }
    
    void BinaryTree::clear()
    {
        removeNode(root);
    }
    
    void BinaryTree::display()
    {
        cout << "Values: ";
        displayValue(root);
        cout << endl;
    }
    
    void BinaryTree::displayValue(Node* n)
    {
        if (n)
        {
            if (n->left)
                displayValue(n->left);
            if (n->right)
                displayValue(n->right);
                
            cout << n->value << ", ";
        }
    }
    
    void BinaryTree::add(int i)
    {
        if (root)
            cout << "root is not null" <<endl;
        else
            cout << "root is null" << endl;
            
        insertNode(root, i);
    }
    
    void BinaryTree::insertNode(Node* n, int v)
    {
        if (n)
        {
            if (v < n->value)
                insertNode(n->left, v);
            else
                insertNode(n->right, v);
                
            cout << "branch added" << endl;
        }
        else
        {
            n = new Node(v);
            cout << "leaf added" << endl;
        }
    }
    
    int main()
    {
        BinaryTree Tree;
        
        int response = 0;
        int value;
        
        while (response != 4)
        {
            cout << "1. Add A Number." << endl;
            cout << "2. Display Values." << endl;
            cout << "3. Clear Tree." << endl;
            cout << "4. Exit." << endl;
            cin >> response;
            
            if (response == 1)
            {
                cout << "Value to add: ";
                cin >> value;
                Tree.add(value);
            }
            else if (response == 2)
            {
                Tree.display();
            }
            else if (response == 3)
            {
                Tree.clear();
            }
            
            cout << " ----------------------------- " << endl;
    
        }
        cin.get();
        return 0;
    }
    Last edited by newtocpp; 11-14-2006 at 02:11 AM.

  2. #2
    Hurry Slowly vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,788
    insertion seems to be OK
    problem with displaying
    Code:
    void BinaryTree::displayValue(Node* n)
    {
        if (n)
        {
            if (n->left)
                displayValue(n->left);
            if (n->right)
                displayValue(n->right);
                
            cout << n->value << ", ";
        }
    }
    Code:
            cout << n->value << ", ";
    should be outputted before right node
    All problems in computer science can be solved by another level of indirection,
    except for the problem of too many layers of indirection.
    – David J. Wheeler

  3. #3
    Registered User
    Join Date
    Nov 2006
    Posts
    13
    I don't think displaying is the probem, inserting is.

    When root is passed in "insertNode(Node* n, int v);" as insertNode(root, i) the new keyword works only for the prototype "Node* n" but root isn't being set as Node *n. I am sorry for my ignorance with pointers and passing them in functions. I am new with them.

    Code:
    void BinaryTree::add(int i)
    {
        if (root)
            cout << "root is not null" <<endl;
        else
            cout << "root is null" << endl;
            
        insertNode(root, i);
    }
    
    void BinaryTree::insertNode(Node* n, int v)
    {
        if (n)
        {
            if (v < n->value)
                insertNode(n->left, v);
            else
                insertNode(n->right, v);
                
            cout << "branch added" << endl;
        }
        else
        {
            n = new Node(v);
            cout << "leaf added" << endl;
        }
    }

  4. #4
    Registered User
    Join Date
    Nov 2006
    Posts
    13
    void BinaryTree::insertNode(Node*& n, int v)


    the *& was what the problem was. I am still unsure of what it exactly means.

    Also I am not sure if I am deleting all the nodes correctly. Would I also make the remove function be void removeNode(Node*& n); ?

    Here is the updated code, it seems to work but this is not what I am doing with trees. I am planning to use binary trees for a way more complex problem, this is just practice. Thanks for all the help provided so far.

    Code:
    #include <iostream>
    
    using namespace std;
    
    class Node
    {
        public:
            Node(int v);
            ~Node();
                   
            int value;
            
            Node* left;
            Node* right;
    };
    
    Node::Node(int v)
    {
        value = v;
        left = NULL;
        right = NULL;
    }
    
    Node::~Node() {}
    
    
    class BinaryTree
    {
        public:
            BinaryTree();
            ~BinaryTree();
            
            void add(int i);
            void display();
            
            void clear();
            
        private:
            Node* root;
            
            void removeNode(Node* n);
            void displayValue(Node* n);
            void insertNode(Node*& n, int v);
    };
    
    BinaryTree::BinaryTree()
    {
        root = NULL;
    }
    
    BinaryTree::~BinaryTree() 
    {
        removeNode(root);
    }
    
    void BinaryTree::removeNode(Node* n)
    {
        if (n)
        {
            removeNode(n->left);
            removeNode(n->right);
            delete n;
            n = NULL;
        }
    }
    
    void BinaryTree::clear()
    {
        removeNode(root);
    }
    
    void BinaryTree::display()
    {
        cout << "Values: ";
        displayValue(root);
        cout << endl;
    }
    
    void BinaryTree::displayValue(Node* n)
    {
        if (n)
        {     
            if (n->left)
                displayValue(n->left);
                
            cout << n->value << ", ";
                
            if (n->right)
                displayValue(n->right);
        }
    }
    
    void BinaryTree::add(int i)
    {       
        insertNode(root, i);
    }
    
    void BinaryTree::insertNode(Node*& n, int v)
    {
        if (n)
        {
            if (v < n->value)
                insertNode(n->left, v);
            else
                insertNode(n->right, v);
                
        }
        else
        {
            n = new Node(v);
        }
    }
    
    int main()
    {
        BinaryTree Tree;
        
        int response = 0;
        int value;
        
        while (response != 4)
        {
            cout << "1. Add A Number." << endl;
            cout << "2. Display Values." << endl;
            cout << "3. Clear Tree." << endl;
            cout << "4. Exit." << endl;
            cin >> response;
            
            if (response == 1)
            {
                cout << "Value to add: ";
                cin >> value;
                Tree.add(value);
            }
            else if (response == 2)
            {
                Tree.display();
            }
            else if (response == 3)
            {
                Tree.clear();
            }
    
            cout << " ----------------------------- " << endl;
        }
        cin.get();
        return 0;
    }
    Last edited by newtocpp; 11-14-2006 at 05:22 AM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. arrays vs lists? And containers in general!
    By clegs in forum C++ Programming
    Replies: 22
    Last Post: 12-03-2007, 02:02 PM
  2. Binary Tree
    By Ideswa in forum C Programming
    Replies: 12
    Last Post: 10-25-2007, 12:24 PM
  3. best STL method to implement a binary tree
    By MatthewDoucette in forum C++ Programming
    Replies: 8
    Last Post: 06-16-2006, 07:08 AM
  4. Binary Tree Sort
    By BakAttack in forum C++ Programming
    Replies: 6
    Last Post: 02-06-2003, 12:07 PM
  5. Templated Binary Tree... dear god...
    By Nakeerb in forum C++ Programming
    Replies: 15
    Last Post: 01-17-2003, 02:24 AM