?
Solved

How to format output of unbalanced binary tree

Posted on 2009-03-31
3
Medium Priority
?
1,076 Views
Last Modified: 2013-12-14
Hello,
I am working on a class assigment, there is an optional part to print our binary tree in a two dimensional format.  I am able to put all nodes into a queue, I can print the queue in the order I wish the nodes to appear but my output is linear (all on one line).  The tree is unbalanced.
I would like the output to appear as the tree would visually appear. Node sequence input is:
50, 45, 65, 51, 66, 46, 35, 47, 38, 20, 25

                                                          50
                                              45                   65
                                    35            46        51        66
                              20        38           47
                                   25

because the tree is unbalanced I am having trouble formatting the output. Can this be done?  Do I need to add some node element that tracks depth of node when input?
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <iomanip>
#include <queue>
using namespace std;
 
struct treeNode { 
   struct treeNode *leftPtr;  /* pointer to left subtree */
   int data; /* node value */
   struct treeNode *rightPtr; /* pointer to right subtree */
};
typedef struct treeNode TreeNode; 
typedef TreeNode *TreeNodePtr; 
TreeNodePtr rootPtr = NULL; /* tree initially empty */
int counter=0, i=0;
/* function prototypes */
void insertNode( TreeNodePtr *treePtr, int value);
void inOrder( TreeNodePtr treePtr );
void preOrder( TreeNodePtr treePtr );
void postOrder( TreeNodePtr treePtr );
void findNode(TreeNode * treePtr, int key);
void deleteNode(int item);
struct treeNode * find_Insucc(treeNode *curr);
void findLargestNode(treeNode *treePtr);
void findSmallestNode(treeNode *treePtr);
void bfs(const treeNode * pNode);
int main()
{ 	
	int userselect;
	int item=0;
	do
	{	/*begin user driven menu*/
		cout<<endl<<endl<<"1. Insert Value. "<<endl;
		cout<<"2. Print Tree. "<<endl;
		cout<<"3. Find Node. "<<endl;
		cout<<"4. Delete Node. "<<endl;
		cout<<"5. Find Smallest Node. "<<endl;
		cout<<"6. Find Largest Node. "<<endl;	
		cout<<"7. Print 2D Tree. "<<endl;
		cout<<"8. Quit."<<endl;
		cin>>userselect;
		switch(userselect)
		{
		case 1:
			{	
				int selection=0;
				cout<<"Read from File? (1=Yes 2=No)"<<endl;
				cin>>selection;
				if(selection==1)
				{
					FILE *fp;
					fp = fopen("N:\\myfile.txt", "r");
					while(!feof((fp)))
					{
						fscanf(fp, "%d", &item);
						insertNode( &rootPtr, item);
					}
				}
				if(selection==2)
				{
					int amount=0;
					cout<<"How many nodes to enter:";
					fflush(stdin);
					cin>>amount;
					for(i=0; i<amount; i++)
					{
						cout<<"Enter integeer: "<<endl;
						cin>>item;
						insertNode( &rootPtr, item);
					}
				}
				break;
			}
		case 2:
			{	
				if(rootPtr==NULL)
					cout<<endl<<"Tree is EMPTY!"<<endl;
				else
				{
					cout<<endl<<"The preOrder traversal is:"<<endl;
					preOrder( rootPtr );
					cout<<endl<<"The inOrder traversal is:"<<endl;
					inOrder( rootPtr );	
					cout<<endl<<"The postOrder traversal is:"<<endl;
					postOrder( rootPtr );
				}
				break;
			}
		case 3:
			{
				counter=0;
				cout<<endl<<"Enter value to find:"<<endl;
				fflush(stdin);
				cin>>item;
				findNode(rootPtr, item);
				break;
			}
		case 4:
			{
				cout<<endl<<"Enter value to remove: "<<endl;
				fflush(stdin);
				cin>>item;
				deleteNode(item);
				break;
			}
		case 5:
			{
				cout<<endl<<"Smallest Node is: ";
				findSmallestNode(rootPtr);
				break;
			}
		case 6:
			{
				cout<<endl<<"Largest Node is: ";
				findLargestNode(rootPtr);
				break;
			}	
		case 7:
			{
				bfs(rootPtr);				
				break;
			}
		case 8:
			{
				return 0;
			}
		}
 
	}
	while(userselect!=8);
   return 0; 
}
void insertNode( TreeNodePtr *treePtr, int value)
{  	
   if ( *treePtr == NULL ) 
   {   
	   (*treePtr) = (struct treeNode *) malloc (sizeof(TreeNode));
	  
      if ( *treePtr != NULL ) 
	  { 		  
         ( *treePtr )->data = value;
         ( *treePtr )->leftPtr = NULL;
         ( *treePtr )->rightPtr = NULL;
      } 
      else 
		  cout<<value<<" not inserted.  Mem not available"<<endl;
   } 
   else 
   { 
      /* data to insert is less than data in current node */
      if ( value < ( *treePtr )->data ) 
		  insertNode( &( ( *treePtr )->leftPtr ), value );
      /* data to insert is greater than data in current node */
      else if ( value > ( *treePtr )->data ) 
		  insertNode( &( ( *treePtr )->rightPtr ), value );
      else 
	  {
		  int choice;
		  /* duplicate data value ignored */
		  cout<<"Duplicate integer exists, enter another? (1=Y or 2=N)"<<endl;
		  cin>>choice;
		  if(choice==1)
			  i--;
	  }
   } 
}
void preOrder( TreeNodePtr treePtr )
{
	if ( treePtr != NULL ) 
	{ 
		cout<<"   "<<treePtr->data;
		preOrder( treePtr->leftPtr );
		preOrder( treePtr->rightPtr ); 
	}
} 
void inOrder( TreeNodePtr treePtr )
{
	if ( treePtr != NULL ) 
	{ 
		inOrder( treePtr->leftPtr );
		cout<<"   "<<treePtr->data;
		inOrder( treePtr->rightPtr );
   } 
}
 
void postOrder( TreeNodePtr treePtr )
{ 
   if ( treePtr != NULL ) 
   { 
      postOrder( treePtr->leftPtr );
      postOrder( treePtr->rightPtr );
	  cout<<"   "<<treePtr->data;
   } 
}
void findNode(TreeNode * treePtr, int key)
{	
	if ( treePtr == NULL ) 
	{
		cout<<key<<" DOES NOT EXIST IN TREE!"<<endl;
		return ;
	} 
	else if (key == treePtr->data)
	{
		cout<<treePtr->data<<" Found!"<<endl;
		if(counter==0)
			cout<<treePtr->data<<" is ROOT!"<<endl;		
		if(counter>0)
			cout<<counter<<" levels deep."<<endl;			
		if((treePtr->leftPtr==NULL) && (treePtr->rightPtr==NULL) && (counter>0))
			cout<<"Node is leaf"<<endl;			
		else
		{
			treeNode * conductor;
			if(treePtr->leftPtr!=NULL)
			{
				conductor=treePtr->leftPtr;
				cout<<conductor->data<<" is LEFT child."<<endl;
			}
			if(treePtr->rightPtr!=NULL)
			{
				conductor=treePtr->rightPtr;
				cout<<conductor->data<<" is RIGHT child."<<endl;
			}
		}
		return ;
	} 
	else if (key < treePtr->data) 
	{
		counter++;
		findNode(treePtr->leftPtr, key);
		return ;
	} 
	else 
	{
		counter++;
		findNode(treePtr->rightPtr, key);
		return ;		
	}
}
void deleteNode(int item)
{
    treeNode *curr=rootPtr,*succ,*pred;
    int flag=0,delcase;
    /*Find node */
    while(curr!=NULL && flag!=1)
    {
        if(item < curr->data)
		{
            pred = curr;
			curr = curr->leftPtr;
        }
        else if(item > curr->data)
		{
            pred = curr;
            curr = curr->rightPtr;
        }
        else
			flag=1;
    }
    if(flag==0)
	{
        cout<<endl<<"Item does not exist"<<endl;
		return ;
    }
    /*Determine if childeren exist*/
    if(curr->leftPtr==NULL && curr->rightPtr==NULL)
		delcase=1; //Node has no children
    else if(curr->leftPtr!=NULL && curr->rightPtr!=NULL)
        delcase=3; //Node contains children
    else
        delcase=2; //Node contains only one child
 
    if(delcase==1)
	{
        if(pred->leftPtr == curr) //if the node is a left child
            pred->leftPtr=NULL; //set pointer of its parent
        else
            pred->rightPtr=NULL;
        delete(curr); /*free allocated memory*/
    }
    if(delcase==2)
	{
        if(pred->leftPtr==curr)
		{ //if the node is a left child
			if(curr->leftPtr==NULL)
				pred->leftPtr=curr->rightPtr;
			else
				pred->leftPtr=curr->leftPtr;
        }
        else
		{ 
			if(curr->leftPtr==NULL)
				pred->rightPtr=curr->rightPtr;
            else
				pred->rightPtr=curr->leftPtr;
        }
        delete(curr);
    }
    if(delcase==3)
	{
		succ = find_Insucc(curr); /*Find the inorder successor*/                                         
        int item1 = succ->data;
        deleteNode(item1);  /*Delete the inorder successor*/
        curr->data = item1; /*Replace witn successor*/                              
    }
	return ;
}
struct treeNode * find_Insucc(treeNode *curr)
{
    treeNode *succ=curr->rightPtr; //Move to the right sub-tree.
    if(succ!=NULL)
	{
		while(succ->leftPtr!=NULL) //If right sub-tree is not empty.
			succ=succ->leftPtr; //move to the left-most end.
    }
    return(succ);
}
void findLargestNode(treeNode *treePtr)
{
    if( treePtr==NULL || treePtr->rightPtr==NULL)
		cout<<treePtr->data<<".";
    else
		findLargestNode(treePtr->rightPtr);
}
void findSmallestNode(treeNode *treePtr)
{
        if( treePtr==NULL || treePtr->leftPtr==NULL)
			cout<< treePtr->data<<".";
        else
            findSmallestNode( treePtr->leftPtr);
}
void bfs(const treeNode* pNode)
{  
	
	queue<const treeNode*> q;
	q.push(pNode);
	while (!q.empty())
	{
		pNode = q.front();
		if (pNode->leftPtr)
			q.push(pNode->leftPtr);
		if (pNode->rightPtr)
			q.push(pNode->rightPtr);
 
			cout<<"  "<<pNode->data;
 
		q.pop();
	}
}

Open in new window

0
Comment
Question by:Zorniac
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 2
3 Comments
 
LVL 39

Expert Comment

by:itsmeandnobodyelse
ID: 24030619
There are two problems:

1. The output would not fit on screen if the last level is greater 5 cause for level 5 you already have to output 32 numbers. Even if the numbers are 2 digits max you need 2 space chars (at least) between what gives 130 chars. A normal text console is only 80 and you would need to enlarge it anyhow.

2. Your current  traversions don't include a level order traversion which isn't quite easy to realize. I don't remember whether a level traversion can be done without a parent pointer for each node, but another choice than to level traversing is to fill up a new container where the numbers were organized in rows rather than in a tree. E. g. you could use a string array of size = max level and keep track of the level and position by using any of the other traversion functions. Then you would move each new entry exactly at the position in the level string where it belongs to. Or you use a 2d array of int where you copy the data of the tree into and finally output the 2d array calculating the proper offsets for each level and position.
0
 
LVL 39

Accepted Solution

by:
itsmeandnobodyelse earned 2000 total points
ID: 24031244
For solving (1) you could turn the output of the tree counter clockwise.

But that would require a 'column traversal' what is not easy to resolve even with additional node members. You better would fill a new data structure then for output where the traversal could be made easier than with following th echild pointers.

0
 
LVL 1

Author Closing Comment

by:Zorniac
ID: 31564897
Thanks,
I am in a time crunch so prior to popping the stack I created an array to hold the values.  Although this isn't dynamic and I hated to do it I was able to capture the node data to the array then with some very ugly code spit out the "desired" output.  This code will only be good for this particular situation
0

Featured Post

On Demand Webinar: Networking for the Cloud Era

Did you know SD-WANs can improve network connectivity? Check out this webinar to learn how an SD-WAN simplified, one-click tool can help you migrate and manage data in the cloud.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Templates For Beginners Or How To Encourage The Compiler To Work For You Introduction This tutorial is targeted at the reader who is, perhaps, familiar with the basics of C++ but would prefer a little slower introduction to the more ad…
Windows programmers of the C/C++ variety, how many of you realise that since Window 9x Microsoft has been lying to you about what constitutes Unicode (http://en.wikipedia.org/wiki/Unicode)? They will have you believe that Unicode requires you to use…
The viewer will learn how to use and create keystrokes in Netbeans IDE 8.0 for Windows.
The viewer will be introduced to the technique of using vectors in C++. The video will cover how to define a vector, store values in the vector and retrieve data from the values stored in the vector.
Suggested Courses

801 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question