c - 二叉搜索树的非递归迭代器

Question

我有一个与此类似的 main.c 文件:

it = bet_create_iterator(bstree);

while ((n = bst_iter_next(it))) {
    printf("value: %d", bst_getvalue(n));
}

希望您从上面可以看出它是如何使用的。但这是我的问题。就是这个功能，

bst_iter_next(it)

它返回一个指向树中节点的指针。

我发现递归遍历 BST 非常简单，但这样做每次返回一个节点却很困难。

如果有人可以帮助一个人并向我解释如何去做，我将不胜感激。

干杯，

安迪。

Answer 1

有it是一个节点双指针，每次调用 bst_iter_next(it)将其指向行中的下一个节点。假设您正在遍历 post order 中的树并调用it = bet_create_iterator(bstree); 。现在你的it指向根节点。接下来您调用bst_iter_next(it); 。它会做这样的事情:

bst_iter_next(node **it) {
    if (*it has children) {
       *it = *it->left;
       return *it
    }
    else if (*it->parent == NULL)
        *it = NULL or whatever;
        return NULL;
    else {
       node *n = *it;
       while(1) {
          if(n->parent == NULL) {
             *it = NULL or whatever;
             return NULL;
          }
          if(n->parent->left == n && n->parent->right!= NULL) {
              *it = n->parent->right;
              return *it;
          }
          else
              n = n->parent;
       }
    }
}

无论如何，这在我看来是可行的，但我的逻辑可能有缺陷。