没有堆栈的非线程二进制搜索树的顺序遍历

Question

假设我们不知何故得到了外星计算机的内存。不幸的是，外星文明拥有比我们大得多的RAM大小，而且某种程度上对函数式语言如此喜爱，以至于所有的数据都在一个巨大的、非线程的、二进制搜索树中(也没有父指针)。嘿，外星人有很多可递归的堆栈！

现在这个二叉树在一个巨大的100兆字节的磁盘阵列中。我们需要一些方法来进行有序遍历。有一种递归方式，它使用完堆栈，没有一台计算机有100 no的堆栈，还有“迭代”方式，它实际上是手动维护堆栈。

我们可以修改树，但只允许在节点上使用额外的指针字段和整数字段。这是因为100兆字节的磁盘阵列几乎完全满了。我们绝对不能使用另外100‘t作为mmap’‘ed堆栈之类的东西。

如何才能完成这项不可能完成的任务？真正令人恼怒的是，嘿，树就坐在那里，整齐有序，在磁盘阵列中，但我们似乎无法把它整理好。

Answer 1

您可以通过将每棵树中最右边的子树临时链接到无序遍历中的后续树来遍历树。例如，当您第一次访问t时

     t
   / ^ \
  a  |  d
 /\  |
 b c-+

您可以通过最初的空右子指针将t的左子元素的最右边元素链接回t。稍后，当遵循正确的指针时，您将返回到t并尝试重复相同的过程，但这次返回到t。在本例中，您将指针还原为null，遍历t并继续遍历t的正确子节点。

这实质上是“计算机编程艺术”第1卷2.3.1节中的练习21。

struct tree {
    tree (int v) : value (v), left (nullptr), right (nullptr) {}
    int value;
    tree *left, *right;
};

template<typename F>
void
inorder (tree *t, F visit) {
    while (t != nullptr) {
        if (t->left == nullptr) {
            visit (t);
            t = t->right;
        } else {
            tree *q, *r;
            r = t;
            q = t = t->left;
            while (q->right && q->right != r)
                q = q->right;
            if (q->right == nullptr)
                q->right = r;
            else {
                q->right = nullptr;
                visit (r);
                t = r->right;
            }            
        }
    }
}