C中的AVL树迭代器

Question

我正在尝试创建一个AVL树迭代器，但遇到了问题。这是我必须获得第一个节点的代码，它成功地返回了最小值。

AVLPtr node = iter->list->root;
AVLPtr current = iter->current;
AVLPtr last = iter->last;
AVLPtr parent;
if(current == NULL || current->parent == NULL)
    parent = NULL;
else
    parent = iter->current->parent;
if(last == NULL && current == NULL){
    while(node->leftChild != NULL){
        node = node->leftChild;
        iter->current = node;
    }
}

当我去获取下一个节点时，我得到了一个SegFault。我想这是因为我在第一个if语句中将节点的父节点更改为NULL。然后，我通过最终使while循环中的根为最小值来打乱我的列表。我的问题是，如何在不更改父节点或根节点的情况下获得第一个节点？或者我还缺少什么？

编辑：我应该使用递归顺序调用将树中每个节点所持有的对象提取到一个单独的链表中吗？

Answer 1

我不知道你所说的第一个元素是什么意思，但我认为你指的是最左边的叶子。如果是这样，那么你可以这样找到：

AVLPtr first = iter->list->root;
AVLPtr last = iter->list->root;
while(first->leftChild != NULL){
    first = first->leftChild;
}
iter->current = first;

您应该始终更改iter->current，并使用其指向左侧、右侧和父级的链接。