c - 用 C(和其他命令式语言)漂亮地打印二叉树

Question

(第一次发布海报，编程方面相当新，所以请耐心等待!)

我对打印格式化二叉树的高效通用算法(在 CLI 环境中)和 都很感兴趣。 C 执行。这是我为了好玩而自己编写的一些代码(这是原始版本的简化版本，是支持许多 BST 操作的更大程序的一部分，但它应该编译得很好):

#include <stdbool.h>    // C99, boolean type support
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define DATATYPE_IS_DOUBLE
#define NDEBUG                      // disable assertions
#include <assert.h>

#define WCHARBUF_LINES          20  // def: 20
#define WCHARBUF_COLMS          800 // def: 80 (using a huge number, like 500, is a good idea,
                                    //          in order to prevent a buffer overflow :)
#define RECOMMENDED_CONS_WIDTH  150
#define RECOMMENDED_CONS_WIDTHQ "150"   // use the same value, quoted

/* Preprocessor directives depending on DATATYPE_IS_* : */
#if defined DATATYPE_IS_INT || defined DATATYPE_IS_LONG
    #define DTYPE           long int
    #define DTYPE_STRING    "INTEGER"
    #define DTYPE_PRINTF    "%*.*ld"
    #undef DATATYPE_IS_CHAR

#elif defined DATATYPE_IS_FLOAT
    #define DTYPE           float
    #define DTYPE_STRING    "FLOAT"
    #define DTYPE_PRINTF    "%*.*f"
    #undef DATATYPE_IS_CHAR

#elif defined DATATYPE_IS_DOUBLE
    #define DTYPE           double
    #define DTYPE_STRING    "DOUBLE"
    #define DTYPE_PRINTF    "%*.*lf"
    #undef DATATYPE_IS_CHAR

#elif defined DATATYPE_IS_CHAR
    #define DTYPE           char
    #define DTYPE_STRING    "CHARACTER"
    #define DTYPE_PRINTF    "%*.*c" /* using the "precision" sub-specifier ( .* ) with a  */
                                    /* character will produce a harmless compiler warning */
#else
    #error "DATATYPE_IS_* preprocessor directive undefined!"

#endif


typedef struct node_struct {
    DTYPE data;
    struct node_struct *left;
    struct node_struct *right;
    /* int height;  // useful for AVL trees */
} node;

typedef struct {
    node *root;
    bool IsAVL;     // useful for AVL trees
    long size;
} tree;


static inline
DTYPE get_largest(node *n){
    if (n == NULL)
        return (DTYPE)0;

    for(; n->right != NULL; n=n->right);

    return n->data;
}

static
int subtreeheight(node *ST){
    if (ST == NULL)
        return -1;

    int height_left  = subtreeheight(ST->left);
    int height_right = subtreeheight(ST->right);

    return (height_left > height_right) ? (height_left + 1) : (height_right + 1);
}


void prettyprint_tree(tree *T){
    if (T == NULL)  // if T empty, abort
        return;

#ifndef DATATYPE_IS_CHAR /* then DTYPE is a numeric type */
    /* compute spaces, find width: */
    int width, i, j;
    DTYPE max = get_largest(T->root);

    width = (max < 10) ? 1 :
            (max < 100) ? 2 :
            (max < 1000) ? 3 :
            (max < 10000) ? 4 :
            (max < 100000) ? 5 :
            (max < 1000000) ? 6 :
            (max < 10000000) ? 7 :
            (max < 100000000) ? 8 :
            (max < 1000000000) ? 9 : 10;
    assert  (max < 10000000000);

    width += 2; // needed for prettier results

#if defined DATATYPE_IS_FLOAT || defined DATATYPE_IS_DOUBLE
    width += 2; // because of the decimals! (1 decimal is printed by default...)
#endif // float or double

    int spacesafter = width / 2;
    int spacesbefore = spacesafter + 1;
    //int spacesbefore = ceil(width / 2.0);

#else /* character input */
    int i, j, width = 3, spacesbefore = 2, spacesafter = 1;

#endif // #ifndef DATATYPE_IS_CHAR

    /* start wchar_t printing, using a 2D character array with swprintf() : */

    struct columninfo{  // auxiliary structure
        bool visited;
        int  col;
    };

    wchar_t wcharbuf[WCHARBUF_LINES][WCHARBUF_COLMS];
    int line=0;
    struct columninfo eachline[WCHARBUF_LINES];

    for (i=0; i<WCHARBUF_LINES; ++i){       // initialization
        for (j=0; j<WCHARBUF_COLMS; ++j)
            wcharbuf[i][j] = (wchar_t)' ';
        eachline[i].visited = false;
        eachline[i].col = 0;
    }

    int height = subtreeheight(T->root);

    void recur_swprintf(node *ST, int cur_line, const wchar_t *nullstr){ // nested function,
                                                                            // GCC extension!
        float offset = width * pow(2, height - cur_line);

        ++cur_line;

        if (eachline[cur_line].visited == false) {
            eachline[cur_line].col = (int) (offset / 2);
            eachline[cur_line].visited = true;
        }
        else{
            eachline[cur_line].col += (int) offset;
            if (eachline[cur_line].col + width > WCHARBUF_COLMS)
                swprintf(wcharbuf[cur_line], L"  BUFFER OVERFLOW DETECTED! ");
        }

        if (ST == NULL){
            swprintf(wcharbuf[cur_line] + eachline[cur_line].col, L"%*.*s", 0, width, nullstr);
            if (cur_line <= height){
                /* use spaces instead of the nullstr for all the "children" of a NULL node */
                recur_swprintf(NULL, cur_line, L"          ");
                recur_swprintf(NULL, cur_line, L"          ");
            }
            else
                return;
        }
        else{
            recur_swprintf(ST->left,  cur_line, nullstr);
            recur_swprintf(ST->right, cur_line, nullstr);

            swprintf(wcharbuf[cur_line] + eachline[cur_line].col - 1, L"("DTYPE_PRINTF"",
                     spacesbefore, 1, ST->data);

          //swprintf(wcharbuf[cur_line] + eachline[cur_line].col + spacesafter + 1, L")");
            swprintf(wcharbuf[cur_line] + eachline[cur_line].col + spacesafter + 2, L")");
        }
    }

    void call_recur(tree *tr){  // nested function, GCC extension! (wraps recur_swprintf())
        recur_swprintf(tr->root, -1, L"NULL");
    }

    call_recur(T);

    /* Omit empty columns: */
    int omit_cols(void){        // nested function, GCC extension!
        int col;

        for (col=0; col<RECOMMENDED_CONS_WIDTH; ++col)
            for (line=0; line <= height+1; ++line)
                if (wcharbuf[line][col] != ' ' && wcharbuf[line][col] != '\0')
                    return col;

        return 0;
    }

    /* Use fputwc to transfer the character array to the screen: */
    j = omit_cols() - 2;
    j = (j < 0) ? 0 : j;

    for (line=0; line <= height+1; ++line){     // assumes RECOMMENDED_CONS_WIDTH console window!
        fputwc('\n', stdout);                   // optional blanc line
        for (i=j; i<j+RECOMMENDED_CONS_WIDTH && i<WCHARBUF_COLMS; ++i)
            fputwc(wcharbuf[line][i], stdout);
        fputwc('\n', stdout);
    }
}

(也上传到 a pastebin service ，以保留语法高亮)

它工作得很好，虽然自动宽度设置可能会更好。预处理器魔术有点愚蠢(甚至丑陋)并且与算法并没有真正相关，但是它允许在树节点中使用各种数据类型(我认为这是对预处理器进行一些试验的机会 - 记住，我是新手!)。

主程序应该调用

system("mode con:cols="RECOMMENDED_CONS_WIDTHQ"lines=2000");

在调用 prettyprint_tree() 之前，在 cmd.exe 中运行时。

示例输出:

(106.0)

(102.0) (109.0)

(101.5) 空 (107.0) (115.0)

NULL NULL (106.1) NULL (113.0) NULL

空空空空空空

理想情况下，输出应该是这样的(我使用 wprintf() 系列函数的原因是无论如何都能够打印 Unicode 字符):

(107.0)
┌─────┴─────┐
(106.1) 空
┌───┴───┐
空空

所以，我的问题:

你怎么看这段代码？ (也非常欢迎编码风格的建议!)

是否可以以优雅的方式扩展以包含线描字符？ (不幸的是，我不这么认为。)

C 或其他命令式语言(或命令式伪代码)中的任何其他算法？

有点不相关:您对 有何看法？嵌套函数 (不可移植的 GNU 扩展)？我认为这是编写函数的递归部分的一种优雅方式，而不必提供所有局部变量作为参数(并且作为实现隐藏技术也很有用)，但它可能是我的 Pascal 过去 :-) 我感兴趣更有经验的编码员的意见。

预先感谢您的回复!

附注。该问题与 this one 不重复.

编辑:
Jonathan Leffler写了一个 excellent answer几天后这很可能会成为“接受的答案”(除非有人发布了同样棒的东西!)。由于篇幅所限，我决定在这里回应而不是发表评论。

上面的代码实际上是一个更大的“家庭作业”项目的一部分(在共享库中实现 BST 操作 + 使用该库的 CLI 应用程序)。但是，“prettyprint”函数是 不是 部分要求；只是我决定添加自己的东西。

我还添加了一个“无需旋转即可转换为 AVL”的函数，该函数使用“arraystr”作为中间表示；-) 我忘了这里没有使用它。我已经编辑了代码以将其删除。另外，bool IsAVL struct 成员绝不是未使用的；只是未在此特定功能中使用。我不得不从各种文件中复制/粘贴代码并进行大量更改以呈现上面引用的代码。这是一个我不知道如何解决的问题。我很乐意发布整个程序，但它太大了，并且用我的母语评论(不是用英语!)。

整个项目大约有 1600 个 LOC(包括注释)，有多个构建目标(调试/发布/静态链接)，它编译了 干净与 -Wall和 -Wextra启用。根据构建目标自动启用/禁用断言和调试消息。另外我认为嵌套函数不需要函数原型(prototype)，毕竟嵌套函数根据定义没有实现任何外部接口(interface) - GCC当然没有在这里提示。我不知道为什么 OSX 上有这么多警告:(

我在 Windows 7 上使用 GCC 4.4.1。

尽管在 Windows 上编写和测试了这个程序，但我实际上是一个 Linux 用户......但我还是受不了 vim我使用 nano (在 GNU 屏幕内)或 gedit相反(射击我)!无论如何，我更喜欢 K&R 支撑样式 :)

可移植性并不重要，对于 Linux 用户来说，GCC 几乎是事实上的......事实上它在 Windows 下也能很好地工作，这是一个很好的奖励。

我没有使用 VCS，也许我应该使用。我想尝试，但所有这些对于我的需求来说似乎都太复杂了，我不知道如何选择一个 :-)

您在检查深度溢出方面绝对是正确的，幸好它很容易添加。

感谢您的 L' '建议!

我找到了你的建议(封装“整个绘图代码，使屏幕图像和相关信息在一个结构中”)极有趣......但我真的不明白你所说的“封装”是什么意思。请您提供 3 或 4 行(伪)代码，显示可能的函数声明和/或可能的函数调用？

这是我的第一个“大型”(和非平凡)程序，我非常感谢您的建议。

编辑 #2:
这里是提到的“快速和肮脏”方法的实现 here .
( 编辑 #3: 我决定将其拆分为 separate answer ，因为它是对 OP 的有效答案。)

很多回复提到 Graphviz .我已经知道它(许多 Linux 应用程序都与它相关联)，但我认为这对于 10KB CLI 可执行文件来说有点过分了。不过，我会牢记在心，以备不时之需。看起来很棒。

Answer 1

您需要决定您的代码是否需要可移植。如果您可能需要使用 GCC 以外的编译器，嵌套函数对您的可移植性目标是致命的。我不会使用它们 - 但我的便携性目标可能与您的不同。

您的代码丢失 <wchar.h> ;它在没有它的情况下编译得相当干净 - GCC 提示您的非静态函数和 swprintf() 缺少原型(prototype)和 fputwc() )，但添加 <wchar.h>产生大量与 swprintf() 相关的严重警告;他们实际上是在诊断错误。

gcc -O -I/Users/jleffler/inc -std=c99 -Wall -Wextra -Wmissing-prototypes \
    -Wstrict-prototypes -Wold-style-definition -c tree.c
tree.c:88:6: warning: no previous prototype for ‘prettyprint_tree’
tree.c: In function ‘prettyprint_tree’:
tree.c:143:10: warning: no previous prototype for ‘recur_swprintf’
tree.c: In function ‘recur_swprintf’:
tree.c:156:17: warning: passing argument 2 of ‘swprintf’ makes integer from pointer without a cast
/usr/include/wchar.h:135:5: note: expected ‘size_t’ but argument is of type ‘int *’
tree.c:156:17: error: too few arguments to function ‘swprintf’
/usr/include/wchar.h:135:5: note: declared here
tree.c:160:13: warning: passing argument 2 of ‘swprintf’ makes integer from pointer without a cast
/usr/include/wchar.h:135:5: note: expected ‘size_t’ but argument is of type ‘int *’
tree.c:174:22: warning: passing argument 2 of ‘swprintf’ makes integer from pointer without a cast
/usr/include/wchar.h:135:5: note: expected ‘size_t’ but argument is of type ‘int *’
tree.c:174:22: warning: passing argument 3 of ‘swprintf’ makes pointer from integer without a cast
/usr/include/wchar.h:135:5: note: expected ‘const wchar_t * restrict’ but argument is of type ‘int’
tree.c:177:13: warning: passing argument 2 of ‘swprintf’ makes integer from pointer without a cast
/usr/include/wchar.h:135:5: note: expected ‘size_t’ but argument is of type ‘int *’
tree.c:177:13: error: too few arguments to function ‘swprintf’
/usr/include/wchar.h:135:5: note: declared here
tree.c: In function ‘prettyprint_tree’:
tree.c:181:10: warning: no previous prototype for ‘call_recur’
tree.c:188:9: warning: no previous prototype for ‘omit_cols’

(这是 MacOS X 10.6.5 上的 GCC 4.5.2。)

请查看界面到 swprintf() ;更像是snprintf()比sprintf() (这是一件好事™!)。

整个想法很有趣。我建议在提交代码进行分析时选择一种表示形式，并清理与代码分析无关的任何内容。例如， arraystr类型已定义但未使用 - 您不想让像我这样的人廉价地查看您的代码。与未使用的结构成员类似；甚至不要将它们作为注释，即使您可能希望将它们保留在 VCS 的代码中(尽管为什么？)。您正在使用版本控制系统 (VCS)，不是吗？这是一个修辞问题 - 如果您不使用 VCS，请立即开始使用，以免失去您所珍视的东西。

在设计方面，您希望避免执行诸如要求主程序运行晦涩难懂的 system() 之类的事情。命令 - 您的代码应该处理这些问题(可能使用初始化函数，也许使用终结函数来撤消对终端设置所做的更改)。

不喜欢嵌套函数的另一个原因:我不知道如何获得函数的声明。看似合理的替代方案不起作用 - 但我没有去阅读有关它们的 GCC 手册。

您检查列宽溢出；您不检查深度溢出。如果您创建的树太深，您的代码将崩溃并烧毁。

小问题:您可以告诉不使用“vi”或“vim”进行编辑的人——他们不会将函数的左大括号放在第 1 列中。在“vi”中，第 1 列中的左大括号为您提供从函数内部的任何位置开始函数的简单方法('[[' 向后跳转；']]' 跳转到下一个函数的开头)。

不要禁用断言。

一定要包含一个主程序和相关的测试数据——这意味着人们可以测试你的代码，而不仅仅是编译它。

使用宽字符常量而不是强制转换:

wcharbuf[i][j] = (wchar_t)' ';

wcharbuf[i][j] = L' ';

您的代码创建一个大屏幕图像(代码中为 20 行 x 800 列)并填充要打印的数据。这是一个合理的方法。小心，您可以安排处理线描字符。但是，我认为您需要重新考虑核心绘图算法。您可能希望封装整个绘图代码，以便屏幕图像和相关信息位于单个结构中，可以通过引用(指针)传递给函数。您将拥有一组函数来在树搜索代码指定的位置绘制各种位。您将有一个函数可以在适当的位置绘制数据值；您将具有在适当位置绘制线条的功能。您可能没有嵌套函数 - 在我看来，当一个函数嵌套在另一个函数中时，阅读代码要困难得多。使函数静态化很好；使嵌套函数成为静态(非嵌套)函数。给他们他们需要的上下文——因此封装了屏幕图像。

整体一个好的开始；很多好主意。还有很多事情要做。

请求有关封装的信息...

您可以使用以下结构:

typedef struct columninfo Colinfo;

typedef struct Image
{
    wchar_t    image[WCHARBUF_LINES][WCHARBUF_COLUMNS];
    Colinfo    eachline[WCHARBUF_LINES];
} Image;

Image image;

您可能会发现添加一些额外成员很方便和/或明智；这将在实现过程中体现出来。然后你可以创建一个函数:

void format_node(Image *image, int line, int column, DTYPE value)
{
    ...
}

您还可以将一些常量(例如空格之后)转换为枚举值:

enum { spacesafter = 2 };

然后这些可以被任何函数使用。