Over a million developers have joined DZone.
{{announcement.body}}
{{announcement.title}}

Groovy Goodness: Preorder and Postorder Tree Traversal [Snippet]

DZone's Guide to

Groovy Goodness: Preorder and Postorder Tree Traversal [Snippet]

Check out this new Groovy post and learn how to use preorder and postorder for a tree traversal in Groovy 2.5.0.

· Java Zone ·
Free Resource

Automist automates your software deliver experience. It's how modern teams deliver modern software.

The Node class in Groovy has the methods depthFirst and breadthFirst to return a collection of Node objects using either depth or breadth first traversal. Since Groovy 2.5.0, we can specify if we want to use preorder (the default) or postorder traversal. Also, the methods now accept a Closure that will be invoked for each visited node. The Closure has the current Node as the first argument. The second argument is the tree level of the current node.

In the following example, we read some XML and then use depthFirst in several ways to visit the tree of nodes:

// 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']


In our second example, we use the breadthFirst method. This means that the nodes are visited per level in the tree:

// 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']


Written with Groovy 2.5.0.

Get the open source Atomist Software Delivery Machine and start automating your delivery right there on your own laptop, today!

Topics:
java ,groovy ,groovy 2.5.0 ,preorder ,postorder

Opinions expressed by DZone contributors are their own.

{{ parent.title || parent.header.title}}

{{ parent.tldr }}

{{ parent.urlSource.name }}