c - 如何按顺序显示平衡二叉树的下一个元素？ (为了)

Question

所以我正在创建有序集 ADT，使用树实现进行分配。其中一个要求是为集合实现一个迭代器。当我使用递归遍历树时，关于如何按顺序返回下一个元素，我遇到了一些麻烦。我正在考虑使用 while 循环到达最左边的叶(节点)，但我不确定如何返回父节点。这是 tree implementation我正在使用它的 header .这是 set adt及其 header .任何帮助将不胜感激。

/*
 * Returns the next element in the sequence represented by the given
 * set iterator.
 */
void *set_next(set_iter_t *iter)
{
  if(iter->node == NULL)
    printf("tree iterator exhausted");
  else
  {
    void *elem;
    while(iter->node->left != NULL)
      iter->node = iter->node->left;
    return elem;
  }
}

编辑:我尝试将遍历存储在一个数组中，但似乎函数没有正确地遍历数组:

static int i = 0;
void *set_next(set_iter_t *iter)
{

  if(iter->node == NULL)
    printf("tree iterator exhausted");
  else
  {
    int size = iter->node->numitems;
    int arr[size];
    int *p;
    p = arr;
    void *elem;
    store_inorder(iter->node, p, i);
    elem = (p+i);
    return elem;
    ++i;
  }
}

这是我用来将遍历存储在数组中的函数:

void store_inorder(tree_t *tree, int inorder[], int index_ptr)
{
    if (tree == NULL)
        return;
    void *p = malloc(sizeof(intptr_t));;
    p = tree->data;
    /*first recur on left child */
    store_inorder(tree->left, inorder, index_ptr);
    inorder[index_ptr] = (intptr_t)tree->data;
    (index_ptr)++;  // increase index for next entry

    /*now recur on right child */
    store_inorder(tree->right, inorder, index_ptr);
}

Answer 1

您可以通过存储从当前位置返回到根的路径来记住迭代器的位置。

想想 Hänsel 和 Gretel。