二叉树作为一种常见的数据结构，在学习过程中经常被使用。

我们在做课程设计的时候，能够图形化打印二叉树无疑是一个加分项，所以今天我们就来讨论一下如何图形化打印二叉树。

目录

如何在分析阶段打印

要完成二叉树的打印，我们至少要保证所有的节点都能不冲突地打印到屏幕上，而一棵二叉树节点最多的情况就是满二叉树。 所以我们只需要考虑如何打印满二叉树即可。

打印二叉树需要基于二叉树的遍历。 如果我们想打印出每个节点，就需要遍历每个节点。 遍历二叉树时，递归顺序（中序、后序）比较简单。 打印到控制台时，只能逐行打印，所以我们可以先将要打印的图形存储在一个数组中。

如果数组存在，它必须有一个大小。 数组的大小取决于二叉树的高度。

一棵只有一个根节点的二叉树只需要一个1×1的数组来存储它。

当有根节点及其左右子节点时，我们需要一个5×3的数组来存储（出于美观原因添加了斜杠和反斜杠）

让我们添加另一个级别。 当二叉树达到三层时，就需要一个13×7的数组来存储。

通过总结规则，我们发现，为了打印完整二叉树，宽度应该以最后一行叶子节点的数量为基础。 为了使其看起来对称，我们将每个叶节点设置为相距三个宽度。 计算后存储二叉树所需的数组宽度为

宽度=(2^(n-1)-1)*3+2^(n-1) n为层数

化简可得

宽度=2^(n+1)-3 n为层数

接下来，计算高度。 二叉树的每一层节点只需要一个高度，但层与层之间的连接高度确实不同。 从上到下看时，当总层数只有两层时，第一层和第二层的连接占据一格高。 当层数为三时，第一层与第二层的连接处占据三格高。 因此，从上到下看，很难找到联系。 线条所占高度的规则。

这时候不妨从下往上搜索。 可以发现，倒数第二层与倒数第二层之间的连线高度必须为1，倒数第二层与倒数第二层之间的连线高度必须为3。倒数第二层与倒数第二层之间的连线高度必须为3。为3。第三层和倒数第四层之间的连接高度必须为7。从这里我们可以总结出一个规则，层与层之间的连接高度必须为2的n次方减1。

最后我们得出这个数组需要申请的内存大小为

宽度=2^(n+1)-3
高度=2^n-1
n为层数

如何将数据存储到打印数组中

生成打印数组时，我们可以先将根节点放在整个数组的第0行中间，然后检查是否有左右孩子。 如果有，则将左右子节点作为新的根节点进行递归。

代码实现存储结构定义

我们使用二叉链表作为二叉树的存储结构

typedef struct TreeNode{
    char data; //数据域
    struct TreeNode * lchild,* rchild; //左右孩子指针
}TreeNode,*P_Node;

二叉树的创建

我们将通过从控制台读取字符串来创建二叉树

规则如下：

将二叉树写成前序遍历字符串，由根-左子-右子组成

每个节点都是一个字符

如果该节点没有子节点，则写为“.”

上图中的二叉树可以写为：ABC..DE.G..F...

//创建树,将输入的字符串以先序的形式存入二叉树
void CreateTree(P_Node &T)
{
    char ch;
    scanf("%c",&ch);
    if(ch == '\n')
    {
        return;
    }
    if(ch == '.')
    {
        T = NULL;
        return;
    }
    T = (P_Node)malloc(sizeof(TreeNode));
    T->data = ch;
    CreateTree(T->lchild);
    CreateTree(T->rchild);
}

寻找深度

生成打印数组时，我们需要用到二叉树的深度，也就是层数，所以我们还需要实现求深度的功能（递归实现）

//求深度
int DeepTree(P_Node T)
{
    if(!T)
    {
        return 0;
    }
    return DeepTree(T->lchild)>DeepTree(T->rchild)?DeepTree(T->lchild)+1:DeepTree(T->rchild)+1;
//关键代码:如果该节点的左子树深度大于右子树则将左子树的深度加一返回,这个返回值便是以该节点做根节点的树的深度,右子树深度大时则相反
}

打印功能的代码实现

做好了准备工作之后，本文的重点就来了。

首先设置全局变量 width 和 。 这两个值在两个函数中都会用到，所以设置为全局的。

int width,height;

同时我们规定数组类型为char，用一串连续空格来代替二维数组。 数组中存储的值和打印的效果对应如下表。

-1

打印'/'

打印'\'

打印空间

其他

直接打印字符

为了实现打印功能，我们需要将需要递归的部分分离出来作为递归函数。 该函数的作用是按顺序遍历二叉树，同时将内容填充到打印数组中。

//T为二叉树的根节点,a是数组的起始地址,i,j是当前节点在数组中的位置
//如果节点有孩子,其孩子的j坐标为 j±(height-i+1)/2
void fillArray(P_Node &T,char *a,int i, int j)
{
    int ti,tj;
    if(T) //如果该位置有节点
    {
        *(a+(i*width)+j) = T->data; //向数组该点填入字符
        if(T->lchild) //有左右孩子给对应的连接线,左右孩子的值在下一层递归赋
        {
            //将该点与其左孩子之间的连线全部填上'/'
            for(ti=i+1,tj=j-1;tj>j-(height-i+1)/2;tj--)
            {
                *(a+((ti)*width)+tj) = -1;
                ti++;
            }
        }
        if(T->rchild)
        {
            for(ti=i+1,tj=j+1;tjlchild, a, ti, j-(height-i+1)/2);
        fillArray(T->rchild, a, ti, j+(height-i+1)/2);
    }
}

计算宽度和高度并实现打印功能的函数

void printBiTree(P_Node &T)
{
    int i,j;
    int n = DeepTree(T); //计算出深度n
    //在计算机中数据以二进制形式存储,所以一个数据左移1位就相当于乘以2的1次方
    width = (2<