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

题目描述

 

题意分析

给定一棵表达式树，输出它的中缀表达式。

算法设计

相当于输出一棵二叉树的中根遍历序列，唯一需要处理的就是括号。通过样例可以看出，如果左子树或者右子树（如果存在的话）不是叶子结点，就需要()将左子树或者右子树包含进去，将这一点加入到递归过程中即可。

C++代码

#include<bits/stdc++.h> using namespace std; struct Node{//结点类 string data; int left=-1,right=-1; }; Node tree[25]; int N; bool isLeaf(int v){//判断是否是叶子结点 return tree[v].left==-1&&tree[v].right==-1; } void DFS(int v){//深度优先遍历 if(tree[v].left!=-1){//左子树非空 printf("%s",!isLeaf(tree[v].left)?"(":"");//如果左子树不是叶子结点输出( DFS(tree[v].left); printf("%s",!isLeaf(tree[v].left)?")":"");//如果左子树不是叶子结点输出) } cout<<tree[v].data; if(tree[v].right!=-1){//右子树非空 printf("%s",!isLeaf(tree[v].right)?"(":"");//如果右子树不是叶子结点输出( DFS(tree[v].right); printf("%s",!isLeaf(tree[v].right)?")":"");//如果右子树不是叶子结点输出) } } int main(){ scanf("%d",&N); bool child[N+1]={false}; for(int i=1;i<=N;++i){ cin>>tree[i].data>>tree[i].left>>tree[i].right; if(tree[i].left!=-1) child[tree[i].left]=true; if(tree[i].right!=-1) child[tree[i].right]=true; } DFS(find(child+1,child+N+1,false)-child);//child中为false的结点就是根节点 return 0; }