Suppose you have an array which is looped n times. and its tree structure looks something like following. Where each node is an array, except the leaf nodes which are strings.
So, lets see nodes which are array A,B,E,G,G,J,K .Leaf nodes which are strings C,D,F,H,I,L,M,N,O,P.
I hope you get the picture. Basically this is an N-ary tree. Now I am going to tell you how to write a breadth first traversal on this N-ary tree.
NSArray *A= [NSArray arrayWithObjects:[NSArray arrayWithObjects:[NSArray arrayWithObjects:@"M",@"N",nil],@"H",@"I"],@"C",@"D",[NSArray arrayWithObjects:[NSArray arrayWithObjects:@"O",nil],[NSArray arrayWithObjects:@"P",nil],nil],@"F", [NSArray arrayWithObjects:@"L",nil],nil];
You start with A store it in an array say tempArray, read all the children of A.
append all the children to tempArray, now read all those children's children one by one and keep appending.
Storing data in above given format is not the most optimum way, but this article is not about finding the optimum way to store your data. It is about how to read through the looped array.
BOOL noLeaves=TRUE;
int totalChildren=0;
NSMutableArray *tempArray=[[NSMutableArray alloc]initWithArray:A];
NSMutableArray *childrenAtNode=[[NSMutableArray alloc]init];
NSMutableString *childrenAtNodeString=[[NSMutableString alloc]initWithString:@""];
while (noLeaves)
{
int p=0;
for (int count=0; count<[A count]; count++)
{
if([[A objectAtIndex:count] isKindOfClass:[NSString class]])
{
totalChildren++;
}
else if([[A objectAtIndex:count] isKindOfClass:[NSArray class]])
{
[childrenAtNode addObject:[NSNumber numberWithInt:[[A objectAtIndex:count] count]]];
[tempArray removeObjectAtIndex:0];
p=1;
NSArray *childArray=[A objectAtIndex:count];
for (int child=0; child < [childArray count]; child++)
{
[tempArray addObject:[childArray objectAtIndex:child]];
}
}
}
A=[[NSArray alloc]initWithArray:tempArray];
if(p==0)
noLeaves=FALSE;
else
{
for (int i=0;i<[childrenAtNode count];i++)
[childrenAtNodeString appendFormat:@"%i,",[[childrenAtNode objectAtIndex:i] intValue]];
[childrenAtNodeString appendString:@":"];
}
[childrenAtNode removeAllObjects];
}
NSLog(@"totalChildren=%i",totalChildren);
NSLog(@"childrenAtNodeString=%@",childrenAtNodeString); //This will print like 6:3,0,0,2,0,1: .... so you can figure out very easily, that level 1 in tree have 6 nodes. first node has 3 children, second node is a leaf node
NSLog(@"A=%@",A);
No comments:
Post a Comment