binary-search-tree - BST【作业】这种迭代遍历的方法是如何工作的？

Question

我正在使用 Pat Morin 的免费书籍 Open Data Structures (in Java) 中的一个示例。我相信我理解树遍历的概念（继续向左走，直到你不能再向左走，然后向右走，然后再往回走。

然而，我对下面的代码有点困惑。它究竟是如何知道更改结构中的分支的，例如：

  r(oot)
  |
 -  -
|    |
a    b
   |  |
   c  d

void traverse2() {
     Node u = r, prev = nil, next;
     while (u != nil) {
       if (prev == u.parent) {
         if (u.left != nil) next = u.left;
         else if (u.right != nil) next = u.right;
         else next = u.parent;
       } else if (prev == u.left) {
         if (u.right != nil) next = u.right;
         else next = u.parent;
       } else {
         next = u.parent;
       }
       prev = u;
       u = next;
} }

从我所见，即使根没有，它也会自动转到父级？

Answer 1

根的父节点为 nil，因此算法在其父节点离开根时终止（它在访问右子树之后执行此操作。）