前言
作为电商网站，必然要有商品类目表，以便商品分类检索。而设计商品类目表，又是一件特别繁杂的事情。一件商品可能有多个类目来检索出来，比如苹果手机，可以从品牌检索也可以从手机检索。一个类目对应多个商品，比如手机下对应了多款属于手机类的商品。而类目是一个多叉树结构，类似于文件夹的结构。通常大电商都是把类目整理好了放在cache上，就不用频繁访问数据库和整理排序了。
个人类目标的结构设计
参考了一下网上无限级分类的表设计，简化模型为一个表内存在父子级从属关系。
表中的isRoot可以去掉，只要parent为0就认为是根节点就好了。而为什么不存子节点而是存父节点，因为子节点的映射类，生成整理的时候比存父节点要复杂一些，当然程序写的不复杂而是这个问题需要花费的时间就会多一些。
表设计好了之后，就需要查询数据并且整理出他们的从属关系。为了减少数据库的查询次数，我采用了全部查询，在内存中生成多叉树的形式。节点类的定义想法非常直接，它存在唯一识别：id，真实信息：name，以及它的子树：List or Map。
/
树型存储
/
class CategoryTree{
private long id;
private String name;
private List children;
public CategoryTree(){
children = new ArrayList();
}
public long getId() {
return id;
}
public void setId(long id) {
this.id = id;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public List getChildren() {
return children;
}
public void setChildren(List children) {
this.children = children;
}
}
/
哈希表存储
/
class CategoryMap{
private long id;
private String name;
private Map children;
public CategoryMap(){
children = new HashMap();
}
public long getId() {
return id;
}
public void setId(long id) {
this.id = id;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public Map getChildren() {
return children;
}
public void setChildren(Map children) {
this.children = //代码效果参考：http://hnjlyzjd.com/hw/wz_24902.html
children;}
}
在对乱序数组生成三级n叉树这个过程中，最快的方式是用map。在生成过程中，只能一级级生成，因为没有父节点不可能有子节点跟随这个逻辑的存在。
//集合存储
public void test1(){
tool.connection2MYSQL();
Connection conn = tool.getCon();
String sql = "select from category";
Statement stm = null;
List clist = new ArrayList();
try {
stm = conn.createStatement();
ResultSet rs = stm.executeQuery(sql);
while(rs.next()){
category c = new category();
c.setId(rs.getLong("id"));
c.setName(rs.getString("name"));
c.setParentId(rs.getLong("parent_id"));
c.setIsRoot(rs.getInt("is_root"));
clist.add(c);
}
tool.closeConn(conn);
} catch //代码效果参考：http://hnjlyzjd.com/xl/wz_24900.html
(SQLException e1) {// TODO Auto-generated catch block
e1.printStackTrace();
}
/
检查集合
/
// for(category ca:clist){
// System.out.println("id: "+ca.getId()+" name: "+ca.getName()+" parentId: "+ca.getParentId()+" isRoot: "+ca.getIsRoot());
// }
/
逻辑尝试=====
/
List roots = new ArrayList();
List second = new ArrayList();
List third = new ArrayList();
//一次遍历 添加根节点
int i = 0;
while(i != clist.size()-1){
if(clist.get(i).getParentId() == 0){
CategoryTree ct = new CategoryTree();
ct.setId(clist.get(i).getId());
ct.setName(clist.get(i).getName());
roots.add(ct);
clist.remove(i);
}else
i++;
}
//二次遍历 添加二级节点
for(int j=0;j
i = 0;
while(i [span style="color: rgba(0, 0, 0, 1)"> clist.size()){
if(clist.get(i).getParentId() == roots.get(j).getId()){
CategoryTree ct = new CategoryTree();
ct.setId(clist.get(i).getId());
ct.setName(clist.get(i).getName());
roots.get(j).getChildren().add(ct);
second.add(ct);//用空间换
clist.remove(i);
}else
i++;
}
}
//三次遍历 添加三级节点
for(int j=0;j
i = 0;
while(i [span style="color: rgba(0, 0, 0, 1)"> clist.size()){
if(clist.get(i).getParentId() == second.get(j).getId()){
CategoryTree ct = new CategoryTree();
ct.setId(clist.get(i).getId());
ct.setName(clist.get(i).getName());
second.get(j).getChildren().add(ct);
third.add(ct);//用空间换
clist.remove(i);
}else
i++;
}
}
for(category ca:clist){
System.out.println("id: "+ca.getId()+" name: "+ca.getName()+" parentId: "+ca.getParentId()+" isRoot: "+ca.getIsRoot());
}
for(CategoryTree ct:roots){
System.out.println("id: "+ct.getId()+" name: "+ct.getName());
{
for(CategoryTree ct1:ct.getChildren())
{
System.out.println("二级 id: "+ct1.getId()+" name: "+ct1.getName());
for(CategoryTree ct2:ct1.getChildren())
System.out.println("三级 id: "+ct2.getId()+" name: "+ct2.getName());
}
}
}/
逻辑尝试=====
/
}
我对每一级的节点做了一个额外的存储，在第三级生成的时候简化一个循环，也就是n平方的复杂度。
使用map生成的话，仅在生成这个过程，就可以把问题化简成n的复杂度。因为Map“知道”自己存储的对象的id，而List要通过遍历才知道它的自己存的元素的id。
public void test2(){
tool.connection2MYSQL();
Connection conn = tool.getCon();
String sql = "select from category";
Statement stm = null;
List clist = new ArrayList();
try {
stm = conn.createStatement();
ResultSet rs = stm.executeQuery(sql);
while(rs.next()){
category c = new category();
c.setId(rs.getLong("id"));
c.setName(rs.getString("name"));
c.setParentId(rs.getLong("parent_id"));
c.setIsRoot(rs.getInt("is_root"));
clist.add(c);
}
tool.closeConn(conn);
} catch (SQLException e1) {
// TODO Auto-generated catch block
e1.printStackTrace();
}
/**
逻辑尝试=====
/
Map rootMap = new HashMap();
Map secondMap = new HashMap();
//遍历一级
int i = 0;
while(i [span style="color: rgba(0, 0, 0, 1)"> clist.size()){
if(clist.get(i).getParentId() == 0){
CategoryMap cm = new CategoryMap();
cm.setId(clist.get(i).getId());
cm.setName(clist.get(i).getName());
rootMap.put(cm.getId(),cm);
clist.remove(i);
}else
i++;
}
//遍历二级
i = 0;
while (i [span style="color: rgba(0, 0, 0, 1)"> clist.size()) {
if (rootMap.get(clist.get(i).getParentId()) != null) {
CategoryMap cm = new CategoryMap();
cm.setId(clist.get(i).getId());
cm.setName(clist.get(i).getName());
rootMap.get(clist.get(i).getParentId()).getChildren().put(cm.getId(), cm);
secondMap.put(cm.getId(), cm);
clist.remove(i);
} else
i++;
}
//遍历三级
i = 0;
while (i [span style="color: rgba(0, 0, 0, 1)"> clist.size()) {
if (secondMap.get(clist.get(i).getParentId()) != null) {
CategoryMap cm = new CategoryMap();
cm.setId(clist.get(i).getId());
cm.setName(clist.get(i).getName());
secondMap.get(clist.get(i).getParentId()).getChildren().put(cm.getId(), cm);
clist.remove(i);
} else
i++;
}
// for (Map.Entry entry : rootMap.entrySet()) {
// System.out.println("Key = " + entry.getKey() + ", id : " + entry.getValue().getId()+" name : "+entry.getValue().getName());
// for (Map.Entry entry1 : entry.getValue().getChildren().entrySet()){
// System.out.println("二级 Key = " + entry1.getKey() + ", id : " + entry1.getValue().getId()+" name : "+entry1.getValue().getName());
// for (Map.Entry entry2 : entry1.getValue().getChildren().entrySet()){
// System.out.println("三级 Key = " + entry2.getKey() + ", id : " + entry2.getValue().getId()+" name : "+entry2.getValue().getName());
// }
// }
//
// }
JSONArray json = new JSONArray();
for (CategoryMap entry : rootMap.values()) {
JSONObject job1 = new JSONObject();
job1.put("id", entry.getId());
job1.put("name", entry.getName());
JSONArray joa1 = new JSONArray();
// System.out.println("id : " + entry.getId()+" name : "+entry.getName());
for (CategoryMap entry1 : entry.getChildren().values()){
JSONObject job2 = new JSONObject();
job2.put("id", entry1.getId());
job2.put("name", entry1.getName());
JSONArray joa2 = new JSONArray();
// System.out.println("二级 id : " + entry1.getId()+" name : "+entry1.getName());
for (CategoryMap entry2 : entry1.getChildren().values()){
JSONObject job3 = new JSONObject();
job3.put("id", entry2.getId());
job3.put("name", entry2.getName());
joa2.add(job3);
// System.out.println("三级 id : " + entry2.getId() + " name : "+entry2.getName());
}
job2.put("chird", joa2);
joa1.add(job2);
}
job1.put("chird", joa1);
json.add(job1);
}
for(int k=0;k
JSONObject jo = json.getJSONObject(k);
System.out.println(jo.toString());
}
/**
逻辑尝试=====
*/
}
最后的生成json的时候，仍然需要三次方的复杂度，我在考虑如何能在整理过程中顺带生成json，现在还没做出来，不过优化成n应该还是有机会的。
另外，遍历源数据的时候，把抽掉的节点remove掉也是一种减少重复遍历的方式。
最后生成的结果如同预期。
连接成功
{"chird":【{"chird":【{"name":"衬衣","id":16}】,"name":"七匹狼","id":6},{"chird":【{"name":"运动服","id":17}】,"name":"阿迪达斯","id":7}】,"name":"男装","id":1}
{"chird":【{"chird":【{"name":"毛衣","id":18}】,"name":"zara","id":8},{"chird":【{"name":"包包","id":19}】,"name":"普拉达","id":9}】,"name":"女装","id":2}
{"chird":【{"chird":【{"name":"笔记本电脑","id":20}】,"name":"dell","id":10},{"chird":【{"name":"台式电脑","id":21}】,"name":"lenovo","id":11}】,"name":"电脑","id":3}
{"chird":【{"chird":【{"name":"note","id":22}】,"name":"三星","id":12},{"chird":【{"name":"iPhone","id":23}】,"name":"苹果","id":13}】,"name":"手机","id":4}
{"chird":【{"chird":【{"name":"第一版","id":24}】,"name":"Java程序设计","id":14},{"chird":【{"name":"第三版","id":25}】,"name":"C++程序设计","id":15}】,"name":"图书","id":5}
总结
对于表设计和这个问题的解决不知道有没有更加规范一点的方式，还需要继续探讨。对于我们项目来说，这个方法已经可以适应了，商品分类我打算用个分类表来做映射，类目表叶子节点的id和商品的id存入，检索的时候根据叶子节点id检索所有商品。本次问题，在于对乱序数组转化为多叉树的模型建立，解决了这个问题，对转化思维又有了进一步的提高。（在这里其实问题的阶并不重要，因为这是有穷集合，类目表的条目基本不会超过几百，考虑的最多的就是访问量的问题，因为小电商不会做cache，每一次访问都生成三级树，所以本次问题重在如何用更好的运算模型去解决同一个问题）
追加
关于三级关系树的运用，我做了一个小的地域管理页面，与类目树是一样的结构。
<%@ page language="java" contentType="text/html; charset=UTF-8"
pageEncoding="UTF-8"%>
<%@include file="/common.jsp" %>
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" ""
[/span>html
[/span>head
[/span>script type="text/javascript" src="js/jquery.js"
<span style="color: rgb
