algorithm - 惯用遍历二叉树(可能是任何树)

Question

双向链表支持链表的惯用遍历，我想为什么不能用二叉树呢？传统上，二叉树或一般树是单向的，这意味着，给定一棵具有足够数量节点的大树，查找叶节点的运行时间可能会非常昂贵。

如果在找到这样一个节点之后，为了找到下一个节点，我可以遍历树返回到根，与另一个遍历树的每个节点的深度优先搜索相比，这不是更有优势吗？在意识到双向链表和二叉树的结合可能会增加好处之前，我从来没有考虑过这一点。

例如，如果我使用了一个内部类

class Tree<T> {

      private class TwoWayNode {

           var data     : T
           var left     : TwoWayNode
           var right    : TwoWayNode
           var previous : TwoWayNode
      }
}

通常使用 left 和 right 遍历每个节点的相应子树，而 previous 将保存指向父节点的指针，从而实现惯用遍历。这样的事情会运作良好吗？有哪些潜在的问题或陷阱？

Answer 1

假设您存储了一个previous 引用，您可以先向最左边走。到达叶子节点后​​，再往上倒退一个，向右遍历。

您始终可以将当前节点(您的“步行者”)与子节点进行比较，这样您就可以检查您是左还是右 em> 最后一次。这使你的遍历无状态，你甚至不需要递归；适用于非常大的数据集。

现在，每次您刚离开右边的叶子时，您都会再次备份。

这个算法是深度优先搜索。^*

让它更快:如果您可以为遍历顺序定义一些确定性条件，这会变得非常灵活，甚至可以用于光线追踪等应用。

---

^*: http://en.wikipedia.org/wiki/Depth-first_search

奖励:这篇关于光线追踪中 Kd 树遍历算法的论文:评论:光线追踪的 Kd 树遍历算法(http://dcgi.felk.cvut.cz/home/havran/ARTICLES)/cgf2011.pdf