-
February 26th, 2013, 08:02 PM
#1
[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)
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
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
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|