1 Replies - 316 Views - Last Post: 30 November 2012 - 01:23 PM Rate Topic: -----

#1 Schlosh08  Icon User is offline

  • New D.I.C Head
  • member icon

Reputation: 0
  • View blog
  • Posts: 28
  • Joined: 03-June 12

Binary Search Tree Program?

Posted 30 November 2012 - 12:30 PM

I am trying to create a program that takes in a tree and outputs preorder, inorder, and post order. An example of the input/output is: ./lab11 FBADCEGIH ABCDEFGHI
PreOrder: FBADCEGIH
InOrder: ABCDEFGHI
PostOrder: ACEDBHIGF

i'm mostly having trouble with the reconstruct function in BinaryTree.cpp, but if other errors are seen, please let me know

here is what I have so far

main.cpp
 #include <iostream>
#include <cstdlib>
#include <string>
#include "BinaryTree.h"

using namespace std;

int main(int argc, char* argv[])
{

	if(argc < 3) {
		cerr << "Usage: ./lab11 <preorderString> <inorderString>" << endl;
		exit(-1);
	}

	string PreOrderString = argv[1];
	string InOrderString = argv[2];

	//reconstruct the tree from the preorder and inorder strings
	BinaryTree HappyLilTree(InOrderString, PreOrderString);

	//print out the tree using all three methods
	HappyLilTree.printPreorderRoutine();
	HappyLilTree.printInorderRoutine();
	HappyLilTree.printPostorderRoutine();

	return 0;
} 


BinaryTree.cpp
#include <cstddef>  // definition of NULL
#include <new>      // for bad_alloc
#include <string>
#include <iostream>
#include <cstdlib>
#include "BinaryTree.h"      // header file
using namespace std;


/* Default Constructor */
BinaryTree::BinaryTree() : root(NULL)
{

}  // end default constructor

/*-----------------------------------------------------------------------------
BinaryTree Constructor
-----------------------------------------------------------------------------*/
BinaryTree::BinaryTree(string inorder, string preorder)
{

	cin >> preorder;
	cin >> inorder;
}

/*-----------------------------------------------------------------------------
BinaryTree reconstruct
This is the recursive function you can use to build the tree, call it from the
constructor above.
-----------------------------------------------------------------------------*/
void BinaryTree::reconstruct(TreeNode *treePtr, string inorder, string preorder)
{
		//HELP
}

/*-----------------------------------------------------------------------------
Prints the tree using PreOrder Traversal
-----------------------------------------------------------------------------*/
void BinaryTree::printPreorderRoutine()
{
		if ( root != NULL ){
			cout << "PreOrder: " << root->item << "";
			printPreorderRoutine( root->leftChildPtr );
			printPreorderRoutine( root->rightChildPtr );
		}
}

/*-----------------------------------------------------------------------------
Prints the tree using InOrder Traversal
-----------------------------------------------------------------------------*/
void BinaryTree::printInorderRoutine(B)/>/>/>/>
{
		if ( root != NULL ){
			printInorderRoutine( root->leftChildPtr );
			cout << "InOrder: " << root->item << "";
			printInorderRoutine ( root->rightChildPtr );
		}		
}

/*-----------------------------------------------------------------------------
Prints the tree using PostOrder Traversal
-----------------------------------------------------------------------------*/
void BinaryTree::printPostorderRoutine()
{
		if ( root != NULL ){
			printPostorderRoutine( root->leftChildPtr );
			printPostorderRoutine( root->rightChildPtr );
			cout << "PostOrder: " << root->item << "";
		
		}
}

/*Indicates if the tree is empty or not */
bool BinaryTree::isEmpty() const
{
   return (root == NULL);
}  // end isEmpty

/*Used to set the data at the root of the tree */
void BinaryTree::setRootData(const TreeItemType& newItem)
{
   	if (!isEmpty())
		root->item = newItem;
	else
	{
		root = new TreeNode();
	}
}  // end setRootData



BinaryTree.h
#include <cstdlib>
#include <iostream>
#include <string>
using namespace std;

//The typedef TreeItemType determines the data type help by the BinaryTree's TreeNodes
typedef char TreeItemType;

//ADT Binary Tree Class */
class BinaryTree
{

public:
	BinaryTree(string inorder, string preorder);//Implement Me!!!

	BinaryTree();

//binary tree operations
	bool isEmpty() const;

//set the root data
	void setRootData(const TreeItemType& newItem);

//print the tree using preorder
	void printPreorderRoutine();//Implement Me!!!

///print the tree using inorder
	void printInorderRoutine();//Implement Me!!!

//print the tree using postorder
	void printPostorderRoutine();//Implement Me!!!

protected:

//TreeNode is the data type that makes up the nodes of the tree
	struct TreeNode
	{
		TreeItemType	item;
		TreeNode*		leftChildPtr;
		TreeNode*		rightChildPtr;
		TreeNode(): leftChildPtr(NULL), rightChildPtr(NULL) {}
	};

	//This is the recursive function that you should implement to reconstruct the tree
   	void reconstruct(TreeNode *treePtr, string inorder, string preorder);	//Implement Me!!!

private:

	/*Pointer to the root of the tree*/
	TreeNode *root;
}; //end of BinaryTree class def.



TreeException.h

#include <stdexcept>
#include <string>

using namespace std;

class TreeException : public logic_error
{
public:
   TreeException(const string & message = "")
                        : logic_error(message.c_str())
   { }
};


This post has been edited by Schlosh08: 30 November 2012 - 12:33 PM


Is This A Good Question/Topic? 0
  • +

Replies To: Binary Search Tree Program?

#2 vividexstance  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 651
  • View blog
  • Posts: 2,231
  • Joined: 31-December 10

Re: Binary Search Tree Program?

Posted 30 November 2012 - 01:23 PM

I'm still going through the code, but one thing that strikes me right away, is that you have using directives (i.e., using namespace std;) in two of your header files. This is something you want to avoid because it can cause subtle namespace issues down the road, which can be hard to track down. Instead, just qualify everything from the standard namespace that is in the header files with std::. It's ok to have the using directives in your implementation files, just not in the header files.

*EDIT*: By saying:

Quote

i'm mostly having trouble with the reconstruct function in BinaryTree.cpp
Do you mean that you don't understand how to reconstruct the tree or you just want someone to show you how? This isn't a homework writing service, show us in code or even pseudo-code what you have come up with. If you really want help you need to show some effort because it doesn't seem like you have put any into the code as of yet.

A suggestion would be to write an insert function and maybe a function that figures out where a new tree node should go, and the insert function can call that function.

This post has been edited by vividexstance: 30 November 2012 - 01:30 PM

Was This Post Helpful? 0
  • +
  • -

Page 1 of 1