[RESOLVED] Binary Tree Post-Order Traversal Issue
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 10 of 10

Thread: [RESOLVED] Binary Tree Post-Order Traversal Issue

Threaded View

  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: 636
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 10:15 AM. Reason: disabled smilies in post

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
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center