[讨论/问答][Java]如何将树形结构转为扁平集合

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 3286 天前的主题，其中的信息可能已经有所发展或是发生改变。

问题就如题。将树形结构转为扁平的集合。
想不用递归。或者其他高性能的实现方式。
最想的就是能用上 J8 最新的 Stream API 。
但是自己咋想也想不到比较靠谱的实现。
这里提供一个借口供大家举例。

class Node {
    private String name;
    private List<Node> children;
    // get set ignore
}

Node

private

扁平

转为

19 条回复 • 2015-12-17 16:01:49 +08:00

msg7086

2015-12-15 01:13:30 +08:00

不想用递归就把递归转换成队列或者栈。

pynix

2015-12-15 04:15:42 +08:00

遍历一遍，扔到列表去。

yimity

2015-12-15 07:30:24 +08:00 via iPhone

@pynix 遍历不得递归嘛？我还是用的递归

yimity

2015-12-15 07:31:38 +08:00 via iPhone

不过我貌似是存成扁平的然后遍历成树形

linux40

2015-12-15 08:28:18 +08:00 via Android

看见楼上都说遍历，我插一嘴，树的遍历只靠循环妥妥的。

yuankui

2015-12-15 09:31:18 +08:00

跟语言无关..

yuankui

2015-12-15 09:32:10 +08:00

楼主搜一下深度优先 || 广度优先

zhuangzhuang1988

2015-12-15 09:49:13 +08:00

flatMap ??

wizardoz

2015-12-15 09:52:21 +08:00

深度优先用栈（其实用到栈就相当于递归），广度优先用队列。

sleeperqp

2015-12-15 11:23:45 +08:00

第一反应是并查集

HypoChen

2015-12-15 11:27:55 +08:00

bfs or dfs

gaopinsong

2015-12-15 13:57:09 +08:00

感谢大家的回复，今天也问了一个高端大学出来的同学，也是让我去搜
深度优先 || 广度优先
又学到了新的姿势。感谢各位的回复

pke

2015-12-15 14:07:16 +08:00

这个和 Dijkstra 算法有什么关系

KotiyaSanae

2015-12-15 14:12:02 +08:00

https://gist.github.com/SeavantUUz/74e91be581099e5536aa 把二叉树压成一个字符串（确实是扁平的集合），没有递归，因为是迭代实现的

domty

2015-12-15 19:17:25 +08:00

不用递归
用 while 循环加 stack 就可以了嘛
况且以我浅薄的经验来看
java 的尾递归调用在不适用 java8 的某些尾递归优化的特性的情况下效率是弱于非递归调用的

FrankFang128

2015-12-16 00:37:25 +08:00 via Android

没人吐槽 J8...

gaopinsong

2015-12-17 16:00:25 +08:00

自己搞了个递归。对于 Java 针对尾递归的优化，不是很了解。回头去搜索下

private Stream<CategoryModel> flatTree(List<CategoryModel> categoryModels) {

Stream<CategoryModel> modelStream = categoryModels.stream();

for (CategoryModel categoryModel: categoryModels) {

List<CategoryModel> children = categoryModel.getChild();

if (children == null || children.size() < 1) continue;

modelStream = Stream.concat(modelStream, flatTree(children));
}

return modelStream;
}

调用的代码

Stream<CategoryModel> modelStream = flatTree(getCategoryTree());

return modelStream.collect(toList());

gaopinsong

2015-12-17 16:00:58 +08:00

自己搞了个递归。对于 Java 针对尾递归的优化，不是很了解。回头去搜索下

private Stream<CategoryModel> flatTree(List<CategoryModel> categoryModels) {
Stream<CategoryModel> modelStream = categoryModels.stream();
for (CategoryModel categoryModel: categoryModels) {
List<CategoryModel> children = categoryModel.getChild();
if (children == null || children.size() < 1) continue;
modelStream = Stream.concat(modelStream, flatTree(children));
}
return modelStream;
}

调用的代码

Stream<CategoryModel> modelStream = flatTree(getCategoryTree());
return modelStream.collect(toList());

gaopinsong

2015-12-17 16:01:49 +08:00

囧。。上边发的。咋没有代码格式。。。。还不能自己删除。囧啊