Binary Tree

[winky]

Hey guys I'm attempting to create a binary tree using pointers and then be able to do functions like post-order, pre-order, etc.

Anyways, I am having problems with getting the functions to work with a user input. I'm relatively new to structs, but I think from the tutorials I have read this is formatted relatively correctly. If anyone knows why my main functions isn't accepting the inputs/functions that I have created that would be awesome. Thanks for any responses you can give me :)

#include <iostream>
#include <cstdlib>
using namespace std;

struct Node 
{
	int data;       
	Node* left;   
    Node* right;  
};

class btree
{
public:
	btree();
	void insert(int num);
	Node *search(int num);
	void btree::preorderWalk( Node *root );
	void btree::inorderWalk( Node *root );
	void btree::postorderWalk( Node *root );
private:
	void insert(int num, Node *leaf);
	Node *search(int num, Node *leaf);

	Node *root;
};

btree::btree()
{
	root=NULL;
}

void btree::insert(int num)
{
	if(root!=NULL)
	{
		insert(num, root);
	}
	else
	{
		root=new Node;
		root->data=num;
		root->left=NULL;
		root->right=NULL;
	}
}
	
void btree::insert(int num, Node *leaf)
{
	if(num< leaf->data)
	{
		if(leaf->left!=NULL)
		{
			insert(num, leaf->left);
		}
		else
		{
			leaf->left=new Node;
			leaf->left->data=num;
			leaf->left->left=NULL;
			leaf->left->right=NULL;
		}
	}
	else if(num>=leaf->data)
	{
		if(leaf->right!=NULL)
			insert(num, leaf->right);
		else
		{
			leaf->right=new Node;
			leaf->right->data=num;
			leaf->right->left=NULL;
			leaf->right->right=NULL;
		}
	}
}

Node *btree::search(int num, Node *leaf)
{
  if(leaf!=NULL)
  {
    if(num==leaf->data)
      return leaf;
    if(num<leaf->data)
      return search(num, leaf->left);
    else
      return search(num, leaf->right);
  }
  else return NULL;
}

Node *btree::search(int num)
{
  return search(num, root);
}

void btree::preorderWalk( Node *root ) 
{   
        if ( root != NULL ) 
		{  
           cout << root->data << " ";      
           preorderWalk( root->left );    
           preorderWalk( root->right );   
        }
		else
		{
			cout << "Tree is empty\n";
		}
}
    

void btree::postorderWalk( Node *root ) 
{   
        if ( root != NULL ) 
		{  
           postorderWalk( root->left );    
           postorderWalk( root->right );  
           cout << root->data << " ";      
        }
}
    


void btree::inorderWalk( Node *root )
{

        if ( root != NULL ) 
		{  
           inorderWalk( root->left );   
           cout << root->data << " ";     
           inorderWalk( root->right );   
        }
}

int main()
{
	char menuchoice;
	int binum;
	cout << "Please enter a menu choice:\n";
	cout << "'A' - In-order Print\n";
	cout << "'B' - Pre-order Print\n";
	cout << "'C' - Post-order Print\n";
	cout << "'I' - Insert Command\n";
	cout << "'S' - Search Command\n";
	cout << "'D' - Delete Command\n";
	cout << "'N' - Tree Minimum Command\n";
	cout << "'Q' - Quit Program\n";
	cin >> menuchoice;
	if(menuchoice == 'I')
	{
		cout << "Enter a key to insert\n";
		cin >> binum;
		void btree::insert(binum);
		cout << "The item inserted";
		
	}
	
	else if(menuchoice == 'A')
	{
		void btree::inorderWalk(root);
	}



	return 0;

}

[Lerner]

The Node struct is correct. However, your use the btree class does have several problems.

First:
You don't need to scope operator in the following line, and those like it.

void btree::preorderWalk( Node *root );

It's not actually an error according to my compiler, but it isn't necessary. This is the typical syntax for a method declaration.

void preorderWalk( Node * );

Your method definitions are correct however. You do need the scope operator there, as you've done it.

Second:
The following isn't a function call to insert a value into a btree object as you apparently intend.

void btree::insert(binum);

The appropriate thing would be to declare a btree object in main() calling the insert method on the btree object and passing it binum.

Third:
The following line:

void btree::inorderWalk(root);

has the same concern as above. In addition however, you are trying to pass the root of a btree to inorderWalk() outside a class method definition. However root is declared as a private member of the btree class so you need an accessor function to get to it. Maybe something like this would be better:

btree b;
b.inorderWalk(b.getRoot());

I'll leave it to you to declare and define getRoot() and see if it actually works.

I've not tested the program I got to compile so I don't know if there are runtime errors. You can post if there are. Include what you use as input, what you expect as output and what you actually get as output or where the program crashes, if it does that instead.

[mitrmkar]

You'd probably want to use a loop for operating with user input, i.e. something like

// use an instance of btree class ...
btree tree;
// a Node pointer
Node * nodeptr = NULL;
do
{
	cout << "Please enter a menu choice:\n"
	       << "'A' - In-order Print\n"
	       << "'B' - Pre-order Print\n"
	       << "'C' - Post-order Print\n"
               << "'I' - Insert Command\n"
	       << "'S' - Search Command\n"
	       << "'D' - Delete Command\n"
	       << "'N' - Tree Minimum Command\n"
	       << "'Q' - Quit Program\n";

	cin >> menuchoice;

	switch(menuchoice)
	{
		case 'I':
			cout << "Enter a key to insert\n";
			cin >> binum;
			tree.insert(binum);
			cout << "The item inserted\n";
		break;
		case 'A':
			cout << "inorderWalk ...\n";
			tree.inorderWalk(nodeptr);
		break;
		// case 'B' ...
		default:
			break;
	}

} while('Q' != menuchoice);

If your btree class's e.g. insert() were a static function i.e.

class btree{
[B]static[/B] void btree::insert(int num);
};

then you could make a call like

btree::insert(binum);

in your code. However, since it is not, you have to have an instance of the btree class and operate with that instance instead, i.e.

btree tree;
tree.insert(binum);

Last but not least, you cannot invoke a function like this

void btree::insert(binum);

the following however is legal (and probably what you meant),

[B]([/B]void[B])[/B] btree::insert(binum);

[winky]

Yeah, I implemented a loop to manage user input. I also fixed my function, so that added a number to binary tree works, but I am having trouble discerning how to enter a Node parameter (i.e. the root node for the walkthroughs)

[mitrmkar]

Lerner suggested the following ...

btree b;
b.inorderWalk(b.getRoot());

i.e. using a new btree::getRoot() function to get the Node pointer needed.
Or perhaps, do a walk based on a node produced by a search() ...