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

Question

是否有可能在BST上进行迭代按顺序遍历,其中BST的节点有父指针(根的父节点null),而不使用visited标志或stack？

我用谷歌搜索,没有找到答复.重点是,我怎么能知道 - 在某个节点 - 我刚刚来到它而已经完成了它下面的一切？

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

Answer 2

这是另一种方法.我认为它基本上等同于svick的答案,但避免了额外的变量.此版本在Python中实现:

node=root
if node is not None:
  while node.left is not None:
    node=node.left
  while node is not None:
    output(node)
    if node.right is not None:
      node=node.right
      while node.left is not None:
        node=node.left
    else:
      while node.parent is not None and node.parent.right is node:
        node=node.parent
      node=node.parent

您最后访问的节点决定了您需要访问的下一个节点.如果你刚刚访问过节点X,那么你需要访问X右边最左边的节点.如果X没有正确的子节点,那么下一个节点是节点X不是来自右边的第一个祖先侧.

Answer 3

使用svick的正确想法(参见他的回答),这是C++中经过测试的代码.请注意,我没有测试他的代码甚至看看它,我只是接受了他的想法并实现了我自己的功能.

void in_order_traversal_iterative_with_parent(node* root) {
node* current = root;
node* previous = NULL;

while (current) {
    if (previous == current->parent) { // Traversing down the tree.
        previous = current;
        if (current->left) {
            current = current->left;
        } else {
            cout << ' ' << current->data;
            if (current->right)
                current = current->right;
            else
                current = current->parent;
        }
    } else if (previous == current->left) { // Traversing up the tree from the left.
        previous = current;
        cout << ' ' << current->data;
        if (current->right)
            current = current->right;
        else
            current = current->parent;
    } else if (previous == current->right) { // Traversing up the tree from the right.
        previous = current;
        current = current->parent;
    }
}

cout << endl;
}