多叉树结构：JSON数据解析（二）
在上篇文章中提到了JSON数据解析的基本方法，但是方法效率太低，这里接着上篇文章写写如何利用多叉树结构，定义对象，实现JSON数据字段快速随机访问。
JSON数据通常就是无根节点的多叉树结构，对于这种无根节点的多叉树，要实现快速随机访问得经历两个过程：隐式构造根节点，建立多叉树和遍历多叉树。
3.2 优化的方法——无根节点多叉树随机访问
对于json的这种数据结构，目前大多数人的做法都是利用list，或者LinkedHashMap去实现，一层层地map套map的结构，非常麻烦。
其实仔细分析下json样本数据的结构就可以知道，其实很多json数据格式都是个没有根节点的多叉树，那么为什么不构造一个隐式的根节点呢？剩下的就是构造多叉树和多叉树的遍历过程了。
并且在随机访问方面，任意给定一个节点，我可以拿到该节点作为子树下所有节点，并且后续还可以扩展为另一种形式：通过节点拿到其所有同名兄弟节点（同层同名字段）。
分析下节点的分类：1.（只有值）无子节点；
2.（有值）有子节点：
2.1 有单子节点”ss_”开头标记
2.2 有多值节点”bb_”开头标记
定义几个节点对象，作为基础数据结构实现：
下面开始构建多叉树，然后遍历多叉树打印输出节点：
import java.io.File;
import java.io.IOException;
//import java.util.Iterator;
//import java.util.LinkedHashMap;
import org.apache.commons.io.FileUtils;
import com.alibaba.fastjson.JSONArray;
import com.alibaba.fastjson.JSONObject;
import com.data.jsontrans.entity.*; public class BuildTreeAction { RootNode root = new RootNode();
//SingleNode singlenode = new SingleNode();
//MultiNode multinode = new MultiNode();
//root.getChilds().add(singlenode);
//root.getChilds().add(multinode); public static void main(String[] args) throws IOException{
GetData();
} public static void GetData() throws IOException{
BuildTreeAction bdtree = new BuildTreeAction();
String json = FileUtils.readFileToString(new File("e:/data/json4.txt"));
JSONObject jsono = JSONObject.parseObject(json);
JSONObject b = jsono.getJSONObject("aggregations");
//bdtree.buildResult(b);
bdtree.BuildTree(b); Node node;
node = bdtree.CreateTree(b);
} public Node CreateTree(JSONObject b){
SingleNode snode = new SingleNode();
MultiNode mnode = new MultiNode();
RootNode rnode = new RootNode(); return rnode;
} public void BuildTree(JSONObject b){
for(String key : b.keySet()){
if(key.startsWith("bb_")){
MultiNode multinode = new MultiNode();
root.getChilds().add(multinode);
if(key.equals("bb_appId")){
multinode.setNodeId("bb_appId");
JSONObject buckets = b.getJSONObject(key);
JSONArray bArray = buckets.getJSONArray("buckets");
for(int i=0; i<bArray.size(); i++){
JSONObject o = bArray.getJSONObject(i);
multinode.setKey(o.get("key").toString());
multinode.setDoc_count(o.get("doc_count").toString());
System.out.println("key:"+multinode.key); //key:UZ6958037483314
System.out.println("doc_count:"+multinode.doc_count); //doc_count:361 for(String sub1_key : o.keySet()){
if(sub1_key.startsWith("bb_")){
MultiNode sub1_multinode = new MultiNode();
multinode.getChilds().add(sub1_multinode); //在bb_appId的multinode加上子节点"bb_?"
if(sub1_key.equals("bb_versionCode")){ sub1_multinode.setNodeId("bb_versionCode");
JSONObject sub1_buckets = o.getJSONObject(sub1_key);
JSONArray sub1_bArray = sub1_buckets.getJSONArray("buckets");
for(int j=0; j<sub1_bArray.size(); j++){
JSONObject o1 = sub1_bArray.getJSONObject(j);
sub1_multinode.setKey(o1.get("key").toString());
sub1_multinode.setDoc_count(o1.get("doc_count").toString());
System.out.println("key:" + sub1_multinode.key);
System.out.println("doc_count:" + sub1_multinode.doc_count); for(String sub2_key : o1.keySet()){
if(sub2_key.startsWith("bb_")){
MultiNode sub2_multinode = new MultiNode();
sub1_multinode.getChilds().add(sub2_multinode); //在bb_versionCode的sub1_multinode加上多子节点
if(sub2_key.equals("bb_isNewVersion")){
multinode.setNodeId("bb_isNewVersion");
JSONObject sub2_buckets = o.getJSONObject(key);
JSONArray sub2_bArray = sub2_buckets.getJSONArray("buckets");
for(int k=0; k<sub2_bArray.size(); k++){
JSONObject o2 = sub2_bArray.getJSONObject(k);
multinode.setKey(o2.get("key").toString());
multinode.setDoc_count(o2.get("doc_count").toString());
System.out.println("key:"+multinode.key);
System.out.println("doc_count:"+multinode.doc_count);
}
}
else if(sub2_key.equals("bb_isNew")){
sub2_multinode.setNodeId("bb_isNew");
JSONObject sub2_buckets = o1.getJSONObject(sub2_key);
JSONArray sub2_bArray = sub2_buckets.getJSONArray("buckets");
for(int k=0; k<sub2_bArray.size(); k++){
JSONObject o2 = sub2_bArray.getJSONObject(k);
sub2_multinode.setKey(o2.get("key").toString());
sub2_multinode.setDoc_count(o2.get("doc_count").toString());
System.out.println("key:"+sub2_multinode.key);
System.out.println("doc_count:"+sub2_multinode.doc_count);
}
} }
else if(sub2_key.startsWith("ss_")){
SingleNode sub2_singlenode = new SingleNode();
sub1_multinode.getChilds().add(sub2_singlenode); //在bb_versionCode的sub1_multinode加上单子节点
if(sub2_key.equals("ss_usercount")){
sub2_singlenode.setNodeId("ss_usercount");
sub2_singlenode.getSnode().setNodeId("value");
sub2_singlenode.getSnode().value = o1.getJSONObject("ss_usercount").getString("value");
System.out.println("ss_appId: "+"value:"+sub2_singlenode.getSnode().value);
} }
} }
}
/*else if(subkey1.equals("bb_versionId")){
//同上处理...
}*/
}
else if(sub1_key.startsWith("ss_")){
SingleNode sub1_singlenode = new SingleNode();
multinode.getChilds().add(sub1_singlenode); //在bb_appId的multinode加上子节点"ss_?"
if(sub1_key.equals("ss_versionCode")){
sub1_singlenode.setNodeId("ss_versionCode");
sub1_singlenode.getSnode().setNodeId("value");
sub1_singlenode.getSnode().value = o.getJSONObject("ss_appId").getString("value");
System.out.println("ss_appId: "+"value:"+sub1_singlenode.getSnode().value);
}
/*else if(sub1_key.equals("ss_versionId")){
//同上处理...
}*/
}
} }
} } else if(key.startsWith("ss_")){
SingleNode singlenode = new SingleNode();
root.getChilds().add(singlenode);
ss_mynode(b, key, singlenode, "ss_appId");
/*else if(key.equals("ss_usercode")){
//...其他"ss_usercode"同上类似处理...//
}*/ } else{
System.out.println("nothing");
} }
}
运行结果：
3.3 效率优化——迭代+递归实现
实际上树的构建和遍历通常用递归实现，这里迭代for循环判断节点就两种类型：单值”ss_”和多值”bb_”节点，这就足够了——for循环迭代+递归。基本思路就是循环依次读取每个节点，每次判断是否单值或多值节点，如果多值节点，继续以其下子节点作为parent再继续递归，传回的参数就是本次节点Node及层级编号。
import java.io.File;
import java.io.IOException;
import java.util.Iterator;
import java.util.List;
import java.util.ArrayList;
//import java.util.LinkedHashMap;
import org.apache.commons.io.FileUtils;
import com.alibaba.fastjson.JSONArray;
import com.alibaba.fastjson.JSONObject;
import com.data.jsontrans.entity.*; public class CreateTreeAction { public static void main(String[] args) throws IOException{
CreateTreeAction ctree = new CreateTreeAction();
String json = FileUtils.readFileToString(new File("e:/data/json4.txt"));
JSONObject jsono = JSONObject.parseObject(json);
JSONObject b = jsono.getJSONObject("aggregations");
Node root = ctree.buildJsonTree(b);
} public Node buildJsonTree(JSONObject b){
RootNode node = new RootNode(); //通用变量node
buildTree(node,b);
return node;
} public void buildTree(Node parent, JSONObject b) {
for(String key : b.keySet()){
if(key.startsWith("bb_")){
//MultiNode multinode = createMutilNode(b, key);
MultiNode multinode = new MultiNode();
multinode.setNodeId(key);
JSONObject buckets = b.getJSONObject(key);
JSONArray bArray = buckets.getJSONArray("buckets");
for(Iterator iterator = bArray.iterator(); iterator.hasNext(); ){
JSONObject o = (JSONObject) iterator.next();
if(o.get("key_as_string")!=null){
multinode.setKey_as_string(o.get("key_as_string").toString());
System.out.println(multinode.key_as_string);
}
multinode.setKey(o.get("key").toString());
multinode.setDoc_count(o.get("doc_count").toString());
System.out.println(multinode.key);
System.out.println(multinode.doc_count);
parent.getChilds().add(multinode);
buildTree(parent, o); //迭代计算buildTree()
}
//parent.getChilds().add(multinode);
}
else if(key.startsWith("ss_")){
//SingleNode singlenode = createSingleNode(b, key);
SingleNode singlenode = new SingleNode();
singlenode.setNodeId(key);
singlenode.value = b.getJSONObject(key).getString("value");
System.out.println("ss_ "+"value:"+singlenode.value);
parent.getChilds().add(singlenode);
} } } }
看下效果图：
（原创文章，转载请注明出处）