题意:第一行几棵树,下面一行就是后序序列,在后面一行是中序序列。 题解:这是一道数据结构题,基本上就是可以通过后序和中序来确定层序,基本思路就是根据后序确定根节点,然后根据中序的根节点,分成左子树和右子树,然后不断的回溯直到左子树和右子树不能再分位置,所得到的就是排序好的树,然后再通过输出遍历的方式得到层序,这个可以用到树的输出,一般用的是队列。 详细代码样例:
using namespace std;
//建树
//先建立树的节点
int N;
int Post[40],In[40];//建立数组存后序和中序
struct node{
int value;//树的全脂
node * right;//右子树指针
node * left;//左子树指针
};
//根据树后序和中序建立树
node * maketree(int h1,int t1,int h2,int t2){//表示后序从h1到t1,中序从h2到t2
//递归先写返回条件
if(h1>t1) return NULL;
node *p = new node;
p->value = Post[t1];//后序的最后一个数就是根节点
//在中序里面找到根节点的位置,准备递归
int index;
for(index=h2;Post[t1]!=In[index];index++);//利用for找到根节点在中序的index
//开始递归,左子树和右子树的递归
p->left=maketree(h1,index-h2-1+h1,h2,index-1);//难点在于index与左子树后序里面的尾数 以及右子树头数
p->right=maketree(index-h2+h1,t1-1,index+1,t2);
return p;
}
int main(){
//存数据
cin>>N;
for(int i=0;i<N;i++) cin>>Post[i];
for(int i=0;i<N;i++) cin>>In[i];
node *root = maketree(0,N-1,0,N-1);//建树 建立好根节点
//建好了之后需要取出来,利用队列取树
node *Queue[40];
int head=0,tail=0;//像指针往后移动
Queue[tail++] = root;//第一个根节点存入队列
while(head<tail){//循环取数
if(head!=0) cout<<' ';//符合输出格式
node *p = Queue[head++];
cout<<p->value;
if(p->left) Queue[tail++]=p->left;
if(p->right) Queue[tail++]=p->right;//先左子树再右子树 这样左右子树就是顺序出来的了
}
}
这道题难度着在于如何对于一个后序和中序,进行一个回溯得到一个指针形式的树,再通过树的遍历方式得到层序,该题目对于数据结构的要求比较高。
|