Need help with Binary Tree Swap

[RayvenHawk]

I'm working on an assignment and I need to swap the values from the left side of the tree to the right side and vise versa. I'm having no luck on it so far.

Here is the header file with the important areas

template<class elemType>
struct nodeType
{
   elemType	           info;
   nodeType<elemType>  *llink;
   nodeType<elemType>  *rlink;
};

template<class elemType>
void binaryTreeType<elemType>::swapSubtreeNodes(nodeType<elemType>* p)
{
   if (p==NULL) 
   {
      return;
   }
   else 
   {
      struct nodeType<elemType> *temp;
      // do the subtrees
      swapSubtreeNodes(node->left);
      swapSubtreeNodes(node->right);
      // swap the pointers in this node
      temp = node->left;
      node->left = node->right;
      node->right = temp;
   }
}

And here is my main menu

int main()
{

	binaryTreeSearch<int> tree;
	int num;

	cout << "My Binary Tree Swap Function Program!"<<endl;
	cout << endl;
	cout << "Insert your numbers (Press Enter after each number)."<<endl;
	cout << " To finish enter -999"<<endl;
	tree.insert(0);
	cin>>num;

	while(num != -999)
	{
		tree.insert(num);
		cin>>num;
	}

	cout << "Here is your unswapped Binary Tree."<<endl;
	tree.printTree();
	cout <<endl;
	cout <<endl;
	cout << "Here is your swapped Binary Tree."<<endl;
	[B]tree.swapSubtreeNodes();[/B] <----- This is where I'm stuck
	tree.printTree();
	cout << endl;

What am I not seeing here, other than the fact when I call the function I have no arguments in it.

[Sci@phy]

You need root pointer that will point at root node inside main fnc. And then call:
tree.swapSubtreeNodes(root);

[RayvenHawk]

ok stupid question, but I'm drawing a blank on how to reference the root node in the main fnc. I assumed it'd be "tree *root", but it comes back and tells me root is undefined.

[Sci@phy]

You can't type "tree *root". Tree is instance of object, not object.
binaryTreeType<elemType> - this is your class that contains entire tree? Then it should have inside it:

nodeType *root;

And when it is initialised (write constructor for object) root = NULL;
Then inside insert() function, check if(root == NULL) root = &temp; that's how you will initialise root

[RayvenHawk]

Ok here is what I have now:

Header file

template<class elemType>
void binaryTreeSearch<elemType>::insert(const elemType &insertItem)
{
	nodeType<elemType> *current;
	nodeType<elemType> *trailCurrent;
	nodeType<elemType> *newNode;

	newNode = new nodeType<elemType>;
	newNode->info = insertItem;
	newNode->llink = NULL;
	newNode->rlink = NULL;

	if (root == NULL)
		root = newNode;
		root = &temp;
	else
	{
		current = root;

		while (current != NULL)
		{
			trailCurrent = current;

			if (current->info == insertItem)
			{
				cout << "The item to be inserted is already in the tree ";
				cout << "duplicates are not allowed." <<endl;
				return;
			}
			else if (current->info < insertItem)
				current = current->llink;
			else
				current = current->rlink;
		}

		if (trailCurrent->info < insertItem)
			trailCurrent->llink = newNode;
		else
			trailCurrent->rlink = newNode;
	}
}

I typed in "tree.swapSubtreeNodes(root);"

But when I compile it tells me it's an undeclared value.

[RayvenHawk]

Thanks a ton Sci@phy. I managed to figure out where my flaw was. I was trying to call the function from main without any values, but my function needed values in order to work.

Problem was I couldn't seem to reference "root" in the main program. Even though it exists in BinaryTree.h.

So what I did was use the same scheme as printTree (which is have 2 void functions, one w/ values & one that calls that function up). And viola! it works great.

Here is what I did.

template<class elemType>
void binaryTreeType<elemType>::swapSubtreeNodes()
{
	swapSubtreeNodes(root); // display new root
}

template<class elemType>
void binaryTreeType<elemType>::swapSubtreeNodes(nodeType<elemType> *p)
{
	nodeType<elemType> *root; //create pointer for root
	nodeType<elemType> *temp; //create pointer for temp
   if (p==NULL) 
   {
      return;
   }
   else 
   {

      // do the subtrees
	  swapSubtreeNodes(p->llink);
      swapSubtreeNodes(p->rlink);
      // swap the pointers in this node
      temp = p->llink;
      p->llink = p->rlink;
      p->rlink = temp;
	
   }
	   root = temp; // set root to equal temp
}

In main I just call tree.swapSubtreeNodes();. The formatting was sucky, but I'm not concerned with that.

You were a great help, very much appreciated. Thank god this term is almost over, I HATE this Data Structures class.

[Sci@phy]

Yeah, that's what I would tell you :) Nice job