Last active
May 15, 2016 12:59
-
-
Save evilkirin/ed521ad192e78a0f9d4db76058983a9d to your computer and use it in GitHub Desktop.
binary_tree_iterator.groovy
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| interface List { | |
| Object first(); | |
| List rest(); | |
| } | |
| def empty() { | |
| null | |
| } | |
| def singleton(node) { | |
| [ | |
| first: { node }, | |
| rest : { null } | |
| ] as List | |
| } | |
| def first(list) { | |
| list.first() | |
| } | |
| def rest(list) { | |
| list.rest() | |
| } | |
| def append(l1, l2) { | |
| if(l1 == null) | |
| return l2 | |
| if(l2 == null) | |
| return l1 | |
| [ | |
| first: { first(l1) }, | |
| rest : { | |
| append(rest(l1), l2) | |
| } | |
| ] as List | |
| } | |
| def makeBinaryTreeIterator(node) { | |
| [ | |
| first: { | |
| node.left != null ? first(makeBinaryTreeIterator(node.left)) : node | |
| }, | |
| rest: { | |
| def leftIt = node.left != null ? makeBinaryTreeIterator(node.left) : null | |
| def rootIt = singleton(node) | |
| def rightIt = node.right != null ? makeBinaryTreeIterator(node.right) : null | |
| def list = append(append(leftIt, rootIt), rightIt) | |
| rest(list) | |
| } | |
| ] as List | |
| } | |
| class Node { | |
| int value; | |
| Node left; | |
| Node right; | |
| } | |
| def tree = new Node(value: 1, left: new Node(value: 2, left: new Node(value:3)), right: new Node(value:4, right: new Node(value: 5))) | |
| def list = makeBinaryTreeIterator(tree) | |
| for(; null != list; list = rest(list)) { | |
| println first(list).value | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment