无法打印带缩进的二叉树

Question

我有二叉查找树

        c
    b      d
a             e
                  f

我想打印

c
  b
    a
  d
    e
      f

没有保存每个节点的深度。我尝试了：

typedef struct _bst_t 
{
    char word[MAX_WORD_LEN];
    struct _bst_t *left;
    struct _bst_t *right;
} bst_t;

    void bst_print(bst_t *bst)
    {
        if (bst != NULL)
        {
            printf("%s\n", bst->word);
            printf(" ");
            if (bst->left != NULL)
                bst_print(bst->left);
            if(bst->right != NULL)
                bst_print(bst->right);
        }
    }

我应该如何更改此代码？

哦。很抱歉没有提供每个节点的深度。我应该创建一个新函数来获取每个节点的深度吗？?

Answer 1

您的问题在于缩进（我认为），解决方案是在递归时随身携带缩进。

1. 将第二个参数添加到bst_print。void bst_print（bst_t*bst，int depth）（更纯，更普遍有用）或void bst_print（bt_t*bst、字符串缩进）（直接适用于打印）
2. 每个子调用都应添加值：bst_print（bst-

Answer 2

递归函数需要知道当前深度，以便它可以打印所需数量的空格。这可以通过向递归函数添加深度参数来完成。在递归调用中传递当前深度加 1。

为了避免向主bst_print函数添加额外参数，可以将递归部分移动到帮助程序函数，并将额外参数最初设置为 0。

void bst_print_(bst_t *bst, unsigned int depth)
{
    if (bst != NULL)
    {
        for (unsigned int i = 0; i < depth; i++)
            printf(" ");
        printf("%s (%d)\n", bst->word, bst->count);
        if (bst->left != NULL)
            bst_print_(bst->left, depth + 1);
        if(bst->right != NULL)
            bst_print_(bst->right, depth + 1);
    }
}

void bst_print(bst_t *bst)
{
    bst_print_(bst, 0);
}