蓝桥杯-历届试题-横向打印二叉树（遍历树+模拟）

//传送门：http://lx.lanqiao.cn/problem.page?gpid=T34 #include<stdio.h> #include<iostream> #include<algorithm> #include<string> #include<queue> #include<string.h> using namespace std; #define INF 0x3f3f3f3f //题意：将整棵树从右到左打印 int fir; //树根的值， 输入数据中没有重复的数字。 struct tree { int num; struct tree *l,*r; tree(){l=r=NULL;} }; void insert(tree* &head,int n) // 建树 { if(!head){ head = (tree *) new tree; head->num = n; } else if(n>head->num) insert(head->r,n); else insert(head->l,n); } void display(tree * head) // 测试用 { if(head->l) display(head->l); cout<<head->num<<endl; if(head->r) display(head->r); } string itos(int num) // 将整数转为字符串 { string s=""; int cot = 0; if(!num) return s="0"; /*if(num<0){ // 题目没有说明没有负数,但是不特判也能过 s+="-"; num*=-1; }*/ int tmp[10]; while(num){ tmp[cot++]=num; num /= 10; } for(int i=cot-1;i>=0;i--) s+=tmp[i]+'0'; return s; } void dfs(tree *head,string s,int n,string s1) //s 保存全部字符串，s1 保存从跟到当前节点左右移动的关系 { if(head->num == fir) s+=itos(head->num); else s+="-|-",s+=itos(head->num); if(head->r) s1+="1",dfs(head->r,s,n+1,s1),s1 = s1.substr(0,s1.length()-1); //先遍历右子树 int len = s.length(); int cot = 0; for(int i=0;i<len;i++){ if(s[i]=='|') { // 如果是 '|' 需要通过 s1判断能否输出 if(s1[cot]!=s1[cot+1]) cout<<"|"; else cout<<"."; cot++; }else if(cot<n) cout<<"."; // 如果不是当前位置的数，用'.'代替 else cout<<s[i]; // 输出当前数 } if(head->r||head->l) cout<<"-|"; // 如果后面有数 输出'-|' cout<<endl; if(head->l) s1+="0",dfs(head->l,s,n+1,s1),s1 = s1.substr(0,s1.length()-1); } int main() { int n; tree *head = NULL; while(~scanf("%d",&n)){ insert(head,n); } //display(head); string s = ""; string s1= ""; fir = head->num; dfs(head,s,0,s1); return 0; }