algorithm - 迭代 k-ary 树前序和后序遍历

Question

我有一个 k-ary 树，我想使用迭代遍历它。

它是一个场景图，所以每次遇到变换节点时，我都会将其矩阵放在堆栈上，每次遇到网格节点时，都会使用矩阵堆栈对其进行渲染。这两者都必须预先订购。但是当一个变换节点的所有子节点都被处理时，它的矩阵必须从矩阵堆栈中弹出。所以我还需要一个后序操作。

我找到了一些用于迭代后序遍历的算法，但总是用于二叉树并且没有额外的预序操作。

Answer 1

这是未经测试的，因此请谨慎对待。

解决这个问题的基本思路是在第一次遇到节点时将其标记为已访问。然后把所有的 child 都放到栈上。

如果遇到没有子节点的叶节点，可以将其打印/处理并从堆栈中弹出。

当栈上的下一个节点已经被访问时，所有的子节点必须之前已经被处理过，否则栈不会被清除到这一步。我们现在知道对于具有任意数量子节点的中间节点，它可以按后序处理。