Uva11234 - Expressions

约定不等于承诺〃 2021-12-20 03:25 62阅读 0赞

###  ###

### [11234 - Expressions][] 第一道自己真正尝试的二叉树题目，虽然最后还是借鉴别人的代码，但是感觉对二叉树现在有点信心了。 ###

这道题题意就是给出一个二叉树的后续遍历结果，求直接遍历的结果。

就是先根据后续遍历序列建树，然后在一个广搜输出结果就OK。。。代码：

#include <stdio.h>
    #include <iostream>
    #include <cstring>
    #include <cstdlib>
    #include <list>
    #include <stack>
    #include <queue>
    #include <algorithm>
    using namespace std;
    const int MAXN = 10010;
    
    //树的结构
    struct Btree{
        char val;
        Btree *lchild;
        Btree *rchild;
        //Btree *father;
    };
    Btree *root ;
    char expre[MAXN];//表达式数组
    int t ;
    list<char>l;//链表存储结果
    queue<Btree*>q;//队列用来广搜
    stack<Btree*>s;//栈用来建树
    
    //节点初始化函数
    void init(Btree *u , char c){
        u->val = c;
        u->lchild = NULL;
        u->rchild = NULL;
    }
    //输出函数
    //我们利用队列进行树的层次遍历，但是每次都先遍历右儿子，把右儿子的值存入list中，记住是往前插入，最后输出即可
    void output(Btree *root){
        q.push(root);
        l.push_front(root->val);
        while(!q.empty()){
            root = q.front();
            q.pop();
            if(root->lchild != NULL || root->rchild != NULL){//只要不为空就要进行插入操作，先访问右节点
               if(root->rchild != NULL){//如果右儿子不为空，把右儿子push进队列中 ，并且则把右儿子的值插入list中
                   q.push(root->rchild);
                   l.push_front(root->rchild->val);
               }
               if(root->lchild != NULL){//如果左儿子不为空，把左儿子push进队列中 ，并且则把左儿子的值插入list中
                   q.push(root->lchild);
                   l.push_front(root->lchild->val);
               }
            }
        }
        list<char>::iterator it;//一个list迭代器来输出
        for(it = l.begin() ; it != l.end() ; it++)
            cout<<*it;
        cout<<endl;
    }
    
    //建树函数、
    //从左往右，我们知道大写字母一定是某一颗子树的根节点，那么我们从左到右，是小写字母就建立一个点并把值赋给它，然后把节点压入栈中，当遇到大写字母时，建立根节点，把栈中的两个节点分别赋为该根节点的儿子，并且出栈，同时把次根节点如栈，更新root，直到最后一个
    void solve(){
        Btree *temp;
        root = new Btree;//分配空间，记住没有分配空间是不能赋值的
        char ch;
        for(int i= 0 ; i != strlen(expre) ; i++){
            if(islower(expre[i])){//小写字母
               temp = new Btree;//建立一个临时的Btree*
               init(temp , expre[i]);//赋值函数
               s.push(temp);//压入栈
            }
            else{
                temp = new Btree;
                init(temp , expre[i]);//建立根节点
                temp->lchild = s.top();//左儿子为栈顶
                s.pop();//清除栈顶
                temp->rchild = s.top();//右儿子为栈顶
                s.pop();//清除栈顶
                if(i != strlen(expre)-1)//如果不是最后一个就把根节点入栈
                    s.push(temp);
                root = temp;//更新root
            }
        }
        output(root);
        while(!q.empty())//注意队列的情空
            q.pop();
        l.clear();//注意对list的清空
    }
    
    //主函数
    int main(){
        cin>>t;
        getchar();
        while(t--){
            gets(expre);
            solve();
        }
        return 0;
    }

[11234 - Expressions]: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2175