欢迎访问我的pat甲级题解目录哦https://blog.csdn.net/richenyunqi/article/details/84981078

题目描述

 

算法设计

我在pat甲级1020. Tree Traversals (25)中介绍过如何利用后根遍历序列和中根遍历序列重建一棵树，得出层次遍历序列的三种形式，在本题中，我是使用静态二叉链表存储这棵树的，而且为了方便，我是直接将后根遍历序列的元素赋值给这棵树的底层数组元素。对于重建一棵树的算法在此不再赘述，介绍一下如何输出题中的序列，显然，题中的序列是按层输出的，第一层从右向左输出，第二层从左向右输出，第三层又从右向左……如此循环往复直至输出整棵树所有节点。为了实现这样的输出序列，可以定义一个vector的数组levelElement，以层数作为数组下标，将每一层的元素都按从左向右的顺序存储在对应的levelElement的一个元素vector中，这一过程深度优先搜索或广度优先搜索均可实现。然后遍历LevelElement，如果当前所处层数为偶数（层数由0开始编号），就从前向后输出levelElement中元素；否则从后向前输出。

使用深度优先搜索的C++代码

#include<bits/stdc++.h> using namespace std; struct Node{//树的结点类 int data,left=-1,right=-1; }; Node tree[35];//树，存储后根遍历序列 int N,in[35],maxLevel=-1;//maxLevel表示最大层数 vector<int>levelElement[30];//存储每一层的元素 int createTree(int root,int left,int right){//重建一棵树 if(left>right) return -1; int i=left; while(in[i]!=tree[root].data)//在中根遍历序列中查找根节点位置 ++i; tree[root].left=createTree(root-1+i-right,left,i-1);//递归重建左子树 tree[root].right=createTree(root-1,i+1,right);//递归重建右子树 return root;//返回根节点位置 } void DFS(int v,int level){//深度优先搜索 if(v==-1) return; maxLevel=max(level,maxLevel);//更新最大层数 levelElement[level].push_back(tree[v].data);//将当前结点压入对应层数下 DFS(tree[v].left,level+1);//递归遍历左子树 DFS(tree[v].right,level+1);//递归遍历右子树 } int main(){ scanf("%d",&N); for(int i=0;i<N;++i) scanf("%d",&in[i]); for(int i=0;i<N;++i) scanf("%d",&tree[i].data); int root=createTree(N-1,0,N-1); DFS(root,0); for(int i=0;i<maxLevel+1;++i)//输出 if(i%2==1) for(int j=0;j<levelElement[i].size();++j) printf("%s%d",i>0?" ":"",levelElement[i][j]); else for(int j=levelElement[i].size()-1;j>=0;--j) printf("%s%d",i>0?" ":"",levelElement[i][j]); return 0; }

使用广度优先搜索的c++代码

#include<bits/stdc++.h> using namespace std; struct Node{//树的结点类 int data,left=-1,right=-1,level=0;//level表示所处层数 }; Node tree[35];//树，存储后根遍历序列 int N,in[35],maxLevel=-1; vector<int>levelElement[30];//存储每一层的元素 int createTree(int root,int left,int right){//重建一棵树 if(left>right) return -1; int i=left; while(in[i]!=tree[root].data)//在中根遍历序列中查找根节点位置 ++i; tree[root].left=createTree(root-1+i-right,left,i-1);//递归重建左子树 tree[root].right=createTree(root-1,i+1,right);//递归重建右子树 return root;//返回根节点位置 } void BFS(int root){ queue<int>q; q.push(root); while(!q.empty()){ int t=q.front(); levelElement[tree[t].level].push_back(tree[t].data); maxLevel=max(maxLevel,tree[t].level);//更新最大层数 q.pop(); if(tree[t].left!=-1){ tree[tree[t].left].level=tree[t].level+1; q.push(tree[t].left); } if(tree[t].right!=-1){ tree[tree[t].right].level=tree[t].level+1; q.push(tree[t].right); } } } int main(){ scanf("%d",&N); for(int i=0;i<N;++i) scanf("%d",&in[i]); for(int i=0;i<N;++i) scanf("%d",&tree[i].data); int root=createTree(N-1,0,N-1); BFS(root); for(int i=0;i<maxLevel+1;++i)//输出 if(i%2==1) for(int j=0;j<levelElement[i].size();++j) printf("%s%d",i>0?" ":"",levelElement[i][j]); else for(int j=levelElement[i].size()-1;j>=0;--j) printf("%s%d",i>0?" ":"",levelElement[i][j]); return 0; }