Friday, November 13, 2009

Create tree from preorder traversal

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

int current=0;

struct bstree {
int val;
struct bstree *left,*right;
};

typedef struct bstree node;

node* tree_build(int* inarr,int* prearr,int left,int right);
void sort(int inarray[], int begin, int end);
void swap(int *a,int *b);
void inorder_traverse(node *ptr);
void bt_free(node *ptr);

main() {
int i;
int prearr[]={10,4,3,2,5,6,11,13,12};
int inarr[10];
for(i=0;i<9;i++)
inarr[i]=prearr[i];
sort(inarr,0,9);
node* root = tree_build(inarr,prearr,0,9);
printf("\n\nTREE CREATED. NOW DOING AN INORDER TRAVERSAL ON THE TREE...\n\n");
inorder_traverse(root);
printf("\n\n");
bt_free(root);
}

void bt_free(node *ptr) {
if(ptr==NULL)
return;
bt_free(ptr->left);
bt_free(ptr->right);
free(ptr);
}

void swap(int *a,int *b) {
int temp=*a;
*a=*b;
*b=temp;
}

void sort(int inarray[],int begin,int end) {
if (end > begin + 1) {
int pivot=inarray[begin],l=begin+1,r=end;
while(l if (inarray[l] <= pivot)
l++;
else
swap(&inarray[l],&inarray[--r]);
}
swap(&inarray[--l],&inarray[begin]);
sort(inarray,begin,l);
sort(inarray,r,end);
}
}

node* tree_build(int inarr[],int prearr[],int left,int right) {
int i,position;
if(left==right)
return NULL;
node *temp=(node *)malloc(sizeof(node));
temp->val=prearr[current];
if(left+1==right)
return temp;
i=left;
while(i if(inarr[i]==prearr[current])
break;
i++;
}
for(position=0;inarr[position]!=inarr[i];position++);
if(position>left) {
current++;
temp->left=tree_build(inarr,prearr,left,position);
}
if(position+1 current++;
temp->right=tree_build(inarr,prearr,position+1,right);
}
return temp;
}

void inorder_traverse(node *ptr) {
if(ptr==NULL)
return;
inorder_traverse(ptr->left);
printf(" %d - ",ptr->val);
inorder_traverse(ptr->right);
}

No comments:

Post a Comment