PAT 甲级 1130 Infix Expression (25 point(s)) 二叉树中序遍历

本是古典何须时尚 2024-05-08 06:14 3阅读 0赞

##### 题目 #####

[题目链接][Link 1]

##### 思路 #####

思路：根据树表达式写出正确的表达式，除了根节点和叶结点外，其他结点在遍历左子树时都必须先输出左括号，然后当遍历完右子树后输出右括号

##### 代码 #####

# include<iostream>
    # include<set>
    # include<string>
    
    using namespace std;
    const int maxn = 30;
    
    struct node {
        
         int left, right;
         string s;
    }tree[maxn];
    
    bool visited[maxn] = {
        false};
    
    int r;
    
    void inorder(int root) {
        
         //如果是叶子结点的下一层，直接退出
         if(root == -1) return;
         //如果是叶子结点，直接输出
         if(tree[root].left == -1 && tree[root].right == -1) cout << tree[root].s;
         else{
        
              //如果既不是叶子结点也不是根节点，那么在遍历左子树时需要输出一个括号
              if(root != r) printf("(");
              inorder(tree[root].left);
              cout << tree[root].s;
              inorder(tree[root].right);
              if(root != r) printf(")");
         }
    }
    
    int main(){
        
         int n;
         scanf("%d", &n);
         for(int i = 1; i <= n; i ++) {
        
              int left, right;
              string exp;
              cin >> exp >> left >> right;
              tree[i].left = left, tree[i].right = right;
              tree[i].s = exp;
              visited[left] = visited[right] = true;
         }
         //找到根结点
         for(int i = 1; i <= n; i ++){
        
              if(!visited[i]){
        
                   r = i;
                   break;
              }
         }
         inorder(r);
         system("pause");
         return 0;
    }

[Link 1]: https://pintia.cn/problem-sets/994805342720868352/problems/994805347921805312