【JSON 处理】将JSON解析为树，并进行层次遍历和深度优先遍历

您所在的位置：网站首页 › 如何遍历json数据 › 【JSON 处理】将JSON解析为树，并进行层次遍历和深度优先遍历

【JSON 处理】将JSON解析为树，并进行层次遍历和深度优先遍历

2023-08-12 08:55| 来源: 网络整理| 查看: 265

1. 基本思路

2. 引入依赖

3. 定义节点

4. 定义树

5. 执行效果

1. 基本思路

我所采用的树形存储是 “孩子链表表示法” 存储

即，节点定义除了包含本节点相关信息（节点名、路径、层级、数据类型和具体数据）之外，还包含子节点链表

需要说明的是，我所采用的方法只适用于根节点为 JSONObject 类型的输入，不适用于根节点为 JSONArray

2. 引入依赖

实现借助于 fastjson，pom 文件加入配置：

com.alibaba fastjson 1.2.54 3. 定义节点

节点定义包含本节点相关信息（节点名、路径、层级、数据类型和具体数据）和子节点链表

package com.amwalle.walle.util; import java.util.List; public class JSONNode { private String nodeName; private String nodePath; private int level; private String dataType; private Object data; private List children; public String getNodeName() { return nodeName; } public void setNodeName(String nodeName) { this.nodeName = nodeName; } public String getNodePath() { return nodePath; } public void setNodePath(String nodePath) { this.nodePath = nodePath; } public int getLevel() { return level; } public void setLevel(int level) { this.level = level; } public String getDataType() { return dataType; } public void setDataType(String dataType) { this.dataType = dataType; } public Object getData() { return data; } public void setData(Object data) { this.data = data; } public List getChildren() { return children; } public void setChildren(List children) { this.children = children; } } 4. 定义树

层次遍历借助 Quene 实现，深度优先遍历借助 Stack 实现

package com.amwalle.walle.util; import com.alibaba.fastjson.*; import com.alibaba.fastjson.parser.Feature; import java.util.*; import java.util.concurrent.ConcurrentLinkedQueue; public class JSONTree { public static JSONNode createJSONTree(Object nodeData, String nodeName, String nodePath, int level) { JSONNode node = new JSONNode(); node.setNodeName(nodeName); node.setNodePath(nodePath); node.setLevel(level); node.setData(nodeData); if (nodeData == null) { node.setDataType(null); return node; } List childrenList = new LinkedList(); if (nodeData instanceof JSONObject) { node.setDataType("Object"); JSONObject jsonObject = (JSONObject) nodeData; Set keySet = jsonObject.keySet(); level++; for (String key : keySet) { JSONNode childNode = createJSONTree(jsonObject.get(key), key, nodePath + "/" + key, level); childrenList.add(childNode); } node.setChildren(childrenList); } else if (nodeData instanceof JSONArray) { node.setDataType("Array"); JSONArray jsonArray = (JSONArray) nodeData; for (int index = 0, size = jsonArray.size(); index < size; index++) { // Array 元素，不是单个节点；所以将元素下一级的孩子链表整个作为 Array 的孩子链表 JSONNode childNode = createJSONTree(jsonArray.get(index), nodeName, nodePath + "[" + index + "]", level); if (childNode.getChildren() != null) { childrenList.addAll(childNode.getChildren()); } } node.setChildren(childrenList); } else { node.setChildren(null); node.setDataType(nodeData.getClass().getName()); } return node; } public static List levelTraversal(JSONNode rootNode) { if (rootNode == null) { return null; } Queue queue = new ConcurrentLinkedQueue(); queue.add(rootNode); List nodeList = new LinkedList(); while (!queue.isEmpty()) { JSONNode node = queue.poll(); nodeList.add(node); if (node != null) { if (node.getChildren() != null) { queue.addAll(node.getChildren()); } } } return nodeList; } public static List depthFirstTraversal(JSONNode rootNode) { if (rootNode == null) { return null; } Stack stack = new Stack(); stack.push(rootNode); List nodeList = new LinkedList(); while (!stack.isEmpty()) { JSONNode node = stack.pop(); nodeList.add(node); if (node == null || node.getChildren() == null) { continue; } List children = node.getChildren(); for (int index = children.size() - 1; index >= 0; index--) { stack.push(children.get(index)); } } return nodeList; } public static void main(String[] args) { String data = "{\n" + " \"checked\": false,\n" + " \"dimensions\": {\n" + " \"width\": 5,\n" + " \"height\": 10\n" + " },\n" + " \"id\": 1,\n" + " \"name\": \"A green door\",\n" + " \"price\": 12.5,\n" + " \"tags\": [\n" + " \"home\",\n" + " \"green\"\n" + " ]\n" + "}"; JSONObject jsonObject = JSONObject.parseObject(data, JSONObject.class, Feature.OrderedField); JSONNode root = JSONTree.createJSONTree(jsonObject, "root", "#", 0); List list = JSONTree.depthFirstTraversal(root); for (JSONNode jsonNode : list) { System.out.printf("%" + (jsonNode.getLevel() * 4 + 1) + "s" + "%1$s%2$s%n", " ", jsonNode.getLevel() + "--" + jsonNode.getNodePath()); } } } 5. 执行效果

层次遍历结果：

0--# 1--#/checked 1--#/dimensions 1--#/id 1--#/name 1--#/price 1--#/tags 2--#/dimensions/width 2--#/dimensions/height

深度优先遍历结果：

0--# 1--#/checked 1--#/dimensions 2--#/dimensions/width 2--#/dimensions/height 1--#/id 1--#/name 1--#/price 1--#/tags

附加一个对 Array 进行了去重的构造方法：

package com.amwalle.walle.util; import com.alibaba.fastjson.JSONArray; import com.alibaba.fastjson.JSONObject; import com.alibaba.fastjson.parser.Feature; import java.util.*; import java.util.concurrent.ConcurrentLinkedQueue; public class JSONTree { private static HashSet pathSet = new HashSet(); /** * This method is used for creating a JSON Tree * * @param nodeData Node data * @param nodeName Node name * @param nodePath Node path * @param level Node level * @return The node */ public static JSONNode createJSONTree(Object nodeData, String nodeName, String nodePath, int level) { JSONNode node = new JSONNode(); node.setNodeName(nodeName); node.setNodePath(nodePath); node.setLevel(level); node.setData(nodeData); if (nodeData == null) { node.setDataType(null); return node; } node.setDataType(nodeData.getClass().getName()); List childrenList = new LinkedList(); if (nodeData instanceof JSONObject) { JSONObject jsonObject = (JSONObject) nodeData; Set keySet = jsonObject.keySet(); level++; for (String key : keySet) { JSONNode childNode = createJSONTree(jsonObject.get(key), key, nodePath + "/" + key, level); childrenList.add(childNode); } node.setChildren(childrenList); } else if (nodeData instanceof JSONArray) { JSONArray jsonArray = (JSONArray) nodeData; for (int index = 0, size = jsonArray.size(); index < size; index++) { // Array 元素，不是单个节点；所以将元素下一级的孩子链表整个作为 Array 的孩子链表 JSONNode childNode = createJSONTree(jsonArray.get(index), nodeName, nodePath + "[" + index + "]", level); if (childNode.getChildren() != null) { childrenList.addAll(childNode.getChildren()); } } node.setChildren(childrenList); } else { node.setChildren(null); } return node; } /** * This method is used for creating a JSON tree, in which all path for node is unique. * * @param nodeData Node data * @param nodeName Node name * @param nodePath Node path * @param level Node level * @return Node */ public static JSONNode createDeduplicateJSONTree(Object nodeData, String nodeName, String nodePath, int level) { JSONNode node = new JSONNode(); node.setNodeName(nodeName); node.setNodePath(nodePath); node.setLevel(level); node.setData(nodeData); if (nodeData == null) { node.setDataType(null); return node; } node.setDataType(NodeType.getJSONTypeByJavaType(nodeData.getClass().getSimpleName())); List childrenList = new LinkedList(); if (nodeData instanceof JSONObject) { JSONObject jsonObject = (JSONObject) nodeData; Set keySet = jsonObject.keySet(); level++; for (String key : keySet) { JSONNode childNode = createDeduplicateJSONTree(jsonObject.get(key), key, nodePath + "/" + key, level); if (childNode != null) { childrenList.add(childNode); } } node.setChildren(childrenList); } else if (nodeData instanceof JSONArray) { JSONArray jsonArray = (JSONArray) nodeData; for (Object aJsonArray : jsonArray) { // Array 元素，不是单个节点；所以将元素下一级的孩子链表整个作为 Array 的孩子链表 JSONNode childNode = createDeduplicateJSONTree(aJsonArray, nodeName, nodePath, level); if (childNode != null && childNode.getChildren() != null) { childrenList.addAll(childNode.getChildren()); } } node.setChildren(childrenList); } else { // 如果路径已经存在，则舍弃该节点 if (!pathSet.add(node.getNodePath())) { return null; } node.setChildren(null); } return node; } public static List levelTraversal(JSONNode rootNode) { if (rootNode == null) { return null; } Queue queue = new ConcurrentLinkedQueue(); queue.add(rootNode); List nodeList = new LinkedList(); while (!queue.isEmpty()) { JSONNode node = queue.poll(); nodeList.add(node); if (node != null) { if (node.getChildren() != null) { queue.addAll(node.getChildren()); } } } return nodeList; } public static List depthFirstTraversal(JSONNode rootNode) { if (rootNode == null) { return null; } Stack stack = new Stack(); stack.push(rootNode); List nodeList = new LinkedList(); while (!stack.isEmpty()) { JSONNode node = stack.pop(); nodeList.add(node); if (node == null || node.getChildren() == null) { continue; } List children = node.getChildren(); for (int index = children.size() - 1; index >= 0; index--) { stack.push(children.get(index)); } } return nodeList; } public static JSONObject createJSONSchema(JSONNode jsonNode, JSONObject jsonObject, String id) { jsonObject.fluentPut("$id", id); jsonObject.fluentPut("type", jsonNode.getDataType()); List children = jsonNode.getChildren(); if (children == null) { return jsonObject; } JSONObject schema = JSONObject.parseObject("{}", JSONObject.class, Feature.OrderedField); for (JSONNode node : children) { JSONObject childSchema = JSONObject.parseObject("{}", JSONObject.class, Feature.OrderedField); createJSONSchema(node, childSchema, id + "properties/" + node.getNodeName()); schema.fluentPut(node.getNodeName(), childSchema); } // TODO 在这里区分子节点的类别，然后判断应该加入什么关键字 if ("array".equals(jsonNode.getDataType())) { JSONObject arraySchema = JSONObject.parseObject("{}", JSONObject.class, Feature.OrderedField); arraySchema.fluentPut("$id", id + "/items"); if (jsonNode.getChildren().isEmpty()) { Object data = jsonNode.getData(); JSONArray dataArray = (JSONArray) data; if (!dataArray.isEmpty()) { arraySchema.fluentPut("type", NodeType.getJSONTypeByJavaType(dataArray.get(0).getClass().getSimpleName())); } } else { arraySchema.fluentPut("type", jsonNode.getChildren().get(0).getDataType()); arraySchema.fluentPut("properties", schema); } jsonObject.fluentPut("items", arraySchema); } else { jsonObject.fluentPut("properties", schema); } return jsonObject; } public static void main(String[] args) { String data = "{\n" + " \"TestNull\": null,\n" + " \"country\": [\n" + " {\n" + " \"A\": \"A\",\n" + " \"B\": \"B\",\n" + " \"C\": \"C\"\n" + " },\n" + " {\n" + " \"C\": \"C\",\n" + " \"D\": \"D\"\n" + " }\n" + " ],\n" + " \"fast_open\": false,\n" + " \"local_address\": \"127.0.0.1\",\n" + " \"local_port\": 1080,\n" + " \"method\": \"aes-256-cfb\",\n" + " \"password\": \"test%\",\n" + " \"server\": \"0.0.0.0\",\n" + " \"server_port\": 8388,\n" + " \"test\": [\n" + " \"hello\",\n" + " \"world\"\n" + " ],\n" + " \"timeout\": 300,\n" + " \"workers\": 1\n" + "}"; JSONObject jsonObject = JSONObject.parseObject(data, JSONObject.class, Feature.OrderedField); JSONNode root = JSONTree.createDeduplicateJSONTree(jsonObject, "root", "#", 0); JSONObject schema = JSONObject.parseObject("{}", JSONObject.class, Feature.OrderedField); assert root != null; createJSONSchema(root,schema,"/"); System.out.println(schema.toJSONString()); List list = JSONTree.depthFirstTraversal(root); assert list != null; for (JSONNode jsonNode : list) { System.out.printf("%" + (jsonNode.getLevel() * 4 + 1) + "s" + "%1$s%2$s%n", " ", jsonNode.getLevel() + "--" + jsonNode.getNodePath() + "--" + jsonNode.getDataType() + jsonNode.getChildren()); } } }

【本文地址】

【JSON 处理】将JSON解析为树，并进行层次遍历和深度优先遍历

【JSON 处理】将JSON解析为树，并进行层次遍历和深度优先遍历

今日新闻

推荐新闻