在没有递归的情况下迭代O(1)空间中的AVL树

Question

我有一个AVL树.每个节点如下所示:

typedef struct {
    Node *parent;  // the parent node
    Node *left;    // the node left of this node
    Node *right;   // the node right of this node
    int height;    // the height of this node
    void *value;   // payload
} Node;

是否可以在O(1)空间中使用这些节点迭代AVL树,而不进行递归,如果是,如何？

如果不是,那么也可以理解具有sub-O(n)空间或iff真正必要的O(N)空间的解决方案.

迭代树我的意思是我想要访问每个节点一次,如果可能的话,按顺序(从最左边到mostright节点).

Answer 1

如果存储了您访问过的最后一个节点,则可以在迭代器中派生要访问的下一个节点.

• 如果最后一个节点是您的父节点,请在左侧子树下.
• 如果最后一个节点是您的左子树,请按下右侧子树.
• 如果最后一个节点是您正确的子树,请转到您的父节点.

该算法为您提供了树的O(1)遍历.您需要对叶子进行一些充实,并确定您希望决定迭代器应该在哪里以及等待递增的迭代器(pre/in/post-order).