二叉搜索树遍历比较两个指针是否相等 [英] Binary search tree traversal that compares two pointers for equality

问题描述

我读了Cormen算法书（二叉搜索树章），并说有两种方法可以遍历树不递归：

I'm reading the Cormen algorithms book (binary search tree chapter) and it says that there are two ways to traverse the tree without recursion:

使用栈和   更复杂的，但优雅   解决方案，它不使用堆栈，但   假定两个指针可   测试是否相等

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

我实现了（使用栈）第一个选项，但不知道如何实现后者。 这不是一门功课，只是读来教育自己。

I've implemented the first option (using stack), but don't know how to implement the latter. This is not a homework, just reading to educate myself.

任何线索，如何实现第二个在C＃？

Any clues as to how to implement the second one in C#?

推荐答案

当然可以。你没有说你想要什么样的穿越，但这里的伪code为中序遍历。

Sure thing. You didn't say what kind of traversal you wanted, but here's the pseudocode for an in-order traversal.

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;
  }
}

要获得pre或后序，重新排列块的顺序。

To get pre- or post-order, you rearrange the order of the blocks.

这篇关于二叉搜索树遍历比较两个指针是否相等的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！