我有一个与此类似的 main.c 文件:
it = bet_create_iterator(bstree);
while ((n = bst_iter_next(it))) {
printf("value: %d", bst_getvalue(n));
}
希望您从上面可以看出它是如何使用的。但这是我的问题。就是这个功能,
bst_iter_next(it)
它返回一个指向树中节点的指针。
我发现递归遍历 BST 非常简单,但这样做每次返回一个节点却很困难。
如果有人可以帮助一个人并向我解释如何去做,我将不胜感激。
干杯,
安迪。
最佳答案
有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;
}
}
}
无论如何,这在我看来是可行的,但我的逻辑可能有缺陷。
关于c - 二叉搜索树的非递归迭代器,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/19483272/