打印二叉树

参考:波兰表示法与表达式树

在终端上打印一个数据类型为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);
}
上一篇:Codeforces Round #648 (Div. 2) E - Maximum Subsequence Value 思维


下一篇:postgres 流复制集群--主备切换(二)