二进制搜索树遍历，比较两个指针的相等性

我正在阅读Cormen算法手册（二叉搜索树章节），它说有两种方法可以在没有递归的情况下遍历树：

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

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

有关如何在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; } } 

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

Answer 2

假设树中的节点是引用并且值是引用，您始终可以调用Object类上的静态ReferenceEquals方法进行比较，以查看任何两个节点/值的引用是否相同。