3 Replies - 5651 Views - Last Post: 25 August 2009 - 05:18 AM Rate Topic: -----

#1 vajrasen  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 5
  • Joined: 10-April 07

to merge the contents of two binary seach trees into one

Post icon  Posted 10 April 2007 - 12:21 AM

write a program in C lannguage to merge the contents of two binary search trees into one.Also, calculate the time and space complexities of your program

This post has been edited by vajrasen: 10 April 2007 - 08:20 AM

Is This A Good Question/Topic? 0
  • +

Replies To: to merge the contents of two binary seach trees into one

#2 Amadeus  Icon User is offline

  • g+ + -o drink whiskey.cpp
  • member icon

Reputation: 248
  • View blog
  • Posts: 13,506
  • Joined: 12-July 02

Re: to merge the contents of two binary seach trees into one

Posted 10 April 2007 - 05:36 AM

As mentioned with another of your posts, the site prefers that a good faith effort is shown by the user before providing source code. If you would care to post the code you've written, we would be pleased to provide some guidance.

Thanks.
Was This Post Helpful? 0
  • +
  • -

#3 avkthavil  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 1
  • Joined: 21-April 07

Re: to merge the contents of two binary seach trees into one

Posted 21 April 2007 - 06:04 AM

hi how r u?
i am fine

Was This Post Helpful? 0
  • +
  • -

#4 amool  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 1
  • Joined: 07-April 08

Re: to merge the contents of two binary seach trees into one

Posted 25 August 2009 - 05:18 AM

Hello!

This is the C code that i have come up with to do the merging of the BST trees.

I am getting an error and I'm not able to pin point that out. Also can somebody show me how to implement the Breadth First Search Traversal to the merged tree?

Please help me out...i really need a very quick reply to my post!
Sorry for the trouble and thanks in advance! :)

The code that i have written:

#include<stdio.h>
#include<alloc.h>
#include<process.h>

struct node
{
int info;
struct node *llink;
struct node *rlink;
};
typedef struct node* NODE;

NODE getnode()
{
NODE x;
x=(NODE)malloc(sizeof(struct node));
if (x==NULL)
{
printf("Out of memory\n");
exit(0);
}
return x;
}
/*void freenode(NODE x)
{
free(x);
}*/

NODE insert(int item,NODE root)
{
NODE temp,cur,prev;
temp=getnode();
temp->info=item;
temp->llink=NULL;
temp->rlink=NULL;

if(root==NULL) return temp;

prev=NULL;
cur=root;
while(cur!=NULL)
{
prev=cur;
cur=(item<cur->info)?cur->llink:cur->rlink;
}
if(item<prev->info)
prev->llink=temp;
else
prev->rlink=temp;
return root;
}

void postorder(NODE root)
{
if(root!=NULL)
{
postorder(root->llink);
postorder(root->rlink);
printf("%d ",root->info);
}
}

void merge(int a[],int b[],int c[],int m,int n)
{
int i,j,k;
i=j=k=0;
while(i<m && j<n)
{
if(a[i]<b[j])
{
c[k]=a[i];
i=i+1;
}
else
{
c[k]=b[j];
j=j+1;
}
k=k+1;
}
while(i<m)
c[k++]=a[i++];
while(j<n)
c[k++]=b[j++];
}

void display(NODE root,int i)
{
int j;
if(root!=NULL)
{
display(root->rlink,i+1);
for(j=1;j<=i;j++)
printf(" ");
printf("%d\n",root->info);
display(root->llink,i+1);
printf("\n");
}
}

void main()
{
NODE streeA,streeB,streeAB;
int item,a[20],b[20],c[40],i;
int m=0,n=0;
streeA=streeB=streeAB=NULL;
clrscr();
printf("Enter the items for the first Binary Search Tree(streeA) and terminate with ^Z\n");
while(scanf("%d",&item)==1)
{
streeA=insert(item,streeA);
a[m++]=item;
}
fflush(stdin);
printf("Enter the items for the second Binary Search Tree(streeB) and terminate with ^Z\n");
while(scanf("%d",&item)==1)
{
streeB=insert(item,streeB);
b[n++]=item;
}
printf("streeA contents are:\n");
display(streeA,1);
printf("streeB contents are:\n");
display(streeB,1);
printf("merged tree\n");
merge(a,b,c,m,n);
for(i=0;i<=m+n;i++)
{
streeAB=insert(c[i],streeAB);
}
fflush(stdin);
display(streeAB,1);
postorder(streeAB);
getch();
}
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1