CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 10 of 10
  1. #1
    Join Date
    Jul 2012
    Posts
    15

    [RESOLVED] Binary Tree Post-Order Traversal Issue

    Hi all,

    I am trying to develop a function which prints a binary tree using post-order traversal (left, right, root) but I am experiencing some troubles. The code
    is compiled but when I run the program it crashes right before printing the post-order traversal.

    Below you can find my code and the output from debugging.

    Code:
    /**
        Program which represents a Binary Search Tree and is modified with the following functions:
        - smallest() - member function which searches for the smallest element in the tree.
        - preorder() - member function which prints the tree nodes using pre-order traversal
        - postorder() - member function which prints the tree nodes using post-order traversal (to be completed)
    */
    
    #include <iostream>
    #include <cstdlib>
    #include <string>
    
    using namespace std;
    
    class TreeNode
    {
        public:
                    void insert_node(TreeNode* new_node);
                    void print_nodes() const;
                    bool find(string value) const;
                    void preorder() const;
                    void postorder(TreeNode& a);
    
        private:
                    string data;
                    TreeNode* left;
                    TreeNode* right;
                    friend class BinarySearchTree;
    };
    
    class BinarySearchTree
    {
        public:
                    BinarySearchTree();
                    void insert(string data);
                    void erase(string data);
                    string smallest(); // Searches for the smallest element in the tree
                    int count(string data) const; // Counts if an element already exists in the tree
                    void print() const;
                    void print_preorder() const;
                    void print_postorder();
    
        private:
                    string small;
                    TreeNode* root;
    };
    
    BinarySearchTree::BinarySearchTree()
    {
        root = NULL;
    }
    
    void BinarySearchTree::print() const
    {
        if (root != NULL)
        {
            root->print_nodes();
        }
    }
    
    void BinarySearchTree::print_preorder() const
    {
        if (root != NULL)
        {
            root->preorder();
        }
    }
    
    void BinarySearchTree::print_postorder()
    {
        if (root != NULL)
        {
            root->postorder(*root);
        }
    }
    
    void BinarySearchTree::insert(string data)
    {
        TreeNode* new_node = new TreeNode;
        new_node->data = data;
        new_node->left = NULL;
        new_node->right = NULL;
        if (root == NULL)
        {
            root = new_node;
        }
        else
        {
            root->insert_node(new_node);
        }
    }
    
    void TreeNode::insert_node(TreeNode* new_node)
    {
        if (new_node->data < data)
        {
            if (left == NULL)
            {
                left = new_node;
            }
            else
            {
                left->insert_node(new_node);
            }
        }
        else if (data < new_node->data)
        {
            if (right == NULL)
            {
                right = new_node;
            }
            else
            {
                right->insert_node(new_node);
            }
        }
    }
    
    string BinarySearchTree::smallest()
    {
        TreeNode* temp = root;
        while (temp->left != NULL)
        {
            if (temp->left->data < temp->right->data)
            {
                temp = temp->left;
                small = temp->data;
            }
        }
        return small;
    }
    
    int BinarySearchTree::count(string data) const
    {
        if (root == NULL) { return 0; }
        else if (root->find(data)) { return 1; }
        else { return 0; }
    }
    
    void BinarySearchTree::erase(string data)
    {
        // Find node to be removed
    
        TreeNode* to_be_removed = root;
        TreeNode* parent = NULL;
        bool found = false;
        while (!found && to_be_removed != NULL)
        {
            if (to_be_removed->data < data)
            {
                parent = to_be_removed;
                to_be_removed = to_be_removed->right;
            }
            else if (data < to_be_removed->data)
            {
                parent = to_be_removed;
                to_be_removed = to_be_removed->left;
            }
            else found = true;
        }
    
        if (!found) return;
    
        // to_be_removed contains data
    
        // If one of the children is empty, use the other
    
        if (to_be_removed->left == NULL || to_be_removed->right == NULL)
        {
            TreeNode* new_child;
            if (to_be_removed->left == NULL)
            {
                new_child = to_be_removed->right;
            }
            else
            {
                new_child = to_be_removed->left;
            }
            if (parent == NULL) // Found in root
            {
                root = new_child;
            }
            else if (parent->left == to_be_removed)
            {
                parent->left = new_child;
            }
            else
            {
                parent->right = new_child;
            }
            return;
        }
    
        // Neither subtree is empty
    
        // Find smallest element of the right subtree
    
        TreeNode* smallest_parent = to_be_removed;
        TreeNode* smallest = to_be_removed->right;
        while (smallest->left != NULL)
        {
            smallest_parent = smallest;
            smallest = smallest->left;
        }
    
        // smallest contains smallest child in right subtree
    
        // Move contents, unlink child
        to_be_removed->data = smallest->data;
        if (smallest_parent == to_be_removed)
        {
            smallest_parent->right = smallest->right;
        }
        else
        {
            smallest_parent->left = smallest->right;
        }
    }
    
    bool TreeNode::find(string value) const
    {
        if (value < data)
        {
            if (left == NULL)
            {
                return false;
            }
            else
            {
                return left->find(value);
            }
        }
        else if (data < value)
        {
            if (right == NULL)
            {
                return false;
            }
            else
            {
                return right->find(value);
            }
        }
        else
        {
            return true;
        }
    }
    
    void TreeNode::print_nodes() const
    {
        if (left != NULL)
        {
            left->print_nodes();
        }
        cout << data << " ";
        if (right != NULL)
        {
            right->print_nodes();
        }
    }
    
    void TreeNode::preorder() const
    {
        cout << data << " ";
        if (left != NULL)
        {
            left->preorder();
        }
        if (right != NULL)
        {
            right->preorder();
        }
    }
    
    void TreeNode::postorder(TreeNode& a)
    {
        if (left != NULL)
        {
            postorder(*a.left);
        }
        if (right != NULL)
        {
            postorder(*a.right);
        }
        cout << data;
    }
    
    int main()
    {
        BinarySearchTree t;
        t.insert("F");
        t.insert("B");
        t.insert("A");
        t.insert("D");
        t.insert("C");
        t.insert("E");
        t.insert("G");
        t.insert("I");
        t.insert("H");
    
        /**t.insert("D");
        t.insert("B");
        t.insert("A");
        t.insert("C");
        t.insert("F");
        t.insert("E");
        t.insert("I");
        t.insert("G");
        t.insert("H");
        t.insert("J");
        //t.erase("A"); // Removing element with no children
        //t.erase("B"); // Removing element with one child
        //t.erase("F"); // Removing element with two children
        //t.erase("D"); // Removing root
        //t.print();*/
        cout << "Preorder:" << endl; t.print_preorder();
        cout << endl;
        cout << "Postorder:";
        t.print_postorder();
        cout << endl;
        cout << t.count("E") << endl;
        cout << t.count("F") << endl;
        cout << "The smallest element in the tree is " << t.smallest() << endl;
    
        system("PAUSE");
        return 0;
    }
    Here is the debug information and a screenshot of what is the program output:
    #0 00401AAE TreeNode::postorder(this=0x381110, a=...) (C:\Program Files (x86)\CodeBlocks\Projects\Test\main.cpp:279)
    #1 00401ABE TreeNode::postorder(this=0x381110, a=...) (C:\Program Files (x86)\CodeBlocks\Projects\Test\main.cpp:279)
    #2 00401ABE TreeNode::postorder(this=0x381110, a=...) (C:\Program Files (x86)\CodeBlocks\Projects\Test\main.cpp:279)
    #3 00401ABE TreeNode::postorder(this=0x381110, a=...) (C:\Program Files (x86)\CodeBlocks\Projects\Test\main.cpp:279)
    #4 004013C1 BinarySearchTree::print_postorder(this=0x28fe9c) (C:\Program Files (x86)\CodeBlocks\Projects\Test\main.cpp:72)
    #5 00401F85 main() (C:\Program Files (x86)\CodeBlocks\Projects\Test\main.cpp:319)

    Name:  Capture.PNG
Views: 2410
Size:  7.6 KB

    This is from the debugger log:
    Child process PID: 5720
    At C:\Program Files (x86)\CodeBlocks\Projects\Test\main.cpp:316
    At C:\Program Files (x86)\CodeBlocks\Projects\Test\main.cpp:317
    At C:\Program Files (x86)\CodeBlocks\Projects\Test\main.cpp:318
    At C:\Program Files (x86)\CodeBlocks\Projects\Test\main.cpp:319
    Program received signal SIGSEGV, Segmentation fault.
    At C:\Program Files (x86)\CodeBlocks\Projects\Test\main.cpp:279

    Please help me on this.

    Thanks in advance.
    Last edited by Brad Jones; February 27th, 2013 at 11:15 AM. Reason: disabled smilies in post

  2. #2
    GCDEF is offline Elite Member Power Poster
    Join Date
    Nov 2003
    Location
    Florida
    Posts
    12,635

    Re: Binary Tree Post-Order Traversal Issue

    I found the problem in less than a minute using the debugger. It's an amazingly useful tool.

    Code:
        if (left != NULL)
        {
            postorder(*a.left);
        }
        if (right != NULL)
        {
            postorder(*a.right);
        }
    You want to be checking a.left and a.right for NULL, not left and right.

  3. #3
    Join Date
    Jul 2012
    Posts
    15

    Re: Binary Tree Post-Order Traversal Issue

    Thank you for your help.

    I found one more mistake in the same function, the cout should be a.data instead of data. The program now works accurately.

    Thanks

  4. #4
    Join Date
    Jan 2009
    Posts
    596

    Re: Binary Tree Post-Order Traversal Issue

    Why are your preorder and postorder methods structured differently? You could have written postorder exactly as preorder, except with the 'cout << data' part at the end. There is no need for it to take an argument.

  5. #5
    Join Date
    Jul 2012
    Posts
    15

    Re: Binary Tree Post-Order Traversal Issue

    I tried this the first time but when I run the program the output is wrong...I don't know why it happens. That's why I decided to do it with argument

  6. #6
    Join Date
    Jan 2009
    Posts
    596

    Re: Binary Tree Post-Order Traversal Issue

    Quote Originally Posted by Symus View Post
    I tried this the first time but when I run the program the output is wrong...I don't know why it happens. That's why I decided to do it with argument
    You must have made a mistake somewhere - it works fine for me. NB: when I said exactly as preorder, except... I meant the same structure. I.e. the postorder method would call the postorder method for the left and right subtrees, not the preorder method.

  7. #7
    Join Date
    Jul 2012
    Posts
    15

    Re: Binary Tree Post-Order Traversal Issue

    I understand what you mean. Let me show you:

    Code:
    void TreeNode::postorder() const
    {
        if (left != NULL)
        {
            left->preorder();
        }
        if (right != NULL)
        {
            right->preorder();
        }
        cout << data << " ";
    }
    And here is what the program prints: B A D C E G I H F which is wrong because I think it should be A, C, E, D, B, H, I, G, F (left, right, root)

  8. #8
    2kaud's Avatar
    2kaud is offline Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    7,822

    Re: Binary Tree Post-Order Traversal Issue

    You're calling preorder in the postorder method!

  9. #9
    Join Date
    Jan 2009
    Posts
    596

    Re: Binary Tree Post-Order Traversal Issue

    Quote Originally Posted by 2kaud View Post
    You're calling preorder in the postorder method!
    Yes, I thought this was probably what was wrong.
    Symus, when you originally coded postorder did you copy and paste preorder and just move the cout line?

  10. #10
    Join Date
    Jul 2012
    Posts
    15

    Re: Binary Tree Post-Order Traversal Issue

    Oops...yes, copy-paste!!! Sorry.

    I just tried it and it works...even for the in-order traversal... I don't know what I did before but I guess that I was calling the wrong functions. I feel so stupid right now. At least now I have two examples of how this program could work - a simple one and one that uses pointers and objects.

    Thanks guys!

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  





Click Here to Expand Forum to Full Width

Featured