1. 引言

电商类的网站（比如：京东）为了便于用户浏览商品，建立了一套类目体系，对商品进行各种粗细粒度的划分。类似地，用户画像的标签体系也划分多层级的结构。在做标签洞察时，需要将这种带有层级的体系序列化json，提供给前端。但是，标签体系是存储在MySQL数据库中，为平铺化的表结构，如何将其表达为具有层次的数据结构呢？多叉树（Multiway Tree）正好能完美地诠释类目体系，比如，一篇论文的结构对应于一棵多叉树，如下图所示：

从上图可以看出，不同于二叉树，多叉树的非叶子节点的孩子节点数目可以为任意整数，而不仅局限于1或2。

2. 代码实现

数据库读取

用DBUtils封装从父节点得到所有子节点的方法：

public List
    
      getChildren(String id) {  ResultSetHandler
     
      
       > h = new BeanListHandler<>(IDName.class);  try {    List
       
         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;}
       
      
     
    

定义

多叉树的树节点定义如下：

public class TagTreeNode {  private String id;  private String name;  private List
    
      children = new LinkedList<>();  public TagTreeNode(String id, String name) {    this.id = id;    this.name = name;  }    // gettter & setter}
    

id与name为节点的属性值，children为子节点list。

构造

多叉树的构造大致分为两类：BFS与DFS。数据库读取拿到的是父节点所有的子节点，因此只能采取BFS来构造了。众所周知，BFS遍历时需要借助队列用以缓存以访问的节点，Java实现代码如下：

public class TagTree {  public TagTreeNode root; // root node  private Queue
    
      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
     
       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);    }  }}