【1130】Infix expression【dfs】

      #include<iostream>
      #include<stdio.h>
      #include<stdlib.h>
      #include<math.h>
      #include<string.h>
      #include<algorithm> 
      #include<map>
      #include<vector>
      #include<queue> 
      #include<string>
      using namespace std;
      struct node{
      	string data;
     	int l,r;//左孩子和右孩子
      }a[100];
      string dfs(int root){
     	if(a[root].l==-1 && a[root].r==-1) return a[root].data;
     	if(a[root].l==-1 && a[root].r!=-1) return"("+a[root].data+
     		dfs(a[root].r)+")";
     	if(a[root].l!=-1 && a[root].r!=-1) return "("+dfs(a[root].l)+
      		a[root].data+dfs(a[root].r)+")";
     	//注意不存在左不空，右空的情况
      }
      int main(){
     	int have[100]={0},n,root=1;
      	cin>>n;
     	for(int i=1;i<=n;i++){
      		cin>>a[i].data>>a[i].l>>a[i].r;
     		if(a[i].l!=-1)  have[a[i].l]=1;
     		if(a[i].r!=-1)  have[a[i].r]=1;
      	}
     	while(have[root]==1) root++;
     	//寻找根结点(孩子结点编号中没有出现过的)
      	string ans=dfs(root);
     	if(ans[0]=='(')  ans=ans.substr(1,ans.size()-2);
     	//最后递归返回的ans，最外层可能会被括号包起来，也可能不被包起来。
     	//要判断一下，如果被包起来，把最外层括号去掉即可
      	cout<<ans;
     	system("pause");
         return 0;
      }
  
 

不用尾递归的版本

PS：//注意括号的输出应该是在运行到运算符结点的时候输出(结合用例图看看)
//如输出个左括号，然后代码继续往左下跑，跑完回来这个运算符结点，又往右下角跑，跑完回来就输出右括号

      #include<iostream>
      #include<stdio.h>
      #include<stdlib.h>
      #include<math.h>
      #include<string.h>
      #include<algorithm> 
      #include<map>
      #include<vector>
      #include<queue> 
      #include<string>
      using namespace std;
      //注意括号的输出应该是在运行到运算符结点的时候输出(结合用例图看看)
      //如输出个左括号，然后代码继续往左下跑，跑完回来这个运算符结点，又往右下角跑，跑完回来就输出右括号
      struct Node{
      	string data;
     	int left;
     	int right;
      }node[30];
      int n;
      bool notRoot[30]={false};
      int k=0;
      void inorder(int root,int layer){
     	if(root!=-1){
     		if(node[root].right!=-1&&layer>0) printf("(");
     		inorder(node[root].left,layer+1);
      		cout<<node[root].data;
     		inorder(node[root].right,layer+1);
     		if(node[root].right!=-1&&layer>0) printf(")");
      	}
      }
      int main(){
     	scanf("%d",&n);
     	int lchild,rchild;
     	for(int i=1;i<=n;i++){
      		cin>>node[i].data>>lchild>>rchild;
      		node[i].left=lchild;
      		node[i].right=rchild;
     		if(lchild!=-1)  notRoot[lchild]=true;
     		if(rchild!=-1) notRoot[rchild]=true;
      	}
     	int root;
     	for(int i=1;i<=n;i++){
     		if(!notRoot[i]){
      			root=i;
     			break;
      		}
      	}
     	inorder(root,0);
     	system("pause");
     	//return 0;
      }
  
 

文章来源: andyguo.blog.csdn.net，作者：山顶夕景，版权归原作者所有，如需转载，请联系作者。

原文链接：andyguo.blog.csdn.net/article/details/103946743