My Weblog

Blog about programming and math

Multiway Tree

You are given a list of edges of tree in ( parent , child ) fashion and you have to create a tree using this list. This problem is bit challenging since this tree can have any number of children.Suppose we have list [ (7 8 ) (7 9) (7 11) (7 12 ) (4 5) (5 6) (6 7) (2 3 ) (3 4) (1 2) ] so you can see root 7 has four children 8,9,11,12. Although technically i don’t know if this is multiway tree or not . Any way its good problem to practice pointers.

#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<vector>
#include<map>
#include<queue>
using namespace std;

struct tree
   {
	int p;
	struct list  *l;
   };

struct list
   {
	struct tree *t;
	struct list *next;
   };
vector<pair<int,int> > v;
map<int,int> P;
multimap<int,int> M;
void creatTree(struct tree **nd, int a , int b)
	{
		if((*nd)->p==a)
		 {
			
			struct list *curr = (*nd)->l;
			if(curr==NULL)
			 {
				curr=(struct list *) malloc( sizeof ( struct list ) );
				curr->next = NULL;
                        	curr->t = (struct tree *) malloc ( sizeof ( struct tree ) );
                        	curr->t->p = b;
                        	curr->t->l = NULL;
				(*nd)->l=curr;
				return;
			 }

			while(curr->next!=NULL) curr=curr->next;
			curr->next = (struct list *) malloc( sizeof ( struct list ) );
			curr->next->next = NULL;
			curr->next->t = (struct tree *) malloc ( sizeof ( struct tree ) );
			curr->next->t->p = b;
			curr->next->t->l = NULL;	
				

		 }
		else 
		 {
			//traverse the whole list to find out suitable position for child
			struct list *curr = (*nd)->l;
			while(curr!=NULL) 
			 {
				creatTree( & ( curr->t ) , a , b );
				curr=curr->next;
			 }

		 }
	}

void print(struct tree *t,int lev)
	{
		cout<<"lev= "<<lev<<" node= "<<t->p<<endl;
		struct list *curr=t->l;
		while(curr!=NULL)
		 {
			print(curr->t,lev+1);
			curr=curr->next;
		}
	}	
	
int main()
	{
		struct tree *root;
		root=NULL;
		int n,a,b;
		cout<<"Enter number of edges\n";
		cin>>n;
		for(int i=0;i<n;i++) cin>>a>>b/*,v.push_back(make_pair(a,b))*/,P[b]=a,M.insert(pair<int,int>( a,b ));
		//search for root.	

		int rt=-1;
		for(map<int,int> :: iterator it = P.begin();it!=P.end();it++)
		 {
			a=it->first;
			b=it->second;
			if(P.count(b)==0) //this is my root 
			 {
				rt=b;
				break;
			 }
		 }
		
		//linear searching over list to get the root
		/*for(int i=0;i<n;i++) 
		 {
			bool flag=true;
			int tmp=v[i].first;
			for(int j=i+1;j<n;j++) 
			 {
				if(tmp==v[j].second) 
				 {
					flag=false;
					break;
				 }
			}
			if(flag) {rt=tmp;break;}
		}*/

		cout<<"root is "<<rt<<endl;
		

		if(rt==-1) cout<<"not tree.it contains cycles\n";
		root=(struct tree *) malloc( sizeof ( struct tree ) );
		root->p=rt;
		root->l=NULL;
		
		queue<int> Q;
		Q.push(rt);
		while(!Q.empty())
		 {
			int tmp=Q.front();Q.pop();
			for(multimap<int,int> :: iterator it=M.equal_range(tmp).first;it!=M.equal_range(tmp).second;it++)
			 {
				creatTree(&root,tmp,it->second);
				Q.push(it->second);
			 }
		 }
		//for(int i=0;i<n;i++)  creatTree(&root,v[i].first,v[i].second); 		

		print(root,0);
		
	}
			

This is sample test case and output.
[user@localhost TCL]$ ./a.out
Enter number of edges
10
7 8
7 9
7 11
7 12
4 5
5 6
6 7
2 3
3 4
1 2
root is 1
lev= 0 node= 1
lev= 1 node= 2
lev= 2 node= 3
lev= 3 node= 4
lev= 4 node= 5
lev= 5 node= 6
lev= 6 node= 7
lev= 7 node= 8
lev= 7 node= 9
lev= 7 node= 11
lev= 7 node= 12

Advertisements

April 29, 2011 - Posted by | Programming

No comments yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: