用 JSON 表现树的结构兼谈队列、堆栈的练习(一)

  1. 云栖社区>
  2. 博客>
  3. 正文

用 JSON 表现树的结构兼谈队列、堆栈的练习(一)

sp42 2017-08-02 11:05:00 浏览1680
展开阅读全文

K/V 与 Array

接触 JSON 的人都知道,JSON 可通过 K/V(Key/Value) 结构很直观地表现一棵树,因为 V 可以“包含”另外一个 K/V 从而不断嵌套下去形成“树状”的结构。但 V 不一定必须为另外一个 K/V,而是可以为 Array 数组。数组中由可以“包含”更多的 K/V 或者又是数组类型——也是可以的。如此反复下去,可以形成层数很深的一棵树。例如

{
  aa : {
	cc :[
               “dd”,
               {
                   ee: true, ff: “hihi”
               }
          ]
  },
  bb: [  ]
}

这里说的树是指无序树,甚至根节点也没有,不过没关系,在最外一层加上便是。

比较微妙的是 JSON 允许了数组和 K/V 相互嵌套。下级子节点应该用 K/V 来装,还是用 Array 来装呢?又怎么理解数组和 K/V 的关系呢?个人理解,数组本质上也可以归纳其为 K/V。我们一般讨论数组时候还会接触到数组的索引,例如 arr[0] = a, arr[1] = b,索引便是 key 的一种,只不过我们通常 JSON 里面的 key 为字符串,实际上为 int 类型也是允许的。相较而言,数组结构比 K/V 的简单,是 K/V 的一种简化。当然我这种只是“大而化之”的理解,——实际上它们差别很多,好比它们的数据结就显著不同:数组仅仅是一个线性表;K/V 会复杂的多,一般要经过多步 hash 的运算。

再看看上面的 JSON 例子,看起来这个 JSON 想要表达很多东西,最外层是个 K/V,里面的 aa 是下一层的 K/V,但 bb 却是数组,——似乎结构有点混乱。如果用来表现一个树,显然也是一颗“混乱的树”。如果实际开发遇到这样结构的设计,那肯定有问题的,需要好好简化的。不过,无论怎么简化,一旦引入树的概念后,好像还是会有矛盾的地方,例如 K/V 和 Array 两者都可以延伸一下级节点,它们之间有什么不同呢?什么时候该用 K/V 呢?什么时候又该使用 Array 呢?这并无标准答案,JSON 自身并不会说明清楚或者强制要求。再例如 cc 这个数组,第一个元素是字符串,第二个元素是 K/V。因为我们知道,JSON 包含的元素可允许是不同类型的,即混合多种类型的值为一个数组——那样本身是没问题的。但结合树的概念的话问题就来了,是否 K/V 就必须是引出下级树节点吗?——我大可以理解为 JSON 的一个值,她是 K/V 类型,那也是合法的啊,同理数组也不一定引出下级的节点,当前只是表现同类对象的集合,——那也是完全合法的。所以怎么定义这是个树节点,还是说一个 JSON 值?二义性的问题由此产生了。

为解决这个二义性的问题,我们可以对 JSON 作适当的约定,以便更清晰地和准确地反映一棵树。首先节点用 K/V 表示;Children 是下级节点的数组,是容器。它不能是其他的类型如 map 的类型,只能是 Array。只有 最外一层 和 父容器名为 children 的数组,里面的 K/V 才是树节点。一个节点可以有零个或一个 children 的 K/V,且 V 必然是数组。

如下便是一个我们约束定义的树:

[ {
    'name' : "关于我们",
    'id' : 'about',
    'children' : [ 
        {
            name : "公司历程",
            id : 'history'
        },
        {
            name : "企业文化",
            id : 'cluture'
        }
    ]
}, {
    'name' : "美食天地",
    'id' : 'product',
    'children' : [ 
        {
            name : "最新美食",
            id : 'new',
            'children' : [
                {
                    'id' : 'yuecai',
                    'name' : '粤菜'
                },
                {
                    'id' : 'yuecai',
                    'name' : '湘菜'
                }
            ]
        },
        {
            name : "热门菜谱",
            id : 'hot'
        }
    ]
}, 
{
    'name' : "最新资讯",
    'id' : 'news'
}, 
{
    'name' : "招聘信息",
    'id' : 'hr'
}, {
    'name' : "联系我们",
    'id' : 'contact'
}]

值得注意的是该结构最外一层为 Array 而不是 K/V。

遍历 JSON

JSON 本身乃 JavaScript 的产物,虽然也有序列化和反序列化的过程,但使用起来还是比较自然、“原生原味”的。

这里重点说说 Java 世界处理 JSON 的话题。当 JSON 字符串经过解析器反序列化之后,可得到 Java 识别的类型。如果引入三方包,就有其自定义的类型(如 JSONArray、JSONObject)。但是我们这里不使用三方包的类型来说明问题(虽然可能都是“同理”得出一致的结论),——因为那又牵涉到该使用哪个三方包的问题(选择困难症患者-_-)。

于 Java 而言与 JSON 对应的结构一般自然的选择是 Map/List 组合——本文就拿 Map/List 就好了。这里用泛型可以加强说明所包含元素的类型是什么,使之更加直观和清晰,即 Map,其中,String 是 key 的类型,我们知道 JSON 的key 类型就是字符串类型;Object 便是 Value 的类型,可以是合法的 JSON 值(字符串、数字、null),或者是另外一个 Map 或 List。至于 List 的泛型便是嵌套的 List<Map>。于是,我们可以写一个方法(或者第三方包),JSON 字符串被解析之后,得到 Map/List 结构的 Java 类型,变成 Java 可以理解的“树”。应该怎么遍历的这棵树呢?最简单的方法,莫过于递归这个 Map/List。

好比现在输入这段 JSON,这是网站的配置文件:

{
	"site" : {
		"titlePrefix" : "大华•川式料理",
		"keywords" : "大华•川式料理",
		"description" : "大华•川式料理饮食有限公司于2015年成立,本公司目标致力打造中国新派川菜系列。炜爵爷川菜料理系列的精髓在于清、鲜、醇、浓、香、烫、酥、嫩,擅用麻辣。在服务出品环节上,团队以ISO9000为蓝本建立标准化餐饮体系,务求以崭新的姿态面向社会各界人仕,提供更优质的服务以及出品。炜爵爷宗旨:麻辣鲜香椒,美味有诀窍,靓油用一次,精品煮御赐。 ",
		"footCopyright":"dsds" 
	},
	"dfd":{
		"dfd":'fdsf',
		"id": 888,
		"dfdff":{
			"dd":'fd'
		}
	},
	"clientFullName":"大华•川式料理",
	"clientShortName":"大华",
	"isDebug": true,
	"data" : {
		"newsCatalog_Id" : 6,
		"jobCatalog_Id" :7
	}
}

送入 JSON 解析器得到 Map:

这里暂忽略 JSON 解析器的原理。先接着看看遍历 JSON 的过程。假设我们要把所有 key 列出来

@SuppressWarnings("unchecked")
public void travel(Map<String, Object> map) {
    for (String key : map.keySet()) {
        Object obj = map.get(key);
        System.out.println("The key is:" + key);

        if (obj != null && obj instanceof Map) {
            Map<String, Object> _map = (Map<String, Object>) obj;
            travel(_map);     
        }
    }
}

打印结果如下

前面说到,我们讨论的是树结构,已经有这样的约定:如果遇到 Key 为 children 且 value 为数组元素的话,那就下级节点,数组里的都是子节点 K/V。否则就是普通的一个 JSON 数组。

@SuppressWarnings("unchecked")
public void travel(Map<String, Object> map) {
	for (String key : map.keySet()) {
		Object obj = map.get(key);
		System.out.println("The key is:" + key);

		if (obj != null && obj instanceof Map) {
			Map<String, Object> _map = (Map<String, Object>) obj;
			if (_map.get(children) != null && _map.get(children) instanceof List) {
				List<Map<String, Object>> list = (List<Map<String, Object>>) _map.get(children);

				for (Map<String, Object> __map : list)
					travel(__map);
			}
		}
	}
}

与前面的函数相比只是增加了 children 的判断,然后遍历 children 里面各项的 map。——一切都非常简单是吧?可以说毫无惊艳之处。不过读者可试着改造一下,把当前支持 Map<String, Object> map 类型的参数改为List<Map<String, Object>> list 的,看看遍历过程有什么不同。

分析树

现在不妨把需求的难度提高那么一丢丢:希望可以完整记下节点的完整的“路径”和层级。文章到这里写得太长太冗长了,笔者还是赶紧给出代码,赶紧收尾。

输入 JSON 数组:

[ {
	'name' : "关于我们",
	'id' : 'about',
	'children' : [ 
		{
			name : "公司历程",
			id : 'history'
		},
		{
			name : "企业文化",
			id : 'cluture'
		}
	]
}, {
	'name' : "美食天地",
	'id' : 'product',
	'children' : [ 
		{
			name : "最新美食",
			id : 'new',
			'children' : [
				{
					'id' : 'yuecai',
					'name' : '粤菜'
				},
				{
					'id' : 'yuecai',
					'name' : '湘菜'
				}
			]
		},
		{
			name : "热门菜谱",
			id : 'hot'
		}
	]
}, 
{
	'name' : "最新资讯",
	'id' : 'news'
}, 
{
	'name' : "招聘信息",
	'id' : 'hr'
}, {
	'name' : "联系我们",
	'id' : 'contact'
}]

这里给出前一小节的答案,就是遍历 List 的,并增加了功能。

/**
     * 分析这棵树,为每个节点增加 fullPath 和 level 属性,分别表示完整的路径和层数
     * 
     * @param list
     *            输入的树,必须为 List
     * @param superNode
     *            父级节点
     * @param level
     *            层数
     */
@SuppressWarnings("unchecked")
public void travelList(List<Map<String, Object>> list, Map<String, Object> superNode, int level) {
	for (Map<String, Object> map : list) {
		if (map != null) {
			String currerntPath = (superNode != null ? superNode.get("fullPath").toString() : "") + "/" + map.get(id).toString();
			map.put("fullPath", currerntPath);
			map.put("level", level);

			// 记录父级信息
			List<String> supers = new ArrayList<>();
			map.put("supers", supers);

			if (superNode != null) {
				supers.addAll((List<String>) superNode.get("supers"));
				supers.add(superNode.get("fullPath") + ":" + superNode.get("name")); // 仅记录 id 和 name
			}

			if (map.get(children) != null && map.get(children) instanceof List)
				travelList((List<Map<String, Object>>) map.get(children), map, level + 1);
		}
	}
}

结果是

好吧,我承认,这也不是太难的例子,仍然不外乎 for 循环+ 递归。下一篇要写 Stack 的内容了。

网友评论

登录后评论
0/500
评论
sp42
+ 关注