c# - 比较两个指针是否相等的二叉搜索树遍历

Question

我正在阅读 Cormen 算法书(二叉搜索树章节)，它说有两种不用递归遍历树的方法:

using stack and a more complicated but elegant solution that uses no stack but assumes that two pointers can be tested for equality

我已经实现了第一个选项(使用堆栈)，但不知道如何实现后者。这不是家庭作业，只是阅读以教育自己。

关于如何在 C# 中实现第二个的任何线索？

Answer 1

没问题。你没有说你想要什么样的遍历，但这是中序遍历的伪代码。

t = tree.Root;
while (true) {
  while (t.Left != t.Right) {
    while (t.Left != null) {   // Block one.
      t = t.Left;
      Visit(t);
    }
    if (t.Right != null) {     // Block two.
      t = t.Right;
      Visit(t);
    }
  }

  while (t != tree.Root && (t.Parent.Right == t || t.Parent.Right == null)) {
    t = t.Parent;
  }
  if (t != tree.Root) {        // Block three.
    t = t.Parent.Right;
    Visit(t);
  } else {
    break;
  }
}

要获得预购或后购，您需要重新排列 block 的顺序。