算法标签：

递归

题解：

从叶子开始建立窗口，从下往上合并、拉伸。

最早的思路是每次建立的时候就用字符串把窗口的表示存储下来，但是这样由于拉伸操作是递归的，需要对二叉树每个叶子节点都存放窗口的字符表示，要占用很大的空间，且拉伸操作的时候处理字符串也很麻烦。

然后想到其实只要对二叉树每个结点存储一下对应窗口的长和宽就可以了，再存储一下分割状态：UP(UpDown, define as -1), LR(LeftRight, define as -2)和字母(不再分割的话这个小窗口有对应的字母标签)

数据结构：

typedef struct node { int w, h; //width height int type; //split type int lson, rson; }node;

先递归计算窗口的大小和每个子窗口的大小（合并左右子树对应窗口的时候根据分割情况可能要进行长或宽上的拉伸）。再根据计算的大小生成窗口的字符串形式，输出。

#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <cstdio>
using namespace std;
#define UD -1
#define LR -2
#define maxn 256
#define maxlen 1024
const double EPS = 1e-2;

typedef struct node
{
    int w, h;           //width height
    int type;           //split type
    int lson, rson;
}node;

node win[maxn];
char str[maxlen][maxlen];

// 修正后的判断字母函数
bool isletter(char x) {
    return x >= 'A' && x <= 'Z';
}

void streach_w(int k, int w)
{
    win[k].w = w;
    if (win[k].type>=0) return;
    else if (win[k].type==UD)
    {
        streach_w(win[k].lson, w);
        streach_w(win[k].rson, w);
    }
    else
    {
        int w1 = (int)(ceil(1.0*w*win[win[k].lson].w/(win[win[k].lson].w+win[win[k].rson].w))+EPS);
        streach_w(win[k].lson, w1);
        streach_w(win[k].rson, w-w1);
        win[k].w=w;
    }
}

void streach_h(int k, int h)
{
    win[k].h = h;
    if (win[k].type>=0) return;
    else if (win[k].type==LR)
    {
        streach_h(win[k].lson, h);
        streach_h(win[k].rson, h);
    }
    else
    {
        int h1 = (int)(ceil(1.0*h*win[win[k].lson].h/(win[win[k].lson].h+win[win[k].rson].h))+EPS);
        streach_h(win[k].lson, h1);
        streach_h(win[k].rson, h-h1);
    }
}

void print(int w, int h, char str[][maxlen])
{
    for (int i=0; i<=h; i++)
    {
        for (int j=0; j<=w; j++)
            cout << str[i][j];
        cout << endl;
    }
}

void clear(int h, int w, char str[][maxlen])
{
    for (int j=0; j<=w; j++)
        str[0][j] = str[h][j] = '-';
    for (int i=0; i<=h; i++)
        str[i][0] = str[i][w] = '|';
    str[0][0] = str[0][w] = str[h][0] = str[h][w] = '*';
    for (int i=1; i<h; i++)
        for (int j=1; j<w; j++)
            str[i][j]=' ';
}

void cre_window(int k, int line1, int line2, int col1, int col2, char str[][maxlen])
{
    if (win[k].type>=0)
    {
        str[line1][col1] = win[k].type + 'A';
        return;
    }
    else if (win[k].type==UD)
    {
        int line = line1 + win[win[k].lson].h;
        for (int i=col1+1; i<col2; i++)
            str[line][i] = '-';
        str[line][col1] = str[line][col2] = '*';
        cre_window(win[k].lson, line1, line, col1, col2, str);
        cre_window(win[k].rson, line, line2, col1, col2, str);
    }
    else  //left and right
    {
        int col = col1 + win[win[k].lson].w;
        for (int i=line1+1; i<line2; i++)
            str[i][col] = '|';
        str[line1][col] = str[line2][col] = '*';
        cre_window(win[k].lson, line1, line2, col1, col, str);
        cre_window(win[k].rson, line1, line2, col, col2, str);
    }
}

int cal_size(int k, int l, int &sum, char tree[])
{
    if (isletter(tree[l]))
    {
        win[k].w = win[k].h = 2;
        win[k].lson = win[k].rson = -1;
        win[k].type = tree[l]-'A';
        if (k==0)
        {
            clear(win[0].h, win[0].w, str);
            cre_window(0, 0, win[0].h, 0, win[0].w, str);
            print(win[0].w, win[0].h, str);
        }
        return l;
    }
    else{
        int tmp;
        win[k].lson = ++sum;
            tmp = cal_size(win[k].lson, l+1, sum, tree);
        win[k].rson = ++sum;
            tmp = cal_size(win[k].rson, tmp+1, sum, tree);
        win[k].type = (tree[l]=='-') ? UD : LR;
        if (win[k].type==UD)             //up and down should have the same width
        {
            if (win[win[k].lson].w!=win[win[k].rson].w)
            {
                if (win[win[k].lson].w > win[win[k].rson].w)
                {
                    win[k].w = win[win[k].lson].w;
                    streach_w(win[k].rson, win[k].w);
                }
                else
                {
                    win[k].w = win[win[k].rson].w;
                    streach_w(win[k].lson, win[k].w);
                }
            }
            else win[k].w = win[win[k].lson].w;
            win[k].h = win[win[k].lson].h + win[win[k].rson].h;
            if (k==0)
            {
                clear(win[0].h, win[0].w, str);
                cre_window(0, 0, win[0].h, 0, win[0].w, str);
                print(win[0].w, win[0].h, str);
            }
            return tmp;
        }//(win[k].type==LR)
        else                            //left and right should have the same height
        {
            if (win[win[k].lson].h!=win[win[k].rson].h)
            {
                if (win[win[k].lson].h > win[win[k].rson].h)
                {
                    win[k].h = win[win[k].lson].h;
                    streach_h(win[k].rson, win[k].h);
                }
                else
                {
                    win[k].h = win[win[k].rson].h;
                    streach_h(win[k].lson, win[k].h);
                }
            }
            else win[k].h = win[win[k].lson].h;
            win[k].w = win[win[k].lson].w + win[win[k].rson].w;
            if (k==0)
            {
                clear(win[0].h, win[0].w, str);
                cre_window(0, 0, win[0].h, 0, win[0].w, str);
                print(win[0].w, win[0].h, str);
            }
            return tmp;
        }//(win[k].type=LR)return tmp;
    }
    return -1;
}

int main(){
    int cs, sum;
    char tree[maxlen];
    scanf("%d", &cs);
    for (int cases=1; cases<=cs; cases++)
    {
        sum=0;
        cin >> tree;
        cout << cases << endl;
        cal_size(0, 0, sum, tree);
    }
    return 0;
}