一、二叉树(60分)
给你一个整数序列，用这些数构成一个完全二叉排序树，输出此二叉树的层序遍历序列。输入的第一行是一个整数n，表示这个整数序列的长度，输入的第二行包含n个整数，每个数代表完全二叉排序树的一个节点，现在需要输出由这n个整数构成的完全二叉排序树的层序遍历序列。
输入样例：
1856 987 -25 0 1021 -238 399 12 77 -1 72190 -25 -168 -41367 3218 12 0 -25
输出样例：
12 -1 987 -25 0 77 3218 -238 -25 0 12 56 399 1021 72190 -41367 -168 -25
个人思路，先排序输入数组得到完全二叉树的中序遍历序列，然后构建一个完全二叉索引树（这颗完全二叉树的节点存储的值是它的层数）中序遍历完全二叉索引树得到的序列，就是前面这个排完序的数组每个元素对应层数。然后再按层数输出就行。
#include <bits/stdc++.h>using namespace std;vector<int>data;vector<int>ind;vector<int>order_data;//存放index完全二叉树的中序遍历int n;//中序遍历void visits(int root){if(root>=n)return;//超过节点范围了else{visits(2*root+1);//左子树order_data.push_back(ind[root]);visits(2*root+2);//右子树}}int main() {cin>>n;int cnt=n;int tp;while(cnt--){cin>>tp;data.push_back(tp);}cnt=n;//构建索引树int level=0;//计算层数int count=1;for(int i=1;cnt>0;i++){level++;for(int k=0;k<count&&cnt>0;k++){ind.push_back(i);cnt--;//完全二叉树索引节点存放的是这个节点的层数}count*=2;}//排序，则得到了原来数据建立的排序完全二叉树的中序遍历sort(data.begin(),data.end());//得到数据visits(0);//输出数据vector<vector<int>>mymap(level);for(int i=0;i<n;i++){mymap[order_data[i]-1].push_back(data[i]);}for(int i=0;i<level;i++){for(int m=0;m<mymap[i].size();m++)cout<<mymap[i][m]<<" ";}}
50行以内解决了hhh，也可以自己算其中的其他关系，但是建立索引树应该是比较快想到的思路了
二、栈(40分）
给你一个函数调用过程，求调用的最大嵌套深度所对应的函数名，并输出调用路径，同时输出这个函数父函数（调用者）的个数和被调用的次数。同一个函数，如果有多条调用路径都可使其嵌套深度最深，则只输出第一条调用路径。
输入的数据中，若为1 funcName的形式，则表示调用funcName这个函数，若输入的是0，则表示结束对嵌套深度最大的函数的调用。
输入样例：
1 main1 input01 mysqrt01 findA01 findB1 area1 mysin01 mycos01 mysqrt0001 findC1 area1 mysin001 mysqrt1 max0001 output00
输出样例：
mysin main-findB-area 1 2mycos main-findB-area 1 1mysqrt main-findB-area 3 3max main-findC-mysqrt 1 1
个人思路：这只是简单的栈模拟，可以边输入边处理的，细心做好记录还是比较容易的
#include <bits/stdc++.h>using namespace std;map<string,int>mp;//记录每个函数调用次数map<string,set<string>>fu;//记录每个函数父函数个数vector<string>sta;//模拟栈vector<vector<string>>data(100);//记录所有最长完整调用int maxlen=0;int num=0;//num记录有多少个最长的调用int main(){int op;string func;int nowlen=0;while(cin>>op){if(op==1){nowlen++;cin>>func;sta.push_back(func);//父函数if(nowlen>1){fu[func].insert(sta[nowlen-2]);}if(mp.find(func)!=mp.end())mp[func]++;elsemp[func]=1;}else{if(nowlen>maxlen){//找到一条当前最长if(num!=0){//清空之前的for(int i=0;i<num;i++)data[i].clear();num=0;}//装入新的data[num++]=sta;maxlen=nowlen;}else if(nowlen==maxlen){//看下是不是以前出现过的int flag=0;for(int i=0;i<num;i++){if(data[i][maxlen-1]==sta[nowlen-1]){flag=1;break;}}if(!flag){data[num++]=sta;}}//出栈nowlen--;sta.erase(sta.end());}}//输出for(int i=0;i<num;i++){cout<<data[i][maxlen-1]<<" ";for(int j=0;j<data[i].size()-2;j++)cout<<data[i][j]<<"-";cout<<data[i][maxlen-2]<<" ";cout<<fu[data[i][maxlen-1]].size()<<" ";cout<<mp[data[i][maxlen-1]];cout<<endl;}}
顺便推荐一个在线编程很棒的网站：Online Compiler and IDE >> C/C++, Java, PHP, Python, Perl and 70+ other compilers and interpreters -
