17

null是否可以在不使用visited标志或 a 的情况下对其节点具有父指针（根的父指针）的 BST 进行迭代顺序遍历stack？

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

4

8 回答 8

18

您可以这样做，您只需要记住上次访问的节点以及当前节点即可。问题陈述不允许这样做：visited每个节点上的标志和 astack都是（最坏情况）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;
        }
    }
}
于 2012-04-29T12:27:16.030 回答
14

这是另一种方法。我认为它本质上等同于 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 不是来自右侧的第一个祖先边。

于 2012-04-29T15:58:30.923 回答
6

使用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;
}
于 2012-04-30T08:07:07.017 回答
0 
public void inorderNoStack() {
    if (root == null) {
        return;
    }

    // use the previous to always track the last visited node
    // helps in deciding if we are going down/up
    Node prev = null;

    Node curr = root;

    while (curr != null) {
        // going down
        if (prev == null || prev.left == curr || prev.right == curr) {
            if (curr.left != null) {
                prev = curr;
                curr = curr.left;
                continue;
            } else {

                visitn(curr);

                if (curr.right != null) {
                    prev = curr;
                    curr = curr.right;
                    continue;
                } else {
                    // swap states
                    prev = curr;
                    curr = prev.parent;
                }
            }
        }

        // going up after left traversal
        if (curr != null && prev == curr.left) {

            visitn(curr);

            if (curr.right != null) {
                prev = curr;
                curr = curr.right;
                continue;
            } else {
                // swap states
                prev = curr;
                curr = prev.parent;
            }
        }

        // going up after right traversal
        if (curr != null && prev == curr.right) {
            // swap states
            prev = curr;
            curr = prev.parent;
        }
    }
}
于 2013-03-26T06:19:02.387 回答
0

第 1 步：编写一个返回有序后继的函数

步骤2：从最左边的节点开始，找到有序的后继，直到没有

    public class TreeNode {
      int data;
      TreeNode left;
      TreeNode right;
      TreeNode parent;
    }

    public class TreeUtility {
      public void inorderNoRecursion(TreeNode root) {
        TreeNode current = leftmostNode(root);
        while(current != null) {
          System.out.println(current.data);
          current = inorderSuccessor(current);
        }
      }

      public TreeNode inorderSuccessor(TreeNode node) {
        if (node.right!=null) {
          return leftmostNode(node.right);
        }

        TreeNode p = node.parent;
        TreeNode c = node;
        while(p!=null && c != p.left) {
          c = p;
          p = p.parent;
        }
        return p;
      }

      private TreeNode leftmostNode(TreeNode node) {
        while (node.left != null) {
          node = node.left;
        }
        return node;
      }
    }
于 2016-02-06T04:44:42.340 回答
0

我的 Java 解决方案没有在现有树上引入任何标志。也没有父指针。这种方法将使节点保持在树的高度。请看一看。

https://github.com/skanagavelu/Algorithams/blob/master/src/tree/InOrderTraversalIterative.java

于 2015-11-16T05:40:38.627 回答
-1

关键是父指针（或改变树的能力），但您需要恒定数量的额外状态（例如，以下协程的程序计数器）。

  1. 将 v 设置为根。
  2. 当 v 有一个左孩子时，将 v 设置为其左孩子。
  3. 产量诉。
  4. 如果 v 是根，则返回。
  5. 将 p 设置为 v 的父级。
  6. 如果 p 的右孩子是 v，则将 v 设置为 p 并转到步骤 4。
  7. 产量 p。
  8. 如果 p 有一个右孩子，则将 v 设置为 p 的右孩子并转到步骤 2。
  9. 将 v 设置为 p 并转到步骤 4。
于 2012-04-29T12:35:31.803 回答
-2

这是在 C++ 中：

void InOrder(Node *r)
{
   if(r==NULL)
         return;

   Node *t=r;

   while(t!=NULL)
       t=t->left;

  while(t!=r)
  {
     if(t==(t->parent->left))
     {
        cout<<t->parent->data;
        t=t->parent->right;
       if(t!=NULL)
      {
       while(t!=NULL)
          t=t->left;
      } 
      if(t==NULL)
          t=t->parent;
     }
     if(t==t->parent->right)
     {
        t=t->parent;
     }
  }
}
于 2012-08-14T22:18:48.480 回答