使用DFS打印Kotlin中的树

Question

我正在研究Trees，并希望在Stack 中打印出树

这是我目前为止得到的。

class TreeNode<T>(var key: T,){
var left: TreeNode<T>? = null
var right: TreeNode<T>? = null
}
fun depthFirstValues(root: TreeNode<Char>){
val stack = mutableListOf(root)
while (stack.size > 0){
val current = stack.removeFirst()
//        println(current.key)
if(current.right!!.equals(true)) stack.add(current.right!!)
if (current.left!!.equals(true)) stack.add(current.left!!)

}
println(stack)
}
fun buildTree(): TreeNode<Char>{
val a = TreeNode('a')
val b = TreeNode('b')
val c = TreeNode('c')
val d = TreeNode('d')
val e = TreeNode('e')
val f = TreeNode('f')

a.left = b
a.right = c
b.left = d
b.right = e
c.right = f
return a
}

我得到了一个emptyList作为返回值。我一整天都在摆弄它，但不知道如何让它发挥作用。任何帮助都将不胜感激。非常感谢。

Answer 1

我发现您的代码有三个主要问题。

• 如果要将整个遍历存储在一个集合中，并在最后打印出来，则需要一个额外的集合来存储深度优先遍历的结果。

  您不能只使用与用于实现遍历的堆栈相同的堆栈，因为保证该堆栈在算法结束时为空，如while循环-stack.size == 0上的条件所示。

• 实际上，您并没有像使用堆栈一样使用stack。您正在从它的前面(removeFirst(移除元素，但在它的后面(add(添加元素，就像队列一样。要像堆栈一样使用它，您应该在列表的相同末尾添加/删除。

• 您没有正确检查null。如果current.right不为null，则current.right!!.equals(true)为false，如果为null，将抛出异常——这根本没有多大意义，是吗？

解决这些问题，我们有：

fun depthFirstValues(root: TreeNode<Char>){
val stack = mutableListOf(root)
val result = mutableListOf<Char>()
while (stack.isNotEmpty()){
val current = stack.removeLast()
current.left?.apply(stack::add)
current.right?.apply(stack::add)
result.add(current.key) // could also get rid of "result" and just println(current.key) here
}
println(result)
}

应用于树时，它将打印[a, c, f, b, e, d]。