c - 在 C 中正确打印二叉树

Question

我一直在尝试制作一个函数，它以一种漂亮的方式在控制台中横向打印二叉树（在这种情况下是红黑树）。我在互联网上找到了这个算法，并将其应用于我的项目。

注意：我在 SO 和其他网站上看到了很多用 Java 打印二叉树的方法，但它们大多使用 Java 的 String 或其他一些高级语言，而在 C 中有时很难调整代码。下面的代码与我以漂亮的方式打印二叉树一样接近。

static void
rbt_display_treeview(Node *root, int depth, char *path, bool is_right)
{
    const int spaces = 8;

    if (root == NULL)
        return;

    depth++;

    rbt_display_treeview(root->right, depth, path, true);

    path[depth - 2] = 0;

    if(is_right)
        path[depth - 2] = 1;

    if(root->left)
        path[depth - 1] = 1;

    printf("\n");

    for (int i = 0; i < depth - 1; i++)
    {
        if (i == depth - 2)
            printf("%c", is_right ? 218 : 192);
        else if (path[i])
            printf("%c", 179);
        else
            printf(" ");

        for (int j = 1; j < spaces; j++)
            if (i < depth - 2)
                printf(" ");
            else
                printf("%c", 196);
    }

    printf(" %d\n", root->data);

    for (int i = 0; i < depth; i++)
    {
        if (path[i])
            printf("%c", 179);
        else
            printf(" ");

        for (int j = 1; j < spaces; j++)
            printf(" ");
    }

    rbt_display_treeview(root->left, depth, path, false);
}

上面的代码被称为：

// Red-Black tree is created and elements (int) are added

// Printing the tree
char *path = calloc(10000, sizeof(char));

if (!path)
        return;

rbt_display_treeview(tree->root, 0, path, false);
printf("\n");
free(path);

但是有两个问题：此代码将尝试访问节点何时为根的索引-1，并且如果树真的很大，则可能会溢出。所以这是我的前两个问题：char *pathchar *path

• 当节点为root时如何防止这种行为？
• path如果用户尝试打印一棵非常大的树，他应该在溢出缓冲区之前用完堆栈空间，应该有多大？

当我测试它时，我在我的红黑树中按顺序添加了以下整数：

[ 16, -34, 24, 43, 18, 20, 22, -21, 4, 28, 45, 24, -47, -43, 29, 14, -35, 32, 8, -9, -46, 41, 46, -3, 17, -32, 24, 50, -19, -48, 15, 20, 22, -50, -43, 18, -28, 12, -14, 19, 12, 44, 19, 23, 45, -38, 45, -15, -28, 15, 35, 16, -41, -25, 7, -20, -7, -13, -31, -5, -48, -37, -23, -36 ]

它产生了以下输出：

                            ┌─────── 50
                            │
                    ┌─────── 46
                    │       │
                    │       └─────── 45
                    │               │
                    │               └─────── 44
                    │
            ┌─────── 43
            │       │
            │       │       ┌─────── 41
            │       │       │
            │       └─────── 35
            │               │
            │               └─────── 32
            │
    ┌─────── 29
    │       │
    │       │       ┌─────── 28
    │       │       │
    │       └─────── 24
    │               │
    │               │               ┌─────── 23
    │               │               │
    │               │       ┌─────── 22
    │               │       │       │
    │               └─────── 20
    │                       │
    │                       │       ┌─────── 19
    │                       │       │
    │                       └─────── 18
    │                               │
    │                               └─────── 17
    │
     16
    │
    │                               ┌─────── 15
    │                               │
    │                       ┌─────── 14
    │                       │       │
    │                       │       └─────── 12
    │                       │
    │               ┌─────── 8
    │               │       │
    │               │       │       ┌─────── 7
    │               │       │       │
    │               │       └─────── 4
    │               │               │
    │       ┌─────── -3
    │       │       │
    │       │       │               │       ┌─────── -5
    │       │       │               │       │
    │       │       │               ┌─────── -7
    │       │       │               │       │
    │       │       │       ┌─────── -9
    │       │       │       │       │
    │       │       │       │       └─────── -13
    │       │       │       │               │
    │       │       └─────── -14
    │       │               │
    │       │               │       ┌─────── -15
    │       │               │       │       │
    │       │               └─────── -19
    │       │                       │
    │       │                       └─────── -20
    │       │                               │
    └─────── -21
            │
            │                               ┌─────── -23
            │                               │
            │                       ┌─────── -25
            │                       │       │
            │               ┌─────── -28
            │               │       │
            │               │       │       ┌─────── -31
            │               │       │       │
            │               │       └─────── -32
            │               │               │
            │       ┌─────── -34
            │       │       │
            │       │       │               ┌─────── -35
            │       │       │               │
            │       │       │       ┌─────── -36
            │       │       │       │       │
            │       │       │       │       └─────── -37
            │       │       │       │
            │       │       └─────── -38
            │       │               │
            │       │               └─────── -41
            │       │
            └─────── -43
                    │
                    │       ┌─────── -46
                    │       │
                    └─────── -47
                            │
                            └─────── -48
                                    │
                                    └─────── -50

但是后来我看到了一些不应该打印的行，比如数字 22、4、-7、-13、-15 等下面的行。所以我在最后一个for循环中添加了另一个条件，看看我是否可以过滤那些不必要的行：

for (int i = 0; i < depth; i++)
{
    if (path[i] && (root->left || i != depth -1)) /* Here */
        printf("%c", 179);
    else
        printf(" ");

    for (int j = 1; j < spaces; j++)
        printf(" ");
}

事实上确实如此，但我仍然不知道为什么。此外，节点上方的两行-9不应该存在时仍在打印。这是我到目前为止所拥有的：

                            ┌─────── 50
                            │
                    ┌─────── 46
                    │       │
                    │       └─────── 45
                    │               │
                    │               └─────── 44
                    │
            ┌─────── 43
            │       │
            │       │       ┌─────── 41
            │       │       │
            │       └─────── 35
            │               │
            │               └─────── 32
            │
    ┌─────── 29
    │       │
    │       │       ┌─────── 28
    │       │       │
    │       └─────── 24
    │               │
    │               │               ┌─────── 23
    │               │               │
    │               │       ┌─────── 22
    │               │       │
    │               └─────── 20
    │                       │
    │                       │       ┌─────── 19
    │                       │       │
    │                       └─────── 18
    │                               │
    │                               └─────── 17
    │
     16
    │
    │                               ┌─────── 15
    │                               │
    │                       ┌─────── 14
    │                       │       │
    │                       │       └─────── 12
    │                       │
    │               ┌─────── 8
    │               │       │
    │               │       │       ┌─────── 7
    │               │       │       │
    │               │       └─────── 4
    │               │
    │       ┌─────── -3
    │       │       │
    │       │       │               │       ┌─────── -5
    │       │       │               │       │
    │       │       │               ┌─────── -7
    │       │       │               │
    │       │       │       ┌─────── -9
    │       │       │       │       │
    │       │       │       │       └─────── -13
    │       │       │       │
    │       │       └─────── -14
    │       │               │
    │       │               │       ┌─────── -15
    │       │               │       │
    │       │               └─────── -19
    │       │                       │
    │       │                       └─────── -20
    │       │
    └─────── -21
            │
            │                               ┌─────── -23
            │                               │
            │                       ┌─────── -25
            │                       │
            │               ┌─────── -28
            │               │       │
            │               │       │       ┌─────── -31
            │               │       │       │
            │               │       └─────── -32
            │               │
            │       ┌─────── -34
            │       │       │
            │       │       │               ┌─────── -35
            │       │       │               │
            │       │       │       ┌─────── -36
            │       │       │       │       │
            │       │       │       │       └─────── -37
            │       │       │       │
            │       │       └─────── -38
            │       │               │
            │       │               └─────── -41
            │       │
            └─────── -43
                    │
                    │       ┌─────── -46
                    │       │
                    └─────── -47
                            │
                            └─────── -48
                                    │
                                    └─────── -50

• 如何防止打印这两行？

PS：红黑树的实现就像任何其他红黑树一样工作。您也可以在其他二叉树中测试它，因为我希望此代码在任何二叉树上运行。

标签： cbinary-treepretty-print