SamuelXiao wrote:

> My program is to read data from a txt file to Binary Search Tree, then

> using a method that traverses the tree and prints to standard output

> the number of nodes which have exactly 2 great grand children. By

> far, i can read the data from a txt file but, for the search for

> exactly 2 great grand children, I still get no idea. I want to check

> the tree from root, whenever there is going down to level 2(which is

> the grand children level). I use a counter to count the nodes. then

> if (the counter>=2), check the counters. But this method seems to be

> failed as I want to use recursive function to do. Any one gives me

> idea? Any help would be appreciated. Thanks.

Here's an outline for a straightforward but not especially

efficient approach: Traverse the tree visiting each node in turn,

and if the node has exactly two great-grandchildren print it.

This approach decomposes into two sub-problems, the traversal

and the testing. The traversal is easy to do recursively:

to traverse a tree or sub-tree rooted at node N:

if N has exactly two great-grandchildren

print N

if N has a left child

traverse the sub-tree rooted at that child

if N has a right child

traverse the sub-tree rooted at that child

The other task is to count the great-grandchildren of node

N. Here's one way:

to count the great-grandchildren of N:

sum = 0

if N has a left child

sum += grandchildren of that child

if N has a right child

sum += grandchildren of that child

now we know N has exactly `sum' great-grandchildren

How to count the grandchildren? Same outline:

to count the grandchildren of N:

sum = 0

if N has a left child

sum += children of that child

if N has a right child

sum += children of that child

now we know N has exactly `sum' grandchildren

Now all you need is to be able to count the direct children of

a node N, and you're all set. But wait: There's an important

simplification available. Have you noticed that the way you

count great-grandchildren is structurally the same as the way

you count grandchildren? Instead of writing separate methods

for great-grandchildren, grandchildren, and children, maybe you

could write just one method to count the children K levels below

a node N and use it recursively:

to count the K-children of N:

sum = 0

if K > 0

if N has a left child

sum += the (K-1)-children of that child

if N has a right child

sum += the (K-1)-children of that child

now we know N has exactly `sum' K-children

As I said, this approach is not terribly efficient: It visits

every node once during the traversal, and up to three additional

times while counting descendants. The task can be done with less

running around, and I encourage you to try to find other ways.

--

Eric.Sosman@sun.com