Solved

How to format output of unbalanced binary tree

Posted on 2009-03-31
3
1,062 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
  • 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 500 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

Threat Intelligence Starter Resources

Integrating threat intelligence can be challenging, and not all companies are ready. These resources can help you build awareness and prepare for defense.

Join & Write a Comment

IntroductionThis article is the second in a three part article series on the Visual Studio 2008 Debugger.  It provides tips in setting and using breakpoints. If not familiar with this debugger, you can find a basic introduction in the EE article loc…
Container Orchestration platforms empower organizations to scale their apps at an exceptional rate. This is the reason numerous innovation-driven companies are moving apps to an appropriated datacenter wide platform that empowers them to scale at a …
The viewer will learn how to use and create keystrokes in Netbeans IDE 8.0 for Windows.
The goal of the video will be to teach the user the concept of local variables and scope. An example of a locally defined variable will be given as well as an explanation of what scope is in C++. The local variable and concept of scope will be relat…

757 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

Need Help in Real-Time?

Connect with top rated Experts

22 Experts available now in Live!

Get 1:1 Help Now