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

This topic created in 3825 days ago, the information mentioned may be changed or developed.

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

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

Node

private

扁平

转为

19 replies • 2015-12-17 16:01:49 +08:00

msg7086

Dec 15, 2015

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

pynix

Dec 15, 2015

遍历一遍，扔到列表去。

yimity

Dec 15, 2015 via iPhone

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

yimity

Dec 15, 2015 via iPhone

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

linux40

Dec 15, 2015 via Android

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

yuankui

Dec 15, 2015

跟语言无关..

yuankui

Dec 15, 2015

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

zhuangzhuang1988

Dec 15, 2015

flatMap ??

wizardoz

Dec 15, 2015

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

sleeperqp

Dec 15, 2015

第一反应是并查集

Hyponet

Dec 15, 2015

bfs or dfs

gaopinsong

Dec 15, 2015

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

pke

Dec 15, 2015

这个和 Dijkstra 算法有什么关系

KotiyaSanae

Dec 15, 2015

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

domty

Dec 15, 2015

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

FrankFang128

Dec 16, 2015 via Android

没人吐槽 J8...

gaopinsong

Dec 17, 2015

自己搞了个递归。对于 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

Dec 17, 2015

自己搞了个递归。对于 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

Dec 17, 2015

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