Prev: search operation
Next: Heap
From: sophia on 14 Apr 2008 08:52
Dear all,

what are the corrections/improvements needed in the following program
which shows the re-construction of a binary tree from inorder and
preorder traversals ?


#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<limits.h>

typedef struct node
{
struct node *left;
int val;
struct node *right;
}sn;

void inordert(sn*);
void freetree(sn*);

int getcount(int*);
int getroot(int*,int);
int getminindex(int*,int);
int* getleft(int,int*,int*);
int* getright(int,int*,int*);

sn* reconst(int,int*,int);
sn* allocate(int);


int preorder[] = {'A','B','D','G','H','C','E','F','I','K','J',0};


int main(void)
{
int inorder[] = {'B','G','H','D','A','E','C','I','K','F','J',0};
int i,arc;

sn* t=NULL;


arc = getcount(inorder);

t= reconst(preorder[0],inorder, arc);

printf("after reconstruction of the binary tree\n");
inordert(t);

freetree(t);

return EXIT_SUCCESS;
}



sn* reconst(int root,int *inorder,int arc)
{

int *nla,*nra,nlarc,nroot,i;
int nrarc;

sn* temp =NULL;
nlarc=nrarc=0;

if(arc == 0)
return NULL;

temp = allocate(root);

if(arc == 1)
return temp;

nla = getleft(root,inorder,&nlarc);
nroot = getroot(nla,nlarc);
temp -> left = reconst(nroot,nla,nlarc);
free(nla);


nra = getright(root,inorder,&nrarc);
nroot = getroot(nra,nrarc);
temp -> right = reconst(nroot,nra,nrarc);
free(nra);

return temp;
}

int getcount(int *inorder)
{
int count=0,i;

for(i=0;inorder[i] != 0;i++)
count++;

return count;
}


sn* allocate(int n)
{
sn* temp;
temp = malloc(sizeof(*temp));

if(!temp)
{
printf("\n memory allocation failed....");
printf("\n going to abort.....");
exit(1);
}

temp -> val = n;
temp -> left = NULL;
temp -> right = NULL;

return temp;
}


int* getleft(int root,int *inorder,int *larc)
{

int i,count;
int *nla;

i=0,count=0;


while(inorder[i] != root)
{ i++;count++;}

nla = malloc((count+1) * sizeof(*nla));
nla[count] =0;

for(i=0;i < count;i++)
nla[i] = inorder[i];

*larc = count;

return nla;

}


int getroot(int *in,int n)
{
int i,j=0,k;
int* indxarray = malloc(n * sizeof(*indxarray));


if(indxarray == NULL)
{
printf("\n memory allocation failed....");
exit(1);
}

memset(indxarray,-1,n);

for(k=0;k<n;k++)
{
i=0;
while(preorder[i])
{
if(preorder[i] == in[k])
indxarray[k] = i;

i++;
}

}

j = getminindex(indxarray,n);

return in[j];
}



int getminindex(int *index,int n)
{
int loc = -1;
int min = INT_MAX;
int i;



for(i=0;i<n;i++)
{
if(index[i] < min)
{
min = index[i];
loc = i;
}
}

return loc;
}


int* getright(int root,int *inorder,int *larc)
{

int i,count,pos,k;
int *nra,ncount;

i=0,count=0,pos=0,ncount=0;


while(inorder[i] != root)
{ i++;pos++;}

count = getcount(inorder);

ncount = (count-pos-1);

nra = malloc( (ncount+1) * sizeof(*nra));
nra[ncount] =0;

k = (pos+1);

for(i=0;i < ncount;i++)
{
nra[i] = inorder[k];
k++;
}

*larc = ncount;

return nra;

}


void inordert(sn *hd)
{
if(hd != NULL)
{
inordert(hd -> left);
printf("\t %c",hd -> val);
inordert(hd -> right);
}
}


void freetree(sn* hd)
{
if(hd)
{
freetree(hd -> left);
freetree(hd -> right);
}

free(hd);
}
From: Richard Heathfield on 14 Apr 2008 09:45
sophia said:

> Dear all,
>
> what are the corrections/improvements needed in the following program

What are your thoughts on this? What have you tried? What are you stuck on?

<snip>

--
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999
From: sophia on 14 Apr 2008 11:06
On Apr 14, 6:45 pm, Richard Heathfield <r...(a)see.sig.invalid> wrote:
> sophia said:
>
> > Dear all,
>
> > what are the corrections/improvements needed in the following program
>
> What are your thoughts on this? What have you tried? What are you stuck on?

well my program is actually based on the diagrams given here:-

http://s297.photobucket.com/albums/mm220/sophiaagnes/
 | 
Pages: 1
Prev: search operation
Next: Heap