Split Windows
题目链接：http://poj.org/problem?id=1108
题目大意：
给你一棵二叉树的先序遍历，有三种字符：|、－、A~Z，然后用窗口表示出来，|: 表示将当前窗口分为左右两半；－: 表示将当前窗口分为上下两半；A~Z: 为当前窗口命名。初始状态为一个大窗口，比如先序序列：|A－BC 表示，当然，形状是不长这样的，具体看样例，但大概意思就是这样。对于每一个小窗口，首先要做到最简，然后和旁边的窗口合并的时候要注意比例，如果出现小数，就左边的、上面的进一，右边的、下面的舍去小数。
题目解法：
并没有用到什么特殊的算法或者数据结构，只要懂得二叉树，接下来模拟即可，这道题做起来感觉挺有意思的。
一． 首先声明一个二叉树的数据结构
typedef struct node //树结点
{
char c; //保存该树结点的字符
int row,col; //保存该树结点的行和列，最后就是通过这个来绘制图形
struct node *fa; //父结点
struct node *lchild; //左孩子
struct node *rchild; //右孩子
}TreeNode;
二． 根据先序序列来构造这样的一根二叉树
TreeNode *Creat(char *s,int &ls) //根据 先序遍历 来构建这棵二叉树
{
TreeNode *T=Init(); //申请空间
T->c=s[ls++]; //赋值
if(s[ls-]=='-'||s[ls-]=='|') //如果这个结点不是叶子结点，就继续创建左右孩子
{
T->lchild=Creat(s,ls);
if(T->lchild) T->lchild->fa=T;
T->rchild=Creat(s,ls);
if(T->rchild) T->rchild->fa=T;
}
return T; //返回树结点的地址
}
三． 封装几个常用的函数
TreeNode *Look_min(TreeNode *T) //返回T子树的最左叶结点
{
while(T->lchild)
{
T=T->lchild;
}
return T;
} TreeNode *Look_max(TreeNode *T) //返回T子树的最右叶结点
{
while(T->rchild)
{
T=T->rchild;
}
return T;
} TreeNode *Look_fa(TreeNode *T) //查找结点T和T的前驱共同的祖先（第一个），如果T是第一个结点就返回NULL
{
while(T->fa)
{
if(T==T->fa->rchild)
{
return T->fa;
}
else T=T->fa;
}
return NULL;
} TreeNode *Look_pre(TreeNode *T) //查找结点T的前驱，如果没有前驱就返回NULL，这里说的前驱必须是叶结点
{
while(T->fa)
{
if(T==T->fa->rchild)
{
return Look_max(T->fa->lchild);
}
else T=T->fa;
}
return NULL;
}
四． * 通过递归来计算每个大写字符应在的行和列
void Calculate_H(TreeNode *T,int mh,int h,int maxh,int minh)
{
if(T)
{
Calculate_H(T->lchild,mh,h,maxh,minh);
if(T->c!='|'&&T->c!='-')
{
int height=h-T->row;
height=maxh*height/minh;
T->row=mh-height+;
}
Calculate_H(T->rchild,mh,h,maxh,minh);
}
} void Calculate_L(TreeNode *T,int ml,int l,int maxl,int minl)
{
if(T)
{
Calculate_L(T->lchild,ml,l,maxl,minl);
if(T->c!='|'&&T->c!='-')
{
int length=l-T->col;
length=maxl*length/minl;
T->col=ml-length+;
}
Calculate_L(T->rchild,ml,l,maxl,minl);
}
} void Calculate_HL(TreeNode *T)
{
if(T)
{
Calculate_HL(T->lchild);
if(T->c!='|'&&T->c!='-') //即叶子结点，就是大写字符
{
TreeNode *pre=Look_pre(T); //首先计算T结点的前驱
if(pre==NULL) //如果前驱为NULL，即第一个大写字母，这个点所在的行就是第一行，列是第一列
{
T->col=;
T->row=;
}
else //如果不是第一个字母
{
TreeNode *fa=Look_fa(T); //因为前面排除了第一个字母，所以这里肯定有前驱，也就肯定有和前驱共享的第一个父结点
if(fa->c=='|') //如果父结点的字符是'|'
{
T->row=Look_min(fa)->row; //那么他的行数和最左孩子是一个档次的，即都为这个被左右分成两半的窗口的第一行
T->col=fa->col+; //他的列在这个窗口中则是左边最大列数加2（中间有个－）
}
else
{
T->row=fa->row+; //同上，这里的每个结点保存的都是以他为根的子树的最大行数或者最大列数
/*
注意递归程序的执行，首先左子树，算完左子树就轮到根结点（中序遍历），然后更新根结点的行数为左子树的行数
就是下面那个else的执行内容，然后算右子树的时候，就可以直接使用根结点的行来表示左子树的最大行数，等右子树计
算完，再有后序遍历来重新更新根结点的值为两边的最大值
*/
T->col=Look_min(fa)->col;
}
}
}
else
{
T->col=T->lchild->col; //更新根结点的行和列，注意这里遇到的只会是'|'或'－'
T->row=T->lchild->row;
}
Calculate_HL(T->rchild);
if(T->c=='|'||T->c=='-')
{
T->row=T->row>T->rchild->row?T->row:T->rchild->row; //这个就是后序遍历更新根结点的位置
T->col=T->col>T->rchild->col?T->col:T->rchild->col;
/*
最后，如果这个根结点的字符是'|'，就是左右分开这个窗口，那么要计算两边的行，按比例更新行的大小，如果是'－'，同样
也要更新上下两个子窗口的列
*/
if(T->c=='|')
{
int mr_lchild=T->lchild->row; //左子树的最大行数
int mr_rchild=T->rchild->row; //右子树的最大行数
if(mr_lchild>mr_rchild) //右子树比较低，那么要按照比例拉伸右子树
{
int mh=mr_lchild+; //先将行转化为高度,下面是细节。
int h=mr_rchild+;
int maxh=mh-Look_min(T->lchild)->row+;
int minh=h-Look_min(T->rchild)->row;
Calculate_H(T->rchild,mh,h,maxh,minh);
}
else
{
int mh=mr_rchild+;
int h=mr_lchild+;
int maxh=mh-Look_min(T->lchild)->row+;
int minh=h-Look_min(T->rchild)->row;
Calculate_H(T->lchild,mh,h,maxh,minh);
}
}
else //同上
{
int mc_lchild=T->lchild->col;
int mc_rchild=T->rchild->col;
if(mc_lchild>mc_rchild)
{
int ml=mc_lchild+;
int l=mc_rchild+;
int maxl=ml-Look_min(T->lchild)->col+;
int minl=l-Look_min(T->rchild)->col;
Calculate_L(T->rchild,ml,l,maxl,minl);
}
else
{
int ml=mc_rchild+;
int l=mc_lchild+;
int maxl=ml-Look_min(T->lchild)->col+;
int minl=l-Look_min(T->rchild)->col;
Calculate_L(T->lchild,ml,l,maxl,minl);
}
}
}
}
}
五． 通过递归来画出窗口基本的骨架
char tu[][]; //保存最终的图 void Draw(TreeNode *T)
{
if(T)
{
Draw(T->lchild);
if(T->c!='|'&&T->c!='-') //如果是字母的话，那么在那一行，那一列，填上字母
{
tu[T->row][T->col]=T->c;
}
else if(T->c=='|') //如果左右分的话，那么在右窗口所属的那个字母的列上画'|'，起点h1，终点h2
{
TreeNode *tmp=Look_min(T->rchild); //右窗口所属的那一个字母就是右子树的最左孩子
int h1=tmp->row+,h2=h1; //起点就是这个字母的下一格，先假设终点等于起点
TreeNode *fa=T->fa; //现在要找的是这个结点的祖先并且是'－'（并且这个结点是在他的左子树），这样，他右孩子的最左孩子就是目标
if(!fa) h2=T->row; //特殊情况处理，如果为NULL，那么这一竖就是直接竖到底的，就是T的行数
bool flag; //标记结点是他的父结点的左孩子还是右孩子，0 是左孩子，1是右孩子
if(fa&&fa->lchild==T) flag=; //下面就是找目标的过程
else flag=;
while(fa)
{
if(fa->c=='-'&&flag==)
{
h2=Look_min(fa->rchild)->row;
break;
}
else
{
h2=fa->row;
}
if(fa->fa&&fa->fa->lchild==fa) flag=;
else flag=;
fa=fa->fa;
}
while(h1<h2) //确定了起点和终点，就可以开始画线了
{
tu[h1++][tmp->col]='|';
}
/*
下面过程不能直接忽略，因为如果*都留到最后处理，会很麻烦。
*/
if(tu[h1][tmp->col]<='Z'&&tu[h1][tmp->col]>='A'); //竖到头后，那个点一般是*，或者有可能遇到字母，就忽略
else
{
tu[h1][tmp->col]='*';
}
}
else //同上
{
TreeNode *tmp=Look_min(T->rchild);
int l1=tmp->col+,l2=l1;
TreeNode *fa=T->fa;
if(!fa) l2=T->col;
bool flag;
if(fa&&fa->lchild==T) flag=;
else flag=;
while(fa)
{
if(fa->c=='|'&&flag==)
{
l2=Look_min(fa->rchild)->col;
break;
}
else
{
l2=fa->col;
}
if(fa->fa&&fa->fa->lchild==fa) flag=;
else flag=;
fa=fa->fa;
}
while(l1<l2)
{
tu[tmp->row][l1++]='-';
}
if( tu[tmp->row][l1]<='Z'&& tu[tmp->row][l1]>='A');
else
{
tu[tmp->row][l1]='*';
}
}
Draw(T->rchild);
}
}
六． 修补这个图
void Fix(TreeNode *T) //修补残图
{
//首先是边界线
for(int i=;i<=T->col;i++)
{
if(tu[][i]==)
{
tu[][i]='-';
if(tu[][i]!=) tu[][i]='*';
}
if(tu[T->row][i]==)
{
tu[T->row][i]='-';
if(tu[T->row-][i]!=) tu[T->row][i]='*';
}
}
for(int i=;i<=T->row;i++)
{
if(tu[i][]==)
{
tu[i][]='|';
if(tu[i][]!=) tu[i][]='*';
}
if(tu[i][T->col]==)
{
tu[i][T->col]='|';
if(tu[i][T->col-]!=) tu[i][T->col]='*';
}
}
//然后是四个顶点
if(tu[][T->col]<='Z'&&tu[][T->col]>='A');
else tu[][T->col]='*';
if(tu[][]<='Z'&&tu[][]>='A');
else tu[][]='*';
if(tu[T->row][]<='Z'&&tu[T->row][]>='A');
else tu[T->row][]='*';
if(tu[T->row][T->col]<='Z'&&tu[T->row][T->col]>='A');
else tu[T->row][T->col]='*';
//最后是有交叉的地方，要变成*号
for(int i=;i<=T->row;i++)
{
for(int j=;j<=T->col;j++)
{
if(tu[i][j]!=&&(tu[i][j]<'A'||tu[i][j]>'Z'))
{
int co=;
if(tu[i-][j]!=) co++;
if(tu[i][j-]!=) co++;
if(tu[i+][j]!=) co++;
if(tu[i][j+]!=) co++;
if(co>=) tu[i][j]='*';
}
}
}
}
注意在主函数中，计算完行列以后，要先将根结点的行列都加2（除非他直接是字母），因为边框的原因。
#include<stdio.h>
#include<string.h>
#include<stdlib.h> typedef struct node //树结点
{
char c; //保存该树结点的字符
int row,col; //保存该树结点的行和列，最后就是通过这个来绘制图形
struct node *fa; //父结点
struct node *lchild; //左孩子
struct node *rchild; //右孩子
}TreeNode; TreeNode *Init() //初始化树结点
{
TreeNode *x;
x=(TreeNode *)malloc(sizeof(TreeNode));
x->fa=NULL;
x->row=x->col=;
x->lchild=NULL;
x->rchild=NULL;
return x;
} TreeNode *Creat(char *s,int &ls) //根据 先序遍历 来构建这棵二叉树
{
TreeNode *T=Init(); //申请空间
T->c=s[ls++]; //赋值
if(s[ls-]=='-'||s[ls-]=='|') //如果这个结点不是叶子结点，就继续创建左右孩子
{
T->lchild=Creat(s,ls);
if(T->lchild) T->lchild->fa=T;
T->rchild=Creat(s,ls);
if(T->rchild) T->rchild->fa=T;
}
return T; //返回树结点的地址
} void Dis(TreeNode *T) //查看生成的二叉树所用。（先序遍历）
{
if(T)
{
if(T->lchild==NULL)
{
printf("自己：%c 行数：%d 列数：%d\n",T->c,T->row,T->col);
}
Dis(T->lchild);
Dis(T->rchild);
}
} void Clear(TreeNode *T) //收回动态申请的空间
{
if(T)
{
Clear(T->lchild);
Clear(T->rchild);
free(T);
}
} TreeNode *Look_min(TreeNode *T) //返回T子树的最左叶结点
{
while(T->lchild)
{
T=T->lchild;
}
return T;
} TreeNode *Look_max(TreeNode *T) //返回T子树的最右叶结点
{
while(T->rchild)
{
T=T->rchild;
}
return T;
} TreeNode *Look_fa(TreeNode *T) //查找结点T和T的前驱共同的祖先（第一个），如果T是第一个结点就返回NULL
{
while(T->fa)
{
if(T==T->fa->rchild)
{
return T->fa;
}
else T=T->fa;
}
return NULL;
} TreeNode *Look_pre(TreeNode *T) //查找结点T的前驱，如果没有前驱就返回NULL，这里说的前驱必须是叶结点
{
while(T->fa)
{
if(T==T->fa->rchild)
{
return Look_max(T->fa->lchild);
}
else T=T->fa;
}
return NULL;
} void Calculate_H(TreeNode *T,int mh,int h,int maxh,int minh)
{
if(T)
{
Calculate_H(T->lchild,mh,h,maxh,minh);
if(T->c!='|'&&T->c!='-')
{
int height=h-T->row;
height=maxh*height/minh;
T->row=mh-height+;
}
Calculate_H(T->rchild,mh,h,maxh,minh);
}
} void Calculate_L(TreeNode *T,int ml,int l,int maxl,int minl)
{
if(T)
{
Calculate_L(T->lchild,ml,l,maxl,minl);
if(T->c!='|'&&T->c!='-')
{
int length=l-T->col;
length=maxl*length/minl;
T->col=ml-length+;
}
Calculate_L(T->rchild,ml,l,maxl,minl);
}
} void Calculate_HL(TreeNode *T)
{
if(T)
{
Calculate_HL(T->lchild);
if(T->c!='|'&&T->c!='-') //即叶子结点，就是大写字符
{
TreeNode *pre=Look_pre(T); //首先计算T结点的前驱
if(pre==NULL) //如果前驱为NULL，即第一个大写字母，这个点所在的行就是第一行，列是第一列
{
T->col=;
T->row=;
}
else //如果不是第一个字母
{
TreeNode *fa=Look_fa(T); //因为前面排除了第一个字母，所以这里肯定有前驱，也就肯定有和前驱共享的第一个父结点
if(fa->c=='|') //如果父结点的字符是'|'
{
T->row=Look_min(fa)->row; //那么他的行数和最左孩子是一个档次的，即都为这个被左右分成两半的窗口的第一行
T->col=fa->col+; //他的列在这个窗口中则是左边最大列数加2（中间有个－）
}
else
{
T->row=fa->row+; //同上，这里的每个结点保存的都是以他为根的子树的最大行数或者最大列数
/*
注意递归程序的执行，首先左子树，算完左子树就轮到根结点（中序遍历），然后更新根结点的行数为左子树的行数
就是下面那个else的执行内容，然后算右子树的时候，就可以直接使用根结点的行来表示左子树的最大行数，等右子树计
算完，再有后序遍历来重新更新根结点的值为两边的最大值
*/
T->col=Look_min(fa)->col;
}
}
}
else
{
T->col=T->lchild->col; //更新根结点的行和列，注意这里遇到的只会是'|'或'－'
T->row=T->lchild->row;
}
Calculate_HL(T->rchild);
if(T->c=='|'||T->c=='-')
{
T->row=T->row>T->rchild->row?T->row:T->rchild->row; //这个就是后序遍历更新根结点的位置
T->col=T->col>T->rchild->col?T->col:T->rchild->col;
/*
最后，如果这个根结点的字符是'|'，就是左右分开这个窗口，那么要计算两边的行，按比例更新行的大小，如果是'－'，同样
也要更新上下两个子窗口的列
*/
if(T->c=='|')
{
int mr_lchild=T->lchild->row; //左子树的最大行数
int mr_rchild=T->rchild->row; //右子树的最大行数
if(mr_lchild>mr_rchild) //右子树比较低，那么要按照比例拉伸右子树
{
int mh=mr_lchild+; //先将行转化为高度,下面是细节。
int h=mr_rchild+;
int maxh=mh-Look_min(T->lchild)->row+;
int minh=h-Look_min(T->rchild)->row;
Calculate_H(T->rchild,mh,h,maxh,minh);
}
else
{
int mh=mr_rchild+;
int h=mr_lchild+;
int maxh=mh-Look_min(T->lchild)->row+;
int minh=h-Look_min(T->rchild)->row;
Calculate_H(T->lchild,mh,h,maxh,minh);
}
}
else //同上
{
int mc_lchild=T->lchild->col;
int mc_rchild=T->rchild->col;
if(mc_lchild>mc_rchild)
{
int ml=mc_lchild+;
int l=mc_rchild+;
int maxl=ml-Look_min(T->lchild)->col+;
int minl=l-Look_min(T->rchild)->col;
Calculate_L(T->rchild,ml,l,maxl,minl);
}
else
{
int ml=mc_rchild+;
int l=mc_lchild+;
int maxl=ml-Look_min(T->lchild)->col+;
int minl=l-Look_min(T->rchild)->col;
Calculate_L(T->lchild,ml,l,maxl,minl);
}
}
}
}
} char tu[][]; //保存最终的图 void Draw(TreeNode *T)
{
if(T)
{
Draw(T->lchild);
if(T->c!='|'&&T->c!='-') //如果是字母的话，那么在那一行，那一列，填上字母
{
tu[T->row][T->col]=T->c;
}
else if(T->c=='|') //如果左右分的话，那么在右窗口所属的那个字母的列上画'|'，起点h1，终点h2
{
TreeNode *tmp=Look_min(T->rchild); //右窗口所属的那一个字母就是右子树的最左孩子
int h1=tmp->row+,h2=h1; //起点就是这个字母的下一格，先假设终点等于起点
TreeNode *fa=T->fa; //现在要找的是这个结点的祖先并且是'－'（并且这个结点是在他的左子树），这样，他右孩子的最左孩子就是目标
if(!fa) h2=T->row; //特殊情况处理，如果为NULL，那么这一竖就是直接竖到底的，就是T的行数
bool flag; //标记结点是他的父结点的左孩子还是右孩子，0 是左孩子，1是右孩子
if(fa&&fa->lchild==T) flag=; //下面就是找目标的过程
else flag=;
while(fa)
{
if(fa->c=='-'&&flag==)
{
h2=Look_min(fa->rchild)->row;
break;
}
else
{
h2=fa->row;
}
if(fa->fa&&fa->fa->lchild==fa) flag=;
else flag=;
fa=fa->fa;
}
while(h1<h2) //确定了起点和终点，就可以开始画线了
{
tu[h1++][tmp->col]='|';
}
/*
下面过程不能直接忽略，因为如果*都留到最后处理，会很麻烦。
*/
if(tu[h1][tmp->col]<='Z'&&tu[h1][tmp->col]>='A'); //竖到头后，那个点一般是*，或者有可能遇到字母，就忽略
else
{
tu[h1][tmp->col]='*';
}
}
else //同上
{
TreeNode *tmp=Look_min(T->rchild);
int l1=tmp->col+,l2=l1;
TreeNode *fa=T->fa;
if(!fa) l2=T->col;
bool flag;
if(fa&&fa->lchild==T) flag=;
else flag=;
while(fa)
{
if(fa->c=='|'&&flag==)
{
l2=Look_min(fa->rchild)->col;
break;
}
else
{
l2=fa->col;
}
if(fa->fa&&fa->fa->lchild==fa) flag=;
else flag=;
fa=fa->fa;
}
while(l1<l2)
{
tu[tmp->row][l1++]='-';
}
if( tu[tmp->row][l1]<='Z'&& tu[tmp->row][l1]>='A');
else
{
tu[tmp->row][l1]='*';
}
}
Draw(T->rchild);
}
} void Fix(TreeNode *T) //修补残图
{
//首先是边界线
for(int i=;i<=T->col;i++)
{
if(tu[][i]==)
{
tu[][i]='-';
if(tu[][i]!=) tu[][i]='*';
}
if(tu[T->row][i]==)
{
tu[T->row][i]='-';
if(tu[T->row-][i]!=) tu[T->row][i]='*';
}
}
for(int i=;i<=T->row;i++)
{
if(tu[i][]==)
{
tu[i][]='|';
if(tu[i][]!=) tu[i][]='*';
}
if(tu[i][T->col]==)
{
tu[i][T->col]='|';
if(tu[i][T->col-]!=) tu[i][T->col]='*';
}
}
//然后是四个顶点
if(tu[][T->col]<='Z'&&tu[][T->col]>='A');
else tu[][T->col]='*';
if(tu[][]<='Z'&&tu[][]>='A');
else tu[][]='*';
if(tu[T->row][]<='Z'&&tu[T->row][]>='A');
else tu[T->row][]='*';
if(tu[T->row][T->col]<='Z'&&tu[T->row][T->col]>='A');
else tu[T->row][T->col]='*';
//最后是有交叉的地方，要变成*号
for(int i=;i<=T->row;i++)
{
for(int j=;j<=T->col;j++)
{
if(tu[i][j]!=&&(tu[i][j]<'A'||tu[i][j]>'Z'))
{
int co=;
if(tu[i-][j]!=) co++;
if(tu[i][j-]!=) co++;
if(tu[i+][j]!=) co++;
if(tu[i][j+]!=) co++;
if(co>=) tu[i][j]='*';
}
}
}
} int main()
{
//freopen("1.in","r",stdin);
//freopen("1.out","w+",stdout);
TreeNode *T;
char s[];
int t,g=;
scanf("%d",&t);
while(t--)
{
printf("%d\n",g++);
scanf("%s",s);
int ls=;
T=Creat(s,ls);
Calculate_HL(T);
memset(tu,,sizeof(tu));
if(T->lchild!=NULL)
{
T->row+=;
T->col+=;
Draw(T);
Fix(T);
for(int i=;i<=T->row;i++)
{
for(int j=;j<=T->col;j++)
{
printf("%c",tu[i][j]==?' ':tu[i][j]);
}
printf("\n");
}
}
else
{
printf("%c-*\n",T->c);
printf("| |\n");
printf("*-*\n");
}
Clear(T);
}
return ;
}
AC代码