参考:波兰表示法与表达式树
在终端上打印一个数据类型为int
的二叉树,方便调试红黑树
实现效果
第二行为后序数组,第三行为中序数组
源码
struct node {
int data;
node *l, *r;
};
int maxDepth(const node *n) {
if (n == nullptr)
return 0;
else {
int maximum = 0, i, d;
if (maximum < (d = maxDepth(n->l))) maximum = d;
if (maximum < (d = maxDepth(n->r))) maximum = d;
return maximum + 1;
}
}
void fillMap(node **map, node *n, int index) {
if (n == nullptr) return;
map[index] = n;
fillMap(map, n->l, index * 2 + 1);
fillMap(map, n->r, index * 2 + 2);
}
inline void putchars(char c, int n) {
while (n--) putchar(c);
}
inline void printLeftToParentBranchTop(int w) {
printf("%*c", w + 1, ' ');
putchars('_', w - 3);
printf("/ ");
}
inline void printRightToParentBranchTop(int w) {
putchar('\\');
putchars('_', w - 3);
printf("%*c", w + 2, ' ');
}
inline void printLeftToParentBranchBottom(int w) {
printf("%*c%*c", w + 1, '/', w - 1, ' ');
}
inline void printRightToParentBranchBottom(int w) {
printf("%*c%*c", w - 1, '\\', w + 1, ' ');
}
inline int printNode(node *n, int w) { return printf("%*d", w, n->data); }
void printTree(node *root) {
int depth = maxDepth(root), i, j, index;
if (depth == 0) {
printf("Null tree\n");
return;
}
node **map = (node **)calloc((1 << depth) - 1, sizeof(node *));
fillMap(map, root, 0);
for (j = 0, index = 0; j < depth; j++) {
int w = 1 << (depth - j + 1);
if (j > 0) {
// Top part of node to parent branch
for (i = 0; i < 1 << j; i++)
if (map[index + i])
if (i % 2 == 0)
printLeftToParentBranchTop(w);
else
printRightToParentBranchTop(w);
else
putchars(' ', w * 2);
putchar('\n');
// Bottom part of node to parent branch
for (i = 0; i < 1 << j; i++)
if (map[index + i])
if (i % 2 == 0)
printLeftToParentBranchBottom(w);
else
printRightToParentBranchBottom(w);
else
putchars(' ', w * 2);
putchar('\n');
}
// Node content
for (i = 0; i < 1 << j; i++, index++)
if (map[index])
putchars(' ', w * 2 - printNode(map[index], w));
else
putchars(' ', w * 2);
putchar('\n');
}
printf("\n");
free(map);
}