1. 引言

電商類的網(wǎng)站（比如：京東）為了便于用戶瀏覽商品，建立了一套類目體系，對(duì)商品進(jìn)行各種粗細(xì)粒度的劃分。類似地，用戶畫(huà)像的標(biāo)簽體系也劃分多層級(jí)的結(jié)構(gòu)。在做標(biāo)簽洞察時(shí)，需要將這種帶有層級(jí)的體系序列化json，提供給前端。但是，標(biāo)簽體系是存儲(chǔ)在MySQL數(shù)據(jù)庫(kù)中，為平鋪化的表結(jié)構(gòu)，如何將其表達(dá)為具有層次的數(shù)據(jù)結(jié)構(gòu)呢？多叉樹(shù)（Multiway Tree）正好能完美地詮釋類目體系，比如，一篇論文的結(jié)構(gòu)對(duì)應(yīng)于一棵多叉樹(shù)，如下圖所示：

從上圖可以看出，不同于二叉樹(shù)，多叉樹(shù)的非葉子節(jié)點(diǎn)的孩子節(jié)點(diǎn)數(shù)目可以為任意整數(shù)，而不僅局限于1或2。

2. 代碼實(shí)現(xiàn)

數(shù)據(jù)庫(kù)讀取

用DBUtils封裝從父節(jié)點(diǎn)得到所有子節(jié)點(diǎn)的方法：

public List<IDName> getChildren(String id) {
  ResultSetHandler<List<IDName>> h = new BeanListHandler<>(IDName.class);
  try {
    List<IDName> results = run.query("select ...", h, id);
    if (results.size() == 0) {
      results = run.query("select ...", h, id);
    }
    return results;
  } catch (SQLException e) {
    System.err.println("sql exception");
  }
  return null;
}

定義

多叉樹(shù)的樹(shù)節(jié)點(diǎn)定義如下：

public class TagTreeNode {
  private String id;
  private String name;
  private List<TagTreeNode> children = new LinkedList<>();

  public TagTreeNode(String id, String name) {
    this.id = id;
    this.name = name;
  }
  
  // gettter & setter
}

id與name為節(jié)點(diǎn)的屬性值，children為子節(jié)點(diǎn)list。

構(gòu)造

多叉樹(shù)的構(gòu)造大致分為兩類：BFS與DFS。數(shù)據(jù)庫(kù)讀取拿到的是父節(jié)點(diǎn)所有的子節(jié)點(diǎn)，因此只能采取BFS來(lái)構(gòu)造了。眾所周知，BFS遍歷時(shí)需要借助隊(duì)列用以緩存以訪問(wèn)的節(jié)點(diǎn)，Java實(shí)現(xiàn)代碼如下：

public class TagTree {
  public TagTreeNode root; // root node
  private Queue<TagTreeNode> queue = new LinkedList<>();

  // create multiway tree
  public TagTree(TagUtil td, Connection conn, String id, String name, Level level) throws SQLException {
    init(td, conn, id, name);
    generate(td, conn);
  }

  // add children nodes
  private void addChildren(TagUtil td, Connection conn, TagTreeNode parent) {
    List<IDName> idnames = td.getChildren(conn, parent.getId());
    if (idnames != null) {
      for (IDName idname : idnames) {
        TagTreeNode node = new TagTreeNode(idname.getId(), idname.getName());
        queue.add(node);
        parent.getChildren().add(node);
      }
    }
  }

  public void init(TagUtil td, Connection conn, String id, String name) {
    root = new TagTreeNode(id, name);
    addChildren(td, conn, root);
  }

  public void generate(TagUtil td, Connection conn) {
    while (!queue.isEmpty()) {
      TagTreeNode node = queue.remove();
      addChildren(td, conn, node);
    }
  }
}