基于堆栈的欧拉树遍历问题

Question

我想要一个用欧拉遍历（this is how it works）遍历二叉树的函数。当然，这很容易通过递归实现——我知道它是如何工作的。但是现在我想使用堆栈而不是递归来实现该算法的迭代版本。我的想法是将我们遍历的方向也存储在堆栈中。我的代码不工作，我无法以某种方式解决这个问题。你能给我一些关于如何解决这个问题的提示吗？到目前为止，这是我的代码：

#define LEFT (struct Node*) 0xBADF00D
#define RIGHT (struct Node*) 0xDEADBEEF

struct Node { 
    int data; 
    struct Node* parent; 
    struct Node* left; 
    struct Node* right; 
}; 

void eulerTree(struct Node* root) 
{ 
    stack<struct Node*> s;

    s.push(root);
    s.push(RIGHT);
    s.push(root);
    s.push(LEFT);

    while(!s.empty()) {
        struct Node* direction = s.top(); s.pop();
        struct Node* node = s.top(); s.pop();

        visit(node);

        if(direction == LEFT) {
            if(node->left) {
                s.push(node->left);
                s.push(RIGHT);

                s.push(node->left);
                s.push(LEFT);
            }
        } 

        if(direction == RIGHT) {
            if(node->right) {
                s.push(node->right);
                s.push(RIGHT);

                s.push(node->right);
                s.push(LEFT);
            }
        }
    }
}

Answer 1

想一想一个简单的二叉树：

           1
        2     3

欧拉遍历为：1 2 1 3 1

您在这里看到了模式： root, root->left, root, root->right, root

所以你的堆叠顺序应该是：

root
root->left
root
root->right
root

但是如果你的根是叶子呢？然后不要推送任何东西，只打印值。

此外，一旦您向左、向右推动节点，请确保将它们设置为 0 作为根节点，这样您就不会永远推动它们。

话虽如此，cpp 中的代码将是：

编辑：

我之前发布的代码有一个错误。正确代码如下：

void eulerTree(struct Node* root) 
{ 
    stack<struct Node*> s;

    s.push(root);


    while(!s.empty()) {

        struct Node* node = s.pop();

        visit(node);

        if(node->right) {
          s.push(node);
          s.push(node->right);
        }

        if(node->left) {
          s.push(node);
          s.push(node->left);
        }
        node->left = 0;
        node->right = 0;
    }
}

不破坏树:

但是，是的，即使代码很简单，这也会破坏不需要的树。为了解决这个问题，我将在欧拉树遍历中对树的叶子使用两个属性。

如果叶子在parent的左边child和那个parent的右边child为空

（或）

如果叶子是对的child

-打印此叶子后，然后打印 parent 节点一直到根。
如果叶子左child右child不为空

-打印此叶子后仅打印其直接 parent.

为了说明请看下面的树。

1 2 3 4 5 6 7

如果叶子是 5 那么在它被打印之后，然后打印所有 parents 直到 1.

如果叶子是 4 那么在它被打印之后，然后只打印它的直接 parent 2.

为了简化实现，我将在当前堆栈之外使用 parent 堆栈。

void eulerTree(struct Node* root) {
  stack<struct Node*> s;
  s.push(root);
  struct Node* original = root;
  stack<struct Node*> p;

  while(!s.empty()) {
    struct Node* node = s.top();
    s.pop();

    visit(node);

    if ( !node->right && !node->left && !p.empty() ) {
      struct Node* pNode = p.top();
      if ( pNode->left == node && !pNode->right  || pNode->right == node ) {
        while ( !p.empty() ) {
          visit(p.top());
          p.pop();
        }
        p.push(original);
      } else {
        visit(pNode);
      }
    }

    if(node->left || node->right) {
      p.push(node);
    }

    if(node->right) {
      s.push(node->right);
    }

    if(node->left) {
      s.push(node->left);
    }
  }
}

Answer 2

递归实现可能如下所示：

void euler(Node *n) {
    visit(n);
    if (n->left) {
        euler(n->left);
        visit(n);
    }
    if (n->right) {
        euler(n->right);
        visit(n);
    }
}

现在，无论何时进行递归调用，调用堆栈都会用于记住我们在代码中的位置以及我们在做什么。然后我们再次从顶部开始，完成后，该信息将从堆栈中弹出，我们从中断的地方继续。

如果您要使用自己的堆栈反复执行此操作，则必须自己完成相同的工作。您必须记住足够多的内容才能从中断的地方继续。

当然，我们必须记住我们在哪个节点上工作，但也有两个递归调用，所以我们可能必须 return 到 2 个可能的地方。当我们从递归调用中 return 时，则：

我们刚刚完成了 n->left 调用，应该继续检查 n->right；或者
我们刚刚完成了 n->right 调用，应该继续 n

我们可以在堆栈上存储一些额外的信息来区分这两种情况，但这对于这个特定的算法来说不是必需的。从上面的描述中，您可以看到我们可以根据 return 来自的节点来区分这些情况——它是 n->left 或 n->right。

因此，只需将等待节点存储在堆栈中，我们就可以编写这样一个迭代版本：

int state=0; // 0 => initial visit, 1 => just did left, 2 => just did right
Node *n = root;
while (n) {
    visit(n);

    if (n->left && state<1) {
        stack.push(n);
        n=n->left;
        state=0;
        continue;
    }

    if (n->right && state<2) {
        stack.push(n);
        n=n->right;
        state=0;
        continue;
    }

    if (stack.empty())
        break; // done

    Node *child=n;
    n = stack.pop();
    state = (child == n->left ? 1 : 2);
}

基于堆栈的欧拉树遍历问题

Problem with Stack based Euler-Tree-traversal

algorithm

tree

binary-tree

tree-traversal

data-structures