algorithm - 如何在没有递归或堆栈但使用父指针的情况下按顺序遍历 BST？

Question

是否可以在不使用已访问的情况下对节点具有父指针(根的父节点为null)的 BST 进行迭代中序遍历> 标志还是堆栈？

我用谷歌搜索并没有找到回复。关键是，我怎么知道 - 在某个节点 - 我刚刚到达它还是我已经完成了它下面的所有内容？

Answer 1

你可以这样做，你只需要记住上次访问的节点和当前节点。问题陈述不允许这样做:每个节点上的 visited 标志和 stack 都是(最坏情况)O( n)，记住最后一个节点只是 O(1)。

在 C# 中，算法可能如下所示:

static void Walk(Node node)
{
    Node lastNode = null;
    while (node != null)
    {
        if (lastNode == node.Parent)
        {
            if (node.Left != null)
            {
                lastNode = node;
                node = node.Left;
                continue;
            }
            else
                lastNode = null;
        }
        if (lastNode == node.Left)
        {
            Output(node);

            if (node.Right != null)
            {
                lastNode = node;
                node = node.Right;
                continue;
            }
            else
                lastNode = null;
        }
        if (lastNode == node.Right)
        {
            lastNode = node;
            node = node.Parent;
        }
    }
}