无法打印带缩进的二叉树

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

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

向 bst_print 添加第二个参数。 void bst_print(bst_t *bst, int depth) （更纯粹，更普遍有用）或 void bst_print(bst_t *bst, string indent)（直接适用于打印）。
每个子调用应该添加到值： bst_print(bst->left, depth+1);

Answer 2

递归函数需要知道当前深度，以便打印所需的空格数。这可以通过向递归函数添加 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);
}

无法打印带缩进的二叉树

Cannot print binary tree with indentation

c

binary-tree

binary-search-tree