Trees

[cis]

In my program i got the tree to print out side ways. Could someone help me print out the tree from top to bottom.

I would like to print it out from top to bottom

Like this

ex.
-----------------------------------------------------

d
/ \
b f
/ \ / \
a c e g

This is my code.
==============================

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <time.h>

//Structure Definition
typedef struct node
{
int data;
struct node *left;
struct node *right;
}*bptr;

bptr root=NULL;


int EnterRequest();
void CreateTree(bptr *btree,int item);
void Inorder(bptr btree);
void Preorder(bptr btree);
void Postorder(bptr btree);
bptr Find(bptr btree,int key);
void PrintTree(bptr btree,int i);
bptr Bdelete(bptr btree,int key);
void ExitPrg();

int EnterRequest()
{
int request;

printf("\nPlease enter the request\n");
printf("\n");
printf("1.CreaetTree\n");
printf("2.PrintOrderTree\n");
printf("3.Find a node\n");
printf("4.PrintTree\n");
printf("5.Delete a node\n");
printf("6.Exit\n");
printf("\n");
printf("?");
scanf("%d",&request);
printf("\n");
return request;
}

void CreateTree(bptr *btree ,int value)
{
if(*btree == NULL)
{
*btree=(node *) malloc(sizeof(struct node));

if(*btree != NULL )
{
(*btree)->data = value;
(*btree)->left = NULL;
(*btree)->right = NULL;
}
else
printf("%d not inserted. No memory available.\n", value);
}
else
if(value < (*btree)->data)
CreateTree( & ((*btree)->left),value);
else if(value > (*btree)->data)
CreateTree( & ((*btree)->right),value);
else
printf("(%d dupl.) ",value);
}

void Inorder(bptr btree)
{

if(btree!=NULL)
{
Inorder(btree->left);
printf("%d ",btree->data);
Inorder(btree->right);
}

}


void Preorder(bptr btree)
{
if(btree!=NULL)
{
printf("%d ",btree->data);
Preorder(btree->left);
Preorder(btree->right);
}

}


void Postorder(bptr btree)
{
if(btree!=NULL)
{
Postorder(btree->left);
Postorder(btree->right);
printf("%d ",btree->data);
}
}


bptr Find(bptr btree,int key)
{
int i=0;
if(btree==NULL)
return NULL;
else
{
while(btree->data!=key)
{

if(key>btree->data)
{ btree=btree->right;
i++;
}
else
{ btree=btree->left;
i++;
}
}
}
if(btree->left||btree->right)
{
printf("Value of the node is %d\n", btree->data);
if(btree->left)
{
btree=btree->left;
printf("And the children of the node is %d\n",btree->data);
}
else
{
btree=btree->right;
printf("And the children of the node is %d\n",btree->data);
}
}
else
{
printf("%d is a leaf\n",btree->data);
}

printf("Which is at the Level %d \n",i);
return btree;
}



void PrintTree(bptr btree,int space)
{
int j;

while(btree!=NULL)
{
PrintTree(btree->right,space+3);

for(j=1;j<space;j++)
{
printf(" ");
}
printf("%d\n",btree->data);
btree=btree->left;
space+=3;
}
return;
}


bptr Bdelete(bptr btree,int key)
{
bptr p1,p2;

if(!btree)
return btree;

if(btree->data==key)
{
if(btree->left==btree->right)
{
free(btree);
return NULL;
}

else if(btree->right==NULL)
{
p1=btree->left;
free(btree);
return p1;

}

else if(btree->left==NULL)
{
p1=btree->right;
free(btree);
return p1;
}
else
{
p1=btree->right;
p2=btree->right;

while(p1->left)
{
p1=p1->left;
p1->left=btree->left;
free(btree);
return p2;
}
}
}
if(btree->data<key)
btree->right=Bdelete((btree->right),key);
else
btree->left=Bdelete(btree->left,key);
return btree;

}



void ExitPrg()
{
clrscr();
printf("\nHAVE A NICE DAY!");
exit(0);
}



int main()
{
bptr res;

int item,key,req,space=0,count;

do
{
req=EnterRequest();

switch(req)
{
case 1:
count=1 ;
root = NULL;
srand(time( NULL ));
while(count <=15 )
{
item = rand() %100;
if(item >= 10)
{
CreateTree(&root,item);//calling the CreateTree Fn
count++;
}
}
Inorder(root);//calling the Inorder Fn inoder to dispaly the
getch();//values being Inserted
break;
case 2:
printf("\nInorder\n");
Inorder(root);
printf("\nPreorder\n");
Preorder(root);
printf("\nPostorder\n");
Postorder(root);
getch();
break;
case 3:
printf("\nEnter the node to be searched for\n");
scanf("%d",&key);
if(key<10||key>100)
{
printf("Please Enter an appropriate value\n");
req=EnterRequest();
}
else
{
clrscr();
res=Find(root,key);
printf("\nThe node is %d",res->data);
}
break;
case 4:
clrscr();
printf("\nPrint's The Two-Dimesional Tree\n");
PrintTree(root,space);
getch();
break;
case 5:
printf("\nEnter the node to be deleted\n");
scanf("%d",&key);
root=Bdelete(root,key);
getch();
clrscr();
Inorder(root);
break;
case 6:ExitPrg();
break;
}
} while(req!=6);

getch();
return(0);
}

[cis]

void PrintTree(bptr btree,int space)
{
int j;

while(btree!=NULL)
{
PrintTree(btree->right,space+3);

for(j=1;j<space;j++)
{
printf(" ");
}
printf("%d\n",btree->data);
btree=btree->left;
space+=3;
}
return;
}

[Nick]

You can use a queue. The basic method is to do something like

queue q;

q.push(root);
while(!q.empty()) {
         n = q.pop();
         print(n);
         q.push(n->left);
         q.push(n->right);
}

[Prelude]

A simple if inefficient method is to use a height variable. To simulate a line order traversal, start with the root node (height 0) and print it, then go to the left leaf and increment height. Print the value and return to the root and repeat the process for the right leaf. When you print all possible values in a height level you increment the height variable and print the next line. By only printing the values at a certain height you can print the tree in line order very simply:

Height = 0:        d
Height = 1:     /     \
Height = 1:    b       f
Height = 2:   / \     / \
Height = 2:  a   c   e   g
Height = 3: / \ / \ / \ / \
Height = 3: * * * * * * * *

-Prelude