Groovy中前序和后序树遍历前序和后序树遍历

113 阅读 0 评论 75 点赞

我是靠谱客的博主顺心诺言，这篇文章主要介绍Groovy中前序和后序树遍历前序和后序树遍历，现在分享给大家，希望可以做个参考。

前序和后序树遍历

Groovy中的Node类有depthFirst和breadthFirst方法，可以使用深度优先遍历或广度优先遍历返回Node对象的集合。由于Groovy 2.5.0，我们可以指定是使用preorder(默认值)还是postorder遍历。此外，这些方法现在接受一个“闭包”，该“闭包”将为每个访问的节点调用。Closure将当前“节点”作为第一个参数，第二个参数是当前节点的树级。

在下面的例子中，我们读取了一些XML，然后使用depthFirst以几种方式访问节点树:

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
// We start with a XML node hierarchy.
def xml = '''
<A>
<B>
<D/>
<E/>
</B>
<C>
<F/>
</C>
</A>
'''
def root = new XmlParser().parseText(xml)
// Preorder traversal is default, but
// we can also specify it with the boolean
// argument of depthFirst method.
assert root.depthFirst(true)
.collect { node -> node.name() } == ['A', 'B', 'D', 'E', 'C', 'F']
// Groovy 2.5.0 adds possibility to
// directly call closure for
// each node visited where the first
// Closure argument is the node and
// the second argument the level.
def result = []
root.depthFirst { node, level -> result << "$level${node.name()}" }
assert result == ['1A', '2B', '3D', '3E', '2C', '3F']
// Postorder traversal can be specified
// by setting preorder argment to false.
// When used in combination with Closure
// argument we must using named argument
// preorder.
result = []
root.depthFirst(preorder: false) { node -> result << node.name() }
assert result == ['D', 'E', 'B', 'F', 'C', 'A']

在第二个示例中，我们使用了breadthFirst方法。这意味着树中每层访问的节点:

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// Let's create a Node hierarchy.
def builder = NodeBuilder.newInstance()
def root = builder.A {
B {
D()
E()
}
C {
F()
}
}
// Preorder traversal is default, but
// we can also specify it with the boolean
// argument of breadthFirst method.
assert root.breadthFirst(true)
.collect { node -> node.name() } == ['A', 'B', 'C', 'D', 'E', 'F']
// Groovy 2.5.0 adds possibility to
// directly call closure for
// each node visited with node and level.
def result = []
root.breadthFirst { node, level -> result << "$level${node.name()}" }
assert result == ['1A', '2B', '2C', '3D', '3E', '3F']
// Postorder traversal is implemented
// as starting at the lowest level and
// working our way up.
result = []
root.breadthFirst(preorder: false) { node -> result << node.name() }
assert result == ['D', 'E', 'F', 'B', 'C', 'A']