Building and inorder traversal of tree: > 2 sons

Question

I need to read in from an Access database a list of members. Each member was sponsored by another member. Each record contains the ID of their sponsor and their own ID. I now must be able to efficiently read in the membership roster and print it out indenting to show who was sponsored by who.

I feel the most efficient way to do this will be to build a tree and then do an inorder traversal.

My output should look something like this:

 Mary Jones
     Kim Smith
     Rena Brown
      Joan Brown
        Patsy Brown
     Howard Sharp
     Ken Johnson
 Peter Pan
     Wendy
     Hook
 Davey Crocket
     …

Order will be by ID number. Everything I find is for a Binary Tree with just a right and left son. As you see this will not work for me.

The preferred solution is Java but will appreciate anything I can get.

Bonnie

Answer 1

Here's what I came up with. It defines a function named ListSponsoredMembers and calls it recursively to build the list:

import java.sql.*;

public class ListSponsorship {
    static Connection conn;

    public static void main(String[] args) {
        try {
            conn = DriverManager.getConnection(
                    "jdbc:ucanaccess://C:/Users/Public/Database1.accdb;");
            PreparedStatement ps1 = conn.prepareStatement(
                    "SELECT memberID, memberName FROM Members " +
                    "WHERE sponsorID IS NULL ORDER BY memberID");
            ResultSet rs = ps1.executeQuery();
            while (rs.next()) {
                ListSponsoredMembers(rs.getInt("memberID"), rs.getString("memberName"), 0);
            }
            ps1.close();
            conn.close();
        } catch(Exception e) {
            e.printStackTrace();
        }
    }

    private static void ListSponsoredMembers(Integer memberID, String memberName, Integer recursionLevel) {
        for (Integer i = 0; i < recursionLevel; i++) {
            System.out.print("  ");
        }
        System.out.println(memberName);
        try {
            PreparedStatement ps2 = conn.prepareStatement(
                    "SELECT memberID, memberName FROM Members " +
                    "WHERE sponsorID=? ORDER BY memberID");
            ps2.setInt(1, memberID);
            ResultSet rs = ps2.executeQuery();
            Integer newRecursionLevel = ++recursionLevel;
            while (rs.next()) {
                ListSponsoredMembers(rs.getInt("memberID"), rs.getString("memberName"), newRecursionLevel);
            }
        } catch (SQLException e) {
            e.printStackTrace();
        }
    }

}

For a [Members] table that looks like this...

memberID  memberName     sponsorID
--------  -------------  ---------
       1  Mary Jones              
       2  Kim Smith              1
       3  Rena Brown             1
       4  Joan Brown             3
       5  Patsy Brown            4
       6  Howard Sharp           1
       7  Ken Johnson            1
       8  Peter Pan               
       9  Wendy                  8
      10  Hook                   8
      11  Davey Crocket           

...it produces the following output:

Mary Jones
  Kim Smith
  Rena Brown
    Joan Brown
      Patsy Brown
  Howard Sharp
  Ken Johnson
Peter Pan
  Wendy
  Hook
Davey Crocket