（信息学奥赛一本通- P1366）)
【题目描述】
树的凹入表示法主要用于树的屏幕或打印输出，其表示的基本思想是兄弟间等长，一个结点的长度要不小于其子结点的长度。二叉树也可以这样表示，假设叶结点的长度为1，一个非叶结点的长度等于它的左右子树的长度之和。
一棵二叉树的一个结点用一个字母表示（无重复），输出时从根结点开始：
每行输出若干个结点字符（相同字符的个数等于该结点长度），
如果该结点有左子树就递归输出左子树；
如果该结点有右子树就递归输出右子树。
假定一棵二叉树一个结点用一个字符描述，现在给出先序和中序遍历的字符串，用树的凹入表示法输出该二叉树。
【输入】
两行，每行是由字母组成的字符串（一行的每个字符都是唯一的），分别表示二叉树的先序遍历和中序遍历的序列。
【输出】
行数等于该树的结点数，每行的字母相同。
【输入样例】
ABCDEFG CBDAFEG【输出样例】
AAAA BB C D EE F G/* //先建树（顺序存储），然后记录每个节点的度数，最后按先序遍历把每个节点 //输出，输出个数等于节点长度。但顺序存储不是很推荐，因为可能世代单传 #include <bits/stdc++.h> using namespace std; string a,b; struct node{ int l;//左儿子 int r;//右儿子 int len;//长度 char data;//字符 int parents; node(){ l=r=len=parents=0; } }tre[2000]; //后序遍历 计算每个节点的长度 void dfs(int root){ if(tre[root].l) dfs(root*2); if(tre[root].r) dfs(root*2+1); tre[tre[root].parents].len+=tre[root].len; } //先序遍历把每个节点输出，输出个数等于节点长度 void preorder(int root){ for(int i=1;i<=tre[root].len;i++) cout<<tre[root].data; cout<<endl; if(tre[root].l) preorder(root*2); if(tre[root].r) preorder(root*2+1); } //la代表这一轮先序遍历的起点，ra先序遍历的终点 //lb代表这一轮中序遍历的起点，rb中序遍历的终点 //k代表tre添加到了第k个节点 void build(int la,int ra,int lb,int rb,int k){ //找到这一轮的根节点在b中的位置 int root=b.find(a[la]); tre[k].data=a[la]; if(root>lb){//代表有左子树 tre[k].l=2*k; tre[2*k].parents=k; build(la+1,root+la-lb,lb,root-1,k*2); } if(root<rb){//代表有右子树 tre[k].r=2*k+1; tre[2*k+1].parents=k; build(root-lb+la+1,ra,root+1,rb,k*2+1); } } int main(){ cin>>a>>b;//先序遍历，中序遍历 build(0,a.size()-1,0,b.size()-1,1);//建树 //所有节点层次赋予之后，就可以开始赋值了，从叶子节点开始赋值，即最后一层开始赋值 for(int j=1;j<=1999;j++)//遍历每个元素,给所有叶子节点赋长度（1）1999表示遍历完整个tre if(tre[j].l==0 && tre[j].r==0) tre[j].len=1; dfs(1);//后序遍历计算每个节点的长度 preorder(1); return 0; } */ //先建树（链式存储），然后记录每个节点的度数，最后按先序遍历把每个节点输出，输出个数等于节点长度 #include <bits/stdc++.h> using namespace std; string a,b; int ind=1; struct node{ int l;//左儿子 int r;//右儿子 int len;//长度 char data;//字符 int parents; node(){ l=r=len=parents=0; } }tre[2000]; //后序遍历 计算每个节点的长度 void dfs(int root){ if(tre[root].l) dfs(tre[root].l); if(tre[root].r) dfs(tre[root].r); tre[tre[root].parents].len+=tre[root].len; } //先序遍历把每个节点输出，输出个数等于节点长度 void preorder(int root){ for(int i=1;i<=tre[root].len;i++) cout<<tre[root].data; cout<<endl; if(tre[root].l) preorder(tre[root].l); if(tre[root].r) preorder(tre[root].r); } //la代表这一轮先序遍历的起点，ra先序遍历的终点 //lb代表这一轮中序遍历的起点，rb中序遍历的终点 //k代表tre添加到了第k个节点 void build(int la,int ra,int lb,int rb,int k){ //找到这一轮的根节点在b中的位置 int root=b.find(a[la]); tre[k].data=a[la]; if(root>lb){//代表有左子树 tre[k].l=++ind; tre[ind].parents=k; build(la+1,root+la-lb,lb,root-1,ind); } if(root<rb){//代表有右子树 tre[k].r=++ind; tre[ind].parents=k; build(root-lb+la+1,ra,root+1,rb,ind); } } int main(){ cin>>a>>b;//先序遍历，中序遍历 build(0,a.size()-1,0,b.size()-1,1);//建树 //所有节点层次赋予之后，就可以开始赋值了，从叶子节点开始赋值，即最后一层开始赋值 for(int j=1;j<=a.size();j++)//遍历每个元素,给所有叶子节点赋长度（1）1999表示遍历完整个tre if(tre[j].l==0 && tre[j].r==0) tre[j].len=1; dfs(1);//后序遍历计算每个节点的长度 preorder(1); return 0; }
