用C（和其他命令式语言）打印二叉树
（首次海报，而且在编程方面很新颖，请耐心等待！）
我对用于打印格式化二叉树（在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] != ' ')
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);
}
}
（也上传到pastebin服务，为了保留语法高亮）
它工作得很好，但自动宽度设置可能会更好。 预处理器的魔术有点愚蠢（甚至是丑陋），并且没有真正与算法相关，但它允许在树节点中使用各种数据类型（我认为这是对预处理器进行实验的机会 - 记住，我是一个新手！）。
主程序应该打电话
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（）系列函数的原因是无论如何都能够打印Unicode字符）：
(107.0)
┌─────┴─────┐
(106.1) NULL
┌───┴───┐
NULL NULL
所以，我的问题是：
预先感谢您的回复！
PS。 这个问题不是重复的。
编辑： Jonathan Leffler写了一个很好的答案，几天之后很可能会成为“接受的答案”（除非有人发布了同样棒的东西！）。 由于空间限制，我决定在这里回应而不是评论。
bool IsAVL结构成员是什么，但未使用; 只是没有在这个特定的功能中使用。 我必须复制/粘贴各种文件中的代码，并进行大量更改才能显示上面引用的代码。 这是一个我不知道如何解决的问题。 我很乐意发布整个计划，但它太大，并以我的母语（不是英文！）评论。 -Wall和-Wextra启用。 断言和调试消息根据构建目标自动启用/禁用。 此外，我认为嵌套函数不需要函数原型，所有嵌套函数都没有按照定义实现任何外部接口--GCC肯定没有在这里抱怨。 我不知道为什么OSX上有这么多的警告:( vim ，我使用nano （在GNU屏幕内）或gedit （反射）我！ 无论如何，我更喜欢K＆R大括号风格:) L' '建议！ 这是我的第一个“大型”（非平凡）计划，我非常感谢您的建议。
编辑＃2：下面是这里提到的“快速和肮脏”方法的实现。
（ 编辑＃3：我决定将它分解为一个单独的答案，因为它是对OP的有效答案。）
很多回复都提到了Graphviz。 我已经知道它了（许多Linux应用程序都与它相关联），但我认为这对于10KB CLI可执行文件来说是过分的。 不过，我会在未来记住它。 这似乎很棒。
你需要决定你的代码是否需要可移植。 如果您可能需要使用GCC以外的编译器，则嵌套函数对您的可移植性目标是致命的。 我不会使用它们 - 但我的可移植性目标可能与您的不一样。
您的代码缺失<wchar.h> ; 它在没有它的情况下相当干净地编译swprintf()抱怨说你的非静态函数和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’
（这是Mac OS X 10.6.5上的GCC 4.5.2。）
swprintf()的接口; 它比snprintf()更像sprintf() （这是一件好事！）。 整体想法很有趣。 我建议您在提交代码进行分析时选择一种表示方式，并清理与代码分析无关的任何内容。 例如， 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)
{
...
}
您还可以将一些常量（如spaceafter）变为枚举值：
enum { spacesafter = 2 };
这些可以被任何功能使用。
编码风格 ： prettyprint_tree()函数处理太多的计算和数据以便阅读。 图像缓冲区的初始化和打印可以例如放置在单独的功能中，并且也可以进行width计算。 我相信你可以用log来写一个公式来代替
width = (max < 10) ? 1 :
(max < 100) ? 2 :
(max < 1000) ? 3 :
...
计算。
我不习惯阅读嵌套函数和C，这使我很难扫描你的代码。 除非你不与别人分享你的代码，或者有意识形态的理由将代码绑定到GCC，否则我不会使用这些扩展。
算法 ：对于用C编写的快速而脏的漂亮打印机，我绝不会使用你的布局风格。 与您的算法相比，编写按顺序遍历来打印是不容易的
a
/
b c
如
c
a
b
我不介意不得不倾斜我的头。 对于任何比我更愿意发射的东西更漂亮的东西
digraph g { a -> b; a -> c; }
并让它点到做格式化。
此代码应该从以下网址获得：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=0nn";
// Output to console
printPretty(root, 1, 0, cout);
cout << "nnTree pretty print with level=5 and indentSpace=3,noutput to file "tree_pretty.txt".nn";
// 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;
}
上一篇: printing a binary tree in C (and other imperative languages)
下一篇: Why is C so fast, and why aren't other languages as fast or faster?