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,794
    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