如何优雅地打印二叉树

in 积露为波 with 1 comment

二叉树的学习理解并不难,但是使用时一旦有了小差错就很难受。为了更好、更直观地debug,简单整理了下打印的思路。之前的堆排序打印大根堆时就用到了这个,只是当时没有明确说明。

更新:https://www.onesrc.cn/p/how-to-print-binary-tree-elegantly-2.html

思路:自下而上探索

既然是二叉树,打印效果最好也是二叉树形式的。为了显示下效果,我决定在excel的天然小方格里面显示。这里就直接用md里的表格说明吧。

前空白数据R[]1234567中间空白
3个 1 7个
1个 2 3 3个
0个4 5 6 71个
PBR[]123456789ABCDEFAB
7 1 15
3 2 3 7
1 4 5 6 7 3
08 9 A B C D E F1

这样折腾完后,打印思路就出来了:

分层: 建立N个数组,编号0-N,其最大装载2^k个

0| 1
1| 2 3
2| 4 5 6 7
3| 8 9 A B C D E F

打印:为方便打印空白单位的数量,我们建立一个数组常量,

BPOW[]={0,1,3,7,15,31,63...}//2^k-1,k=0,1,...

按照打印前空白、数据、中间空白、数据、中间空白、数据。。。的循环顺序进行

实现:简单二叉树打印

#include <stdio.h>
#define MAXCOUNT 100
#define TREEARRAYCOUNT 10
const int BPOW[] = {0, 1, 3, 7, 15, 31, 63, 127};

void printBlank(int n){//打印n个空白单位
    for (int i = 0; i < n; i++)
        printf(" ");//按需调整“    ”
}

void printBinTree(char oldTree[],int s,int t){
    int nodeCount = t - s + 1;
    int MaxL = -1;
    char *tree = oldTree + s;
    char treeArray[TREEARRAYCOUNT][TREEARRAYCOUNT] = {};
    for (int i = 0; i < nodeCount;){//分层
        MaxL++;
        for (int j = 0; j <= BPOW[MaxL] && i < nodeCount;)
            treeArray[MaxL][j++] = tree[i++];
    }
    MaxL++;//Better view
    for (int k = 0; k <= MaxL; k++){//打印
        printBlank(BPOW[MaxL - k]);
         //BPOW[k]+i<nodeCount,一个不多,一个不少↓
        for (int i = 0; i <= BPOW[k]&& (BPOW[k]+i<nodeCount); i++){
              printf("%c", treeArray[k][i]);//按需调整“    ”
            printBlank(BPOW[MaxL - k + 1]);
        }
        printf("\n");
    }
    printf("-----------------------------------\n");
}

int main(void){
    char tree[16] = {'0','1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C', 'D', 'E', 'F'};
    printBinTree(tree, 1, 15);//有效数据从1开始
    return 0;
}

其中printBinTree(oldtree, 1, 15);//有效数据从1开始是考虑到二叉树的链式存储转换为数组存储时有效数据从1开始的情况。具体调用时是0还是1,根据自己的实际情况确定。

链式存储可以转换为数组存储后调用或者层次遍历后打印,这里不再给出具体函数。

打印效果

       1               
   2       3       
 4   5   6   7   
8 9 A B C D E F

//Better View
               1                               
       2               3               
   4       5       6       7       
 8   9   A   B   C   D   E   F 

截图:excel探索过程

EXCEL_8JEcfN897e.png

Responses
  1. study 一起学习 go

    Reply