迭代螺纹二叉树遍历只有恒定的额外空间

Question

如何在不使用堆栈的情况下非递归地遍历O(n)中的线程二叉树(只允许为临时变量使用常量额外空间,因此我们不能将访问标志添加到树中的每个节点).我花了很多时间思考它,但除非我们要遍历具有树数据的内存位置,否则我似乎并不可行.假设我们使用多个数组表示来实现指针,然后我们可以遍历O(n)中的树,是否有人有其他想法？

注意这不是功课,只是为了节省一些键盘敲击的能量来写关于作业的评论!

Answer 1

假设我们在C中有以下线程树表示:

typedef struct threaded_binary_tree {
    int value;

    // Flag that tells whether right points to a right child or to a next
    // node in inorder.
    bool right_is_child;

    struct threaded_binary_tree *left, *right;
} threaded_binary_tree;

然后,在O(1)内存中遍历它可能如下所示:

void inorder(threaded_binary_tree *node)
{
    threaded_binary_tree *prev = NULL;

    // Ignore empty trees
    if (node == NULL)
        return;

    // First, go to the leftmost leaf of the tree
    while (node->left != NULL)
        node = node->left;

    while (node != NULL) {
        // Nodes are visited along going upward in the tree
        printf("%d\n", node->value);

        prev = node;
        node = node->right;

        if (prev->right_is_child) {
            // We're descending into tree

            if (node != NULL) {
                // Again, go to the leftmost leaf in this subtree
                while (node->left != NULL)
                    node = node->left;
            }
        }
        // else, we're climbing up in the tree
    }
}

警告:我没有运行此代码.