【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