Pretty-печать двоичного дерева на C (и других императивных языках) - PullRequest
7 голосов
/ 23 декабря 2010

( Новичок и довольно новый в программировании, так что наберитесь терпения, пожалуйста! )

Меня интересует как эффективный общий алгоритм печати отформатированных двоичных деревьев (в среде 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);
    }
}

( также загружен в службу вставки , чтобы сохранить подсветку синтаксиса )

Работает довольно хорошо, хотя автоматическая настройка ширины может быть лучше. Магия препроцессора немного глупа (или даже некрасива) и не имеет никакого отношения к алгоритму, но она позволяет использовать различные типы данных в узлах дерева (я видел в этом шанс немного поэкспериментировать с препроцессором - помните, я новичок!).

Основная программа должна вызывать

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

перед вызовом prettyprint_tree () при запуске внутри cmd.exe.

Пример вывода:


                                                  (106.0)


                      (102.0)                                                 (109.0)


        (101.5)                      NULL                       (107.0)                     (115.0)


  NULL          NULL                                     (106.1)        NULL         (113.0)        NULL


                                                      NULL   NULL                 NULL   NULL

В идеале вывод должен выглядеть следующим образом (причина, по которой я использую семейство функций wprintf (), в любом случае позволяет печатать символы Юникода):

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

Итак, мои вопросы:

  • Что вы думаете об этом коде? (Предложения по стилю кодирования также приветствуются!)
  • Можно ли его элегантно расширить, чтобы включить символы рисования линий? (К сожалению, я так не думаю.)
  • Любые другие алгоритмы на C или других императивных языках (или императивный псевдокод)?
  • Несколько не связано: каково ваше мнение о вложенных функциях (непереносимое расширение GNU)? Я думаю, что это элегантный способ написания рекурсивных частей функции без необходимости предоставлять все локальные переменные в качестве аргументов (а также полезно в качестве техники, скрывающей реализацию), но это может быть моим прошлым на Паскале :-) Меня интересует мнение более опытных программистов.

Заранее спасибо за ваши ответы!

PS. Вопрос не дубликат этот .


редактирование: Джонатан Леффлер написал отличный ответ , который, скорее всего, станет "принятым ответом" через несколько дней (если кто-то не напишет что-то столь же потрясающее!). Я решил ответить здесь вместо комментариев из-за нехватки места.

  • Приведенный выше код фактически является частью более крупного проекта «домашней работы» (реализация операций BST в общей библиотеке + приложение CLI с использованием этой библиотеки). Однако функция prettyprint была , а не частью требований; просто кое-что я решил добавить сам.
  • Я также добавил функцию «конвертировать в AVL без поворотов», которая использовала «arraystr» в качестве промежуточного представления ;-) Я забыл, что она здесь не использовалась. Я отредактировал код, чтобы удалить его. Кроме того, член bool IsAVL struct совсем не используется; просто не используется в этой конкретной функции. Мне пришлось копировать / вставлять код из различных файлов и вносить множество изменений, чтобы представить код, приведенный выше. Это проблема, которую я не знаю, как решить. Я бы с удовольствием выложил всю программу, но она слишком большая и прокомментирована на моем родном языке (не на английском!).
  • Весь проект был около 1600 LOC (включая комментарии) с несколькими целями сборки (отладка / выпуск / статическое связывание), и он скомпилировал clean с включенными -Wall и -Wextra. Утверждения и сообщения отладки включались / отключались автоматически в зависимости от цели сборки. Также я подумал, что прототипы функций не нужны для вложенных функций, потому что все вложенные функции не реализуют никакого внешнего интерфейса по определению - GCC, конечно, здесь не жаловался. Я не знаю, почему на OSX так много предупреждений: (* ​​1076 *
  • Я использую GCC 4.4.1 в Windows 7.
  • Несмотря на написание и тестирование этой программы для Windows, я на самом деле пользователь Linux ... Тем не менее, я терпеть не могу vim и вместо этого использую nano (внутри экрана GNU) или gedit (пристрелите меня) )! В любом случае, я предпочитаю стиль скобок K & R:)
  • Переносимость не имеет большого значения, для пользователей Linux GCC в значительной степени de facto ... Тот факт, что он также хорошо работает под Windows, является хорошим бонусом.
  • Я не использую VCS, возможно, я должен. Я хочу попробовать, но все они кажутся слишком сложными для моих нужд, и я не знаю, как выбрать один: -)
  • Вы определенно правы в отношении проверки на переполнение глубины, к счастью, это очень легко добавить.
  • Спасибо за L' ' совет!
  • Мне кажется, ваше предложение (инкапсулирующее "весь код чертежа таким образом, чтобы изображение на экране и связанная с ним информация находились в единой структуре" ) чрезвычайно , интересно ... но я не очень понимаю, что вы подразумеваете под "инкапсуляцией". Не могли бы вы предоставить 3 или 4 строки (псевдо) кода, показывающие возможное объявление функции и / или возможный вызов функции?

Это моя первая "большая" (и нетривиальная) программа, и я очень благодарен за ваш совет.


edit # 2: Вот реализация "быстрого и грязного" метода, упомянутого здесь .
( edit # 3: Я решил разделить его на отдельный ответ , так как это правильный ответ для OP.)

Во многих ответах упоминается Графвиз . Я уже знал об этом (многие приложения Linux связаны с ним), но я думал, что это будет излишним для исполняемого файла CLI 10 КБ. Тем не менее, я буду помнить это на будущее. Кажется, отлично.

Ответы [ 5 ]

4 голосов
/ 24 декабря 2010

Вы должны решить, должен ли ваш код быть переносимым. Если вам когда-нибудь понадобится использовать компилятор, отличный от GCC, вложенные функции смертельны для вашей цели переносимости. Я бы не стал их использовать, но мои цели по переносимости могут не совпадать с вашими.

Ваш код отсутствует <wchar.h>; без компиляции он довольно аккуратно - GCC жаловался на отсутствие прототипов для ваших нестатических функций и для swprintf() и 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’

(Это GCC 4.5.2 на MacOS X 10.6.5.)

  • Посмотрите на интерфейс к swprintf(); это больше похоже на snprintf(), чем sprintf() (что A Good Thing ™!).

Общая идея интересна. Я предлагаю выбрать одно представление при отправке кода для анализа и очистить все, что не имеет отношения к анализу кода. Например, тип arraystr определен, но не используется - вы не хотите, чтобы такие люди, как я, получали дешевые снимки вашего кода. Аналогично с неиспользованными членами структуры; даже не оставляйте их в качестве комментариев, даже если вы захотите сохранить их в коде вашей VCS (хотя почему?). Вы используете систему контроля версий (VCS), не так ли? И это риторический вопрос - если вы не используете VCS, начните использовать его сейчас, прежде чем потерять то, что вы цените.

С точки зрения дизайна, вам нужно избегать таких вещей, как требование основной программы выполнить неясную команду system() - ваш код должен решать такие проблемы (возможно, с помощью функции инициализатора и, возможно, функции финализатора, чтобы отменить внесены изменения в настройки терминала).

Еще одна причина не любить вложенные функции: я не могу понять, как получить объявление функции на месте. То, что казалось правдоподобными альтернативами, не сработало, но я не стал читать руководство GCC по ним.

  • Вы проверяете переполнение ширины столбца; Вы не проверяете переполнение глубины. Ваш код вылетит и сгорит, если вы создадите слишком глубокое дерево.

Minor nit: вы можете сказать людям, которые не используют '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)
{
    ...
}

Вы также можете преобразовать некоторые константы, такие как spacesafter, в значения enum:

enum { spacesafter = 2 };

Затем они могут использоваться любой из функций.

2 голосов
/ 13 февраля 2011

Этот код должен работать с: http://www.ihas1337code.com/2010/09/how-to-pretty-print-binary-tree.html

    #include <fstream>
#include <iostream>
#include <deque>
#include <iomanip>
#include <sstream>
#include <string>
#include <cmath>
using namespace std;

struct BinaryTree {
  BinaryTree *left, *right;
  int data;
  BinaryTree(int val) : left(NULL), right(NULL), data(val) { }
};

// Find the maximum height of the binary tree
int maxHeight(BinaryTree *p) {
  if (!p) return 0;
  int leftHeight = maxHeight(p->left);
  int rightHeight = maxHeight(p->right);
  return (leftHeight > rightHeight) ? leftHeight + 1: rightHeight + 1;
}

// Convert an integer value to string
string intToString(int val) {
  ostringstream ss;
  ss << val;
  return ss.str();
}

// Print the arm branches (eg, /    \ ) on a line
void printBranches(int branchLen, int nodeSpaceLen, int startLen, int nodesInThisLevel, const deque<BinaryTree*>& nodesQueue, ostream& out) {
  deque<BinaryTree*>::const_iterator iter = nodesQueue.begin();
  for (int i = 0; i < nodesInThisLevel / 2; i++) {
    out << ((i == 0) ? setw(startLen-1) : setw(nodeSpaceLen-2)) << "" << ((*iter++) ? "/" : " ");
    out << setw(2*branchLen+2) << "" << ((*iter++) ? "\\" : " ");
  }
  out << endl;
}

// Print the branches and node (eg, ___10___ )
void printNodes(int branchLen, int nodeSpaceLen, int startLen, int nodesInThisLevel, const deque<BinaryTree*>& nodesQueue, ostream& out) {
  deque<BinaryTree*>::const_iterator iter = nodesQueue.begin();
  for (int i = 0; i < nodesInThisLevel; i++, iter++) {
    out << ((i == 0) ? setw(startLen) : setw(nodeSpaceLen)) << "" << ((*iter && (*iter)->left) ? setfill('_') : setfill(' '));
    out << setw(branchLen+2) << ((*iter) ? intToString((*iter)->data) : "");
    out << ((*iter && (*iter)->right) ? setfill('_') : setfill(' ')) << setw(branchLen) << "" << setfill(' ');
  }
  out << endl;
}

// Print the leaves only (just for the bottom row)
void printLeaves(int indentSpace, int level, int nodesInThisLevel, const deque<BinaryTree*>& nodesQueue, ostream& out) {
  deque<BinaryTree*>::const_iterator iter = nodesQueue.begin();
  for (int i = 0; i < nodesInThisLevel; i++, iter++) {
    out << ((i == 0) ? setw(indentSpace+2) : setw(2*level+2)) << ((*iter) ? intToString((*iter)->data) : "");
  }
  out << endl;
}

// Pretty formatting of a binary tree to the output stream
// @ param
// level  Control how wide you want the tree to sparse (eg, level 1 has the minimum space between nodes, while level 2 has a larger space between nodes)
// indentSpace  Change this to add some indent space to the left (eg, indentSpace of 0 means the lowest level of the left node will stick to the left margin)
void printPretty(BinaryTree *root, int level, int indentSpace, ostream& out) {
  int h = maxHeight(root);
  int nodesInThisLevel = 1;

  int branchLen = 2*((int)pow(2.0,h)-1) - (3-level)*(int)pow(2.0,h-1);  // eq of the length of branch for each node of each level
  int nodeSpaceLen = 2 + (level+1)*(int)pow(2.0,h);  // distance between left neighbor node's right arm and right neighbor node's left arm
  int startLen = branchLen + (3-level) + indentSpace;  // starting space to the first node to print of each level (for the left most node of each level only)

  deque<BinaryTree*> nodesQueue;
  nodesQueue.push_back(root);
  for (int r = 1; r < h; r++) {
    printBranches(branchLen, nodeSpaceLen, startLen, nodesInThisLevel, nodesQueue, out);
    branchLen = branchLen/2 - 1;
    nodeSpaceLen = nodeSpaceLen/2 + 1;
    startLen = branchLen + (3-level) + indentSpace;
    printNodes(branchLen, nodeSpaceLen, startLen, nodesInThisLevel, nodesQueue, out);

    for (int i = 0; i < nodesInThisLevel; i++) {
      BinaryTree *currNode = nodesQueue.front();
      nodesQueue.pop_front();
      if (currNode) {
          nodesQueue.push_back(currNode->left);
          nodesQueue.push_back(currNode->right);
      } else {
        nodesQueue.push_back(NULL);
        nodesQueue.push_back(NULL);
      }
    }
    nodesInThisLevel *= 2;
  }
  printBranches(branchLen, nodeSpaceLen, startLen, nodesInThisLevel, nodesQueue, out);
  printLeaves(indentSpace, level, nodesInThisLevel, nodesQueue, out);
}

int main() {
  BinaryTree *root = new BinaryTree(30);
  root->left = new BinaryTree(20);
  root->right = new BinaryTree(40);
  root->left->left = new BinaryTree(10);
  root->left->right = new BinaryTree(25);
  root->right->left = new BinaryTree(35);
  root->right->right = new BinaryTree(50);
  root->left->left->left = new BinaryTree(5);
  root->left->left->right = new BinaryTree(15);
  root->left->right->right = new BinaryTree(28);
  root->right->right->left = new BinaryTree(41);

  cout << "Tree pretty print with level=1 and indentSpace=0\n\n";
  // Output to console
  printPretty(root, 1, 0, cout);

  cout << "\n\nTree pretty print with level=5 and indentSpace=3,\noutput to file \"tree_pretty.txt\".\n\n";
  // Create a file and output to that file
  ofstream fout("tree_pretty.txt");
  // Now print a tree that's more spread out to the file
  printPretty(root, 5, 0, fout);

  return 0;
}
2 голосов
/ 24 декабря 2010

Стиль кодирования : функция prettyprint_tree() слишком много жонглирует вычислениями и данными, чтобы их было удобно читать. Инициализация и печать буфера изображения могут быть размещены, например, в отдельных функциях, а также в вычислении width. Я уверен, что вы можете написать формулу с log, чтобы заменить

width = (max < 10) ? 1 :
        (max < 100) ? 2 :
        (max < 1000) ? 3 :
        ...

расчет.

Я не привык читать вложенные функции и Си, что значительно усложняет мне сканирование вашего кода. Если вы не поделитесь своим кодом с другими или у вас нет идеологических причин связывать код с GCC, я бы не использовал эти расширения.

Алгоритм : Для быстрого и грязного симпатичного принтера, написанного на C, я бы никогда не использовал ваш стиль макета. По сравнению с вашим алгоритмом, не составляет никакого труда написать обход порядка для печати

   a
  / \
 b   c

в

     c
 a
     b

и я не против того, чтобы наклонить голову. За что-нибудь более красивое, чем я, я бы предпочел испускать

digraph g { a -> b; a -> c; }

и оставьте значение dot для форматирования.

0 голосов
/ 25 декабря 2010

Вот реализация C "быстрого и грязного" метода, упомянутого здесь . Это не становится намного быстрее и / или грязнее:

void shittyprint_tree(tree *T){ // Supposed to be quick'n'dirty!
                                // When DTYPE is "char", width is a bit larger than needed.
    if (T == NULL)
        return;

    const int width = ceil(log10(get_largest(T->root)+0.01)) + 2;
    const wchar_t* sp64 = L"                                                                ";

    void nested(node *ST, int spaces){  // GCC extension
        if (ST == NULL){
            wprintf(L"\n");             // Can be commented to disable the extra blanc line.
            return;
        }
        nested(ST->right, spaces + width);
        wprintf(L"%*.*s("DTYPE_PRINTF")\n", 0, spaces, sp64, 1, 1, ST->data);
        nested(ST->left, spaces + width);
    }

    nested(T->root, 2);
}

Пример вывода (с использованием того же дерева, что и раньше):


            (115.0)

                 (113.0)

       (109.0)

            (107.0)

                 (106.1)

  (106.0)

       (102.0)

            (101.5)

Я не могу сказать, однако, что это соответствует моим первоначальным требованиям ...

0 голосов
/ 24 декабря 2010

Может быть, вы можете взглянуть на алгоритм линии Брезенхема , который может подойти вам

...