二叉搜索树有序遍历 [英] Binary Search Tree Inorder Traversal

问题描述

我对以下代码感到困惑:

I am confused by this code:

void in_order_traversal_iterative(BinaryTree *root) {
  stack<BinaryTree*> s;
  BinaryTree *current = root;
  while (!s.empty() || current) {
    if (current) {
      s.push(current);
      current = current->left;
    } else {
      current = s.top();
      s.pop();
      cout << current->data << " ";
      current = current->right;
    }
  }
}

我们设置了一个指向根的指针.然后，如果存在，则将当前(当前为root)推入堆栈.我不明白为什么我们最初将整个树推入堆栈，而不是仅仅将节点保存的数据值推入堆栈.我是否完全遗漏了某些东西，或者不了解为什么它会以这种方式工作?我不明白为什么我们要推入整个树，而不是单个节点...

We set a pointer to point to root. Then if it exists, then push the current (which is root currently) into the stack. I do not see why we push the whole tree into the stack initially, instead of just the value of the data the node holds. Am I missing something completely or not understanding why it would work this way? I cannot comprehend why we push the whole tree in, rather than a single node...

推荐答案

您错过了以下事实:弹出节点后，仍然必须遍历其正确的子节点:

You're missing the fact that after a node is popped, its right child must still be traversed:

  current = s.top();
  s.pop();
  cout << current->data << " ";
  current = current->right;

如果堆栈中只有数据，那么这将是不可能的.循环不变性是堆栈完全容纳那些具有未遍历的右子节点的节点.

If you had only the data on the stack, this would be impossible. The loop invariant is that the stack holds exactly those nodes with un-traversed right children.

查看发生了什么的另一种方法是通过代数将递归遍历转换为迭代:

Another way to see what's going on is to transform the recursive traversal to the iterative by algebra:

traverse(node) {
  if (node) {
    traverse(node->left);
    visit(node);
    traverse(node->right);
  }
}

首先将尾调用转换为迭代.我们通过更新参数并将递归调用替换为函数的开始goto来实现此目的:

First convert the tail call to iteration. We do this by updating the argument and replacing the recursive call with a goto the start of the function:

traverse(node) {
 start:
  if (node) {
    traverse(node->left);
    visit(node);
    node = node->right;
    goto start;
  }
}

goto和if与while相同，所以到目前为止.

The goto and if are the same as a while, so we have so far

traverse(node) {
  while (node) {
    traverse(node->left);
    visit(node);
    node = node->right;
  }
}

要替换其他递归调用，需要我们模拟编译器运行时环境的调用堆栈.我们使用显式堆栈来做到这一点.

Replacing the other recursive call requires us to simulate the call stack of the compiler's runtime environment. We do that with an explicit stack.

traverse(node) {
 start:
  while (node) {
    stack.push(node);   // save the value of the argument.
    node = node->left;  // redefine it the same way the recursive call would have
    goto start;         // simulate the recursive call
                        // recursive call was here; it's gone now!
   recursive_return:    // branch here to simulate return from recursive call
    visit(node);
    node = node->right;
  }
  // simulate the recursive return: if stack has args, restore and go to return site
  if (!stack.empty()) {
    node = stack.pop();  // restore the saved parameter value
    goto recursive_return;
  }
}

尽管这很丑陋，但是它始终是实现递归代码的迭代版本的一种方法. (如果有多个非尾递归调用，则更为复杂，但数量不多.)而且我敢肯定，您可以看到与代码相似的地方.

Though it's ugly, this is a way that always works to implement iterative versions of recursive code. (It's more complicated if there are multiple non-tail recursive calls, but not much.) And I'm sure you can see the similarity to your code.

我们甚至可以用更多的代数摆脱丑陋.首先，看到这段代码并不难:

We can even get rid of the ugliness with more algebra. First, it's not hard to see this code:

 start:
  while (node) {
    stack.push(node);   // save the value of the argument.
    node = node->left;  // redefine it the same way the recursive call would have
    goto start;         // simulate the recursive call

以start开头执行时等同于

  while (node) {
    stack.push(node);   // save the value of the argument.
    node = node->left;  // redefine it the same way the recursive call would have
  }

我们也可以替换

  if (!stack.empty()) {
    node = stack.pop();  // restore the saved parameter value
    goto recursive_return;
  }

带有以下

  if (!stack.empty()) {
    node = stack.pop();  // restore the saved parameter value
    visit(node);
    node = node->right;
    goto start;
  }

我们只是将recursive_return:之后的三个指令复制到了if主体中.

We have merely copied the three instructions after recursive_return: into the if body.

有了这个，就没有办法到达recursive_return标签，因此我们可以将其与以下两个语句一起删除:

With this, there is no way left to arrive at the recursive_return label, so we can delete it along with the two following statements:

   // Dead code!  Delete me!
   recursive_return:
    visit(node);
    node = node->right;

我们现在有:

traverse(node) {
 start:
  while (node) {
    stack.push(node);   // save the value of the argument.
    node = node->left;  // redefine it the same way the recursive call would have
  }
  if (!stack.empty()) {
    node = stack.pop();  // restore the saved parameter value
    visit(node);
    node = node->right;
    goto start;
  }
}

我们可以通过将其替换为无限循环来摆脱最后一个goto start:

We can get rid of the last goto start by replacing it with an endless loop:

traverse(node) {
  loop {
    while (node) {
      stack.push(node);        // save the value of the argument
      node = node->left;       // redefine it the same way the recursive call would have
    }
    if (stack.empty()) break;  // original code returns, so does this!
    node = stack.pop();        // restore the saved parameter value
    visit(node);
    node = node->right;
  }
}

请注意，我们在与先前代码相同的条件下返回:堆栈为空！

Note we are returning under the same conditions as the previous code: the stack is empty!

我会让您自己证明该代码与您提供的内容相同，只是效率更高，因为它避免了一些比较！我们根本不必对指针和堆栈元素进行推理.它只是发生了."

I will let you prove to yourself that this code does the same as what you presented, only it's a bit more efficient because it avoids some comparisons! We never had to reason at all about pointers and stack elements. It "just happened."

这篇关于二叉搜索树有序遍历的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！