不能打印带有缩进的二叉树

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

递归函数需要知道当前深度，这样它就可以打印所需的空格数。这可以通过向递归函数中添加一个depth参数来实现。在递归调用中传递当前深度加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);
}

Answer 2

你的问题是压痕(我想)，解决办法是在你回溯时带着缩进。

1. 向bst_print添加第二个参数。无论是printing).
2. Each子调用( void bst_print(bst_t *bst, int depth) )(更纯净，更普遍有用)还是void bst_print(bst_t *bst, string indent) (直接适用于void bst_print(bst_t *bst, int depth)子调用)都应该增加值：bst_print(bst->left, depth+1);

。