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

Question

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

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

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

class Tree<T> {

      private class TwoWayNode {

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

left和right的使用是正常的，从每个节点遍历各自的子树，而previous将持有指向父节点的指针，从而实现惯用遍历。像这样的东西能很好地工作吗?潜在的问题或陷阱是什么？

Answer 1

实际上，二叉树的节点通常是用指向左右子节点和父节点的指针实现的(参见红黑树的this implementation )。

但您并不总是需要父指针：

对于顺序遍历，您可以使用递归算法，这样调用栈会为您处理这一点。如果您想访问最小或最大节点，只需维护一个指向them.

• Sometimes的额外指针，您可以使用finger tree.

• Or来组织您的指针。(参见

• 第666页)：
• 节点的左指针指向第一个(左)子节点
• 节点的右指针指向兄弟节点(如果它是左子节点)或返回父节点(如果是右child)

​

Extra cool: Threaded二进制搜索树，无需堆栈即可轻松实现有序(和逆序)遍历--所以O(1)空间！