-
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
-
February 26th, 2013, 09:17 PM
#2
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.
-
February 26th, 2013, 10:21 PM
#3
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
-
February 27th, 2013, 05:49 PM
#4
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.
-
February 28th, 2013, 09:03 AM
#5
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
-
February 28th, 2013, 01:07 PM
#6
Re: Binary Tree Post-Order Traversal Issue
Originally Posted by Symus
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.
-
March 2nd, 2013, 03:07 PM
#7
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)
-
March 2nd, 2013, 04:09 PM
#8
Re: Binary Tree Post-Order Traversal Issue
You're calling preorder in the postorder method!
-
March 2nd, 2013, 05:26 PM
#9
Re: Binary Tree Post-Order Traversal Issue
Originally Posted by 2kaud
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?
-
March 3rd, 2013, 03:01 PM
#10
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
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|