algorithm - 带有扭曲的平衡二叉树访问

Question

寻找一个就地 O(N) 算法，该算法打印节点对（在遍历树时），如下所示，对于给定的平衡二叉树：

输出：bc、de、ef、fg

其中“a”是根节点，“b”是左子节点，“c”是右子节点，等等。请注意输出中的“ef”对。

基于以下评论的附加信息：

“节点对”是每个级别的每个相邻对
除了“左”和“右”之外，每个节点都可以有“父”指针/引用
如果我们要放松 O(N) 并就地，是否有更简单的解决方案（递归和迭代）？

score 3 · Accepted Answer

如果这棵树存储在一个数组中，它可以重新排列为“级别连续”（第一个元素是根，接下来的两个是它的孩子，接下来的四个是他们的孩子，等等），这个问题很简单。

如果以另一种方式存储，就会出现问题。您可以尝试广度优先遍历，但这会消耗 O(n) 内存。

好吧，我想您可以通过存储当前级别和当前元素的路径（表示为二进制数）来创建 O(n log n) 时间算法，并且仅存储最后访问的元素以便能够创建对。只有 O(1 + log n) 内存。-> 这实际上可能是一个带有回溯的 O(n) 算法（见下文）。

我知道有一个简单的算法可以在 O(n) 中按顺序访问所有节点，因此可能有一个技巧可以在 O(n) 时间内按顺序访问“姐妹”节点。O(n log n) 时间是有保证的，你可以停在给定的水平。

还有一个简单的 O(n log n) 算法，您只需过滤给定级别的节点，增加下一个循环的级别。

编辑：

好的，我创建了一个在 O(n) 中运行且具有 O(1) 内存的解决方案（两个机器字大小的变量来跟踪当前和最大级别 / 从技术上讲是 O(log log n) 内存，但让我们掩饰一下that/ 和一些节点），但它要求所有节点都包含指向其父节点的指针。使用这种特殊结构，可以在没有 O(n log n) 堆栈的情况下进行中序遍历，只使用两个节点进行左、上或右步进。你停在一个特定的最高水平，永远不会低于它。您跟踪实际和最高级别，以及您在最高级别遇到的最后一个节点。显然，如果您在最高级别遇到下一个，您可以打印出这样的对。每次您意识到该级别上没有更多内容时，您都会增加最高级别。

从 n-1 节点二叉树中的根节点开始，这相当于 1 + 3 + 7 + 15 + ... + n - 1 次操作。这是 2 + 4 + 8 + 16 + ... + n - log2n = 2n - log2n = O(n) 操作。

在没有特殊Node* parent成员的情况下，由于中序遍历所需的堆栈，该算法仅适用于 O(log n) 内存。

score 2 · Accepted Answer

假设您的树具有以下结构：

struct Node
{
    Node *left;
    Node *right;
    int value;
};

您可以在三遍中打印出所有对，并在适当的位置修改树。right这个想法是将相同深度的节点及其指针链接在一起。您通过以下left指针向下遍历。我们还维护每个深度的预期节点计数，因为我们不会为每个深度终止列表。然后，我们解压缩以将树恢复到其原始配置。

它的美妙之处在于zip_down功能；它将两个子树“压缩”在一起，使得左子树的右分支指向右子树的左分支。right如果对每个子树都执行此操作，则可以通过跟随指针遍历每个深度。

struct Node
{
    Node *left;
    Node *right;
    int value;
};

void zip_down(Node *left, Node *right)
{
    if (left && right)
    {
        zip_down(left->right, right->left);
        left->right= right;
    }
}

void zip(Node *left, Node *right)
{
    if (left && right)
    {
        zip(left->left, left->right);
        zip_down(left, right);
        zip(right->left, right->right);
    }
}

void print_pairs(const Node * const node, int depth)
{
    int count= 1 << depth;

    for (const Node *node_iter= node; count > 1; node_iter= node_iter->right, --count)
    {
        printf("(%c, %c) ", node_iter->value, node_iter->right->value);
    }

    if (node->left)
    {
        print_pairs(node->left, depth + 1);
    }
}

void generate_tree(int depth, Node *node, char *next)
{
    if (depth>0)
    {
        (node->left= new Node)->value= (*next)++;
        (node->right= new Node)->value= (*next)++;

        generate_tree(depth - 1, node->left, next);
        generate_tree(depth - 1, node->right, next);
    }
    else
    {
        node->left= NULL;
        node->right= NULL;
    }
}

void print_tree(const Node * const node)
{
    if (node)
    {
        printf("%c", node->value);
        print_tree(node->left);
        print_tree(node->right);
    }
}

void unzip(Node * const node)
{
    if (node->left && node->right)
    {
        node->right= node->left->right;
        assert(node->right->value - node->left->value == 1);
        unzip(node->left);
        unzip(node->right);
    }
    else
    {
        assert(node->left==NULL);
        node->right= NULL;
    }
}

int _tmain(int argc, _TCHAR* argv[])
{
    char value_generator= 'a';
    Node root;

    root.value= value_generator++;
    generate_tree(2, &root, &value_generator);
    print_tree(&root);
    printf("\n");

    zip(root.left, root.right);
    print_pairs(&root, 0);
    printf("\n");

    unzip(&root);
    print_tree(&root);
    printf("\n");

    return 0;
}

EDIT4：就地，O(n) 时间，O(log n) 堆栈空间。

algorithm - 带有扭曲的平衡二叉树访问

2 回答 2

Related

Reference