我有一个 k-ary 树,我想使用迭代遍历它。
它是一个场景图,所以每次遇到变换节点时,我都会将其矩阵放在堆栈上,每次遇到网格节点时,都会使用矩阵堆栈对其进行渲染。这两者都必须预先订购。 但是当一个变换节点的所有子节点都被处理时,它的矩阵必须从矩阵堆栈中弹出。所以我还需要一个后序操作。
我找到了一些用于迭代后序遍历的算法,但总是用于二叉树并且没有额外的预序操作。
最佳答案
这是未经测试的,因此请谨慎对待。
解决这个问题的基本思路是在第一次遇到节点时将其标记为已访问。然后把所有的 child 都放到栈上。
如果遇到没有子节点的叶节点,可以将其打印/处理并从堆栈中弹出。
当栈上的下一个节点已经被访问时,所有的子节点必须之前已经被处理过,否则栈不会被清除到这一步。 我们现在知道对于具有任意数量子节点的中间节点,它可以按后序处理。
关于algorithm - 迭代 k-ary 树前序和后序遍历,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/24589134/