kotlin 遍历

kotlin 遍历

Below are the classic binary tree recursive traversal methods embedded into our BinaryNode class. We use a companion object to minimize our space complexity, which is comparable to static methods in Java. You may wonder why we allow for a nullable BinaryNode to be passed into each of these methods. I settled at this option for the sake of clarity. Because the left and right nodes are mutable objects, we would need to create immutable references to them before passing them to the recursive calls. You could say our base case is an empty leaf node.

下面是嵌入到BinaryNode类中的经典二叉树递归遍历方法。 我们使用一个伴随对象来最大程度地减少空间复杂度 ，这与Java中的静态方法相当。 您可能想知道为什么我们允许将可为null的BinaryNode传递给这些方法中的每一个。 为了清楚起见，我选择了此选项。 由于左节点和右节点是可变对象，因此在将它们传递给递归调用之前，我们需要为其创建不可变的引用。 您可以说我们的基本情况是一个空的叶子节点。

The wonderful part about Kotlin is that we can define our action as a lambda expression. Below you will see an action defined as a parameter, which uses the value of the node being passed in as the first parameter. Our action here returns Unit, which is comparable to returning void in Java. Let’s look at how we can use this lambda expression.

关于Kotlin的妙处在于，我们可以将动作定义为lambda表达式。 在下面，您将看到一个定义为参数的操作，该操作将传入的节点的值用作第一个参数。 我们此处的操作返回Unit，这与在Java中返回void相当。 让我们看看如何使用此lambda表达式。

class BinaryNode<T>( var value: T, var left: BinaryNode<T>? = null, var right: BinaryNode<T>? = null ) { companion object { fun <T> traversePreorder( node: BinaryNode<T>?, action: (value: T) -> Unit ) { if(node != null) { action.invoke(node.value) traversePreorder(node.left, action) traversePreorder(node.right, action) } } fun <T> traverseInorder( node: BinaryNode<T>?, action: (value: T) -> Unit ) { if(node != null) { traverseInorder(node.left, action) action.invoke(node.value) traverseInorder(node.right, action) } } fun <T> traversePostOrder( node: BinaryNode<T>?, action: (value: T) -> Unit ) { if (node != null) { traversePostOrder(node.left, action) traversePostOrder(node.right, action) action.invoke(node.value) } } } }

Forgive me for my crude test tree!

原谅我的测试树！

As you can see we can pass the root node to our traversal functions and define the action we can take when processing the value of the node as we pass through it. In our last call, just by changing our lambda expression, we define a Postorder search.

如您所见，我们可以将根节点传递给遍历函数，并定义在处理节点传递的值时可以采取的操作。 在上一个调用中，只需更改lambda表达式，即可定义Postorder搜索。

fun main() { val rootOfBinaryTestTree = rootOfBinaryTestTree() println("Preorder") BinaryNode.traversePreorder(rootOfBinaryTestTree) { println(it) } println("\nInorder") BinaryNode.traverseInorder(rootOfBinaryTestTree) { println(it) } println("\nPostorder") BinaryNode.traversePostOrder(rootOfBinaryTestTree) { value -> println(value) } println("\nFind 3") var found = false BinaryNode.traversePostOrder(rootOfBinaryTestTree) { value -> if(value == 3) { found = true } } println("Found 3: $found") } /** * (1) * / \ * (2) (3) * / \ / \ * (4) (5)(6) (7) */ fun rootOfBinaryTestTree(): BinaryNode<Int> { var rootNode = BinaryNode(1) rootNode.left = BinaryNode(2) rootNode.right = BinaryNode(3) rootNode.left?.left = BinaryNode(4) rootNode.left?.right = BinaryNode(5) rootNode.right?.left = BinaryNode(6) rootNode.right?.right = BinaryNode(7) return rootNode } // Output Preorder 1 2 4 5 3 6 7 Inorder 4 2 5 1 6 3 7 Postorder 4 5 2 6 7 3 1 Find 3 Found 3: true

What about N-ary trees?

那Nary树呢？

Below, similarly, is our Node with a list of children. We implement DepthFirst and BreadthFirst with stack and queue respectively. Our action is defined just as above.

同样，下面是带有子列表的节点 。 我们分别使用堆栈和队列来实现DepthFirst和BreadthFirst。 我们的动作如上定义。

class Node<T>( var value: T, var children: MutableList<Node<T>> = mutableListOf() ) { companion object { fun <T> traverseDepthFirst( rootNode: Node<T>, action: (value: T) -> Unit ) { val stack = ArrayDeque<Node<T>>() stack.addFirst(rootNode) while(stack.isNotEmpty()) { val currentNode = stack.removeFirst() action.invoke(currentNode.value) for(index in currentNode.children.size - 1 downTo 0) { stack.addFirst(currentNode.children[index]) } } } fun <T> traverseBreadthFirst( rootNode: Node<T>, action: (value: T) -> Unit ) { val queue = ArrayDeque<Node<T>>() queue.addFirst(rootNode) while(queue.isNotEmpty()) { val currentNode = queue.removeLast() action.invoke(currentNode.value) for(childNode in currentNode.children) { queue.addFirst(childNode) } } } } }

Here we have a similarly awful test tree. We call the traversals the same way as we do with BinaryNode. This time getting extra fancy using when in our search variation.

在这里，我们有一棵同样糟糕的测试树。 我们将遍历称为BinaryNode一样 。 这次在我们的搜索变体形式中使用when获得了更多的幻想。

fun main() { val rootOfNAryTestTree = rootOfNAryTestTree() println("\nDepth First") Node.traverseDepthFirst(rootOfNAryTestTree) { println(it) } println("\nBreadth First") Node.traverseBreadthFirst(rootOfNAryTestTree) { println(it) } println("\nTest Breadth First Search") var found3 = false var found9 = false Node.traverseBreadthFirst(rootOfNAryTestTree) { when(it) { 3 -> found3 = true 9 -> found9 = true } } println("found3 = $found3, found9 = $found9") } /** * (1) * / \ * (2) (3) * / | \ | \ * (4)(5)(6)(7) (8) */ fun rootOfNAryTestTree(): Node<Int> { var level1Node1 = Node(2) level1Node1.children = mutableListOf(Node(4), Node(5), Node(6)) var level1Node2 = Node(3) level1Node2.children = mutableListOf(Node(7), Node(8)) var rootNode = Node(1) rootNode.children = mutableListOf(level1Node1, level1Node2) return rootNode } //Output Depth First 1 2 4 5 6 3 7 8 Breadth First 1 2 3 4 5 6 7 8 Test Breadth First Search found3 = true, found9 = false

Thank you for taking the time to reach this point. I’m always open to constructive criticism or suggestions on expanding the article. I created the above using IntelliJ Community Edition and you can download the project at the following link.

感谢您抽出宝贵的时间达到这一点。 对于本文的扩展，我总是持建设性的批评或建议。 我是使用IntelliJ Community Edition创建的，您可以通过以下链接下载该项目。

https://github.com/montwell/KotlinTreeTraversals

https://github.com/montwell/KotlinTreeTraversals

翻译自: https://medium.com/@montwell/tree-traversals-in-kotlin-7ff1940af7fa

kotlin 遍历