2017年计算机考研程序设计

向右看齐 2023-06-24 10:26 13阅读 0赞

### 2017年计算机考研程序设计 ###

题目：  
请设计一个算法，将给定的表达式树(二叉树)转换为等价的中缀表达式(通过括  
号反映操作符的计算次序)并输出。例如，当下列两棵表达式树作为算法的输入时：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw_size_16_color_FFFFFF_t_70]

二叉树结点定义如下：

typedef struct node
    { 
        char data[10]; //存储操作数或操作符
        struct node *left, *right;
    } BTree;

要求：  
(1)给出算法的基本设计思想。  
(2)根据设计思想，采用C或C++语言描述算法，关键之处给出注释。

参考代码

#include <bits/stdc++.h>
    using namespace std;
    
    const int N = 10;
    
    typedef struct node
    { 
        char data[10]; //存储操作数或操作符
        struct node *left, *right;
    } BTree;
    
    
    //生成中缀表达式是利用树的中序遍历
    void inOrder(BTree *tree,int depth){ 
        //depth记录深度，判断是否为根节点
        if(tree==NULL)return ;
        else if(tree->left==NULL&&tree->right==NULL){ 
            cout<<tree->data;        
            //为叶子节点（操作数）
        }
        else{ 
        //运算符
            if(depth>1){ 
                //不为根节点
                cout<<"(";
            }
            inOrder(tree->left,depth+1);
            cout<<tree->data;//输出运算符
            inOrder(tree->right,depth+1);
            if(depth>1)cout<<")";//输出右括号;
        }
    }
    
    int preorder[30];//前序遍历序列
    int inorder[30];//中序遍历序列
    char element[30][N];//元素，每一个序列编一个唯一的标识（可以按照层次遍历）
    
    BTree*  makeTree(int L1,int R1,int L2,int R2){ 
        //利用前序与中序遍历创造一个树
        //前序区间[L2,R2],中序区间[L1，R1]
        if(L1>R1)return NULL;
        BTree *bt;
        bt = new BTree();
        int p=L1,Data=preorder[L2];
        strcpy(bt->data,element[Data]);
        while(inorder[p]!=Data)p++;
        int nodecount=p-L1;
        bt->left=makeTree(L1,p-1,L2+1,L2+nodecount);
        bt->right=makeTree(p+1,R1,L2+nodecount+1,R2);
        return bt;
    }
    
    int main(){ 
        int n;//节点个数
        cin>>n;
        for(int i=0;i<n;++i){ 
            //按照层次遍历的顺序输入节点元素
            cin>>element[i];
        }
        for(int i=0;i<n;++i){ 
            //按照节点的编号输入前序遍历
            cin>>preorder[i];
        }
        for(int i=0;i<n;++i){ 
            //按照节点的编号输入中序遍历
            cin>>inorder[i];
        }
        BTree * tree = makeTree(0,n-1,0,n-1);//构造一颗树
        inOrder(tree,1);//输出中缀表达式
    }

测试数据1

8
    * + * a b c - d
    0 1 3 4 2 5 6 7
    3 1 4 0 5 2 6 7

输出1

(a+b)*(c*(-d))

测试数据2

8
    + * - a b - c d
    0 1 3 4 2 5 6 7
    3 1 4 0 2 6 5 7

输出2

(a*b)+(-(c-d))

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191222190524845.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw,size_16,color_FFFFFF,t_70