Question 4 (25 points)

Class Person represents people and their children. Complete the implementation of method printFamily so that it lists a peson and all of the person's descendant's, by generation, i.e., first the person, then the person's children (in any order), then the person's grandchildren (in any order), etc.

For example, invoking the printFamily() method on person A, whose family tree is given at bottom, could output the names A, B, C, D, E, F, G, H, I, J (one per line). Assume that no one has more than 999 descendants.

Hint: This is quite similar to the floodfill algorithm of Program 5.

Solution

public class Person

{

. . .

private String name; // The person's name.

// The children of a person are child[ 0 ] , ... , child[ n_children- 1].

private int n_children;

private Person[] child;

. . .

// Print this and this's descendants, by generation.

public void printFamily()

{

// queue[ 0 ], ... , queue[ R - 1] is a ( possibly incomplete )

// list of this and this's descendents, by generation.

Person[] queue = new Person[ 1000 ];

int L;

int R;

// Set queue to contain just this.

L = 0; R = 1; queue[ 0 ] = this;

// Print entire family, by generation.

while( L < R )

{

for( int i = 0; i < queue[ L ].n_children; i++ )

queue[ R++ ] = queue[ L ].child[ i ];

System.out.println( queue[ L++ ].name );

}

} // printFamily

} // Person

Comments

This problem was quite well handled by those examinees who attempted it, suggesting that we could divide the students into those who actually did Program 5 and those who transcribed it.

Note how using n_children in the for-loop avoids the necessity of having to consider the state of array child when no children are present.

The loop condition is strictly L < R, and not L <= R. The latter condition will result in an index out of bounds error if a person happens to have exactly 999 descendants.