[RESOLVED] Binary Tree Post-Order Traversal Issue

[Symus]

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.

/**
    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)



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.