java - 树的构建和中序遍历 : > 2 sons

Question

我需要从 Access 数据库读入成员列表。每个成员都由另一个成员赞助。每条记录都包含其赞助商的 ID 和他们自己的 ID。我现在必须能够有效地读取成员(member)名册并将其打印出来，并缩进以显示谁由谁赞助。

我认为最有效的方法是构建一棵树，然后进行中序遍历。

我的输出应该如下所示:

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

订单将按 ID 号进行。我找到的所有东西都是针对只有左右儿子的二叉树。如你所见，这对我不起作用。

首选的解决方案是 Java，但我会感激我能得到的任何东西。

邦妮

Answer 1

这就是我的想法。它定义了一个名为 ListSponsoredMembers 的函数，并递归调用它来构建列表:

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();
        }
    }

}

对于如下所示的 [Members] 表...

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           

...它产生以下输出:

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