UVa 11234 Expressions 二叉树 层次遍历 广搜

11234-Expressions

1181

50.55%

471

89.60%

题目链接：

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=103&page=show_problem&problem=2175

题目类型： 数据结构， 二叉树

题目大意：

一般情况下，都是中缀操作符， 如x+y。然后题目给出了一种后缀操作符的形式， 变成 x y +。 进行后缀操作可以用栈模拟，使用push,pop， 过程和经典的“括号匹配”差不多。 然后要求我们转换成队列的方式，用队列的push和pop(队列的和栈的区别).

解体思路：

一开始没思路， 后来觉得听说是要建树。 这题也是我写的第一道二叉树题。

题目的最关键部分是进行二叉树建树， 以及层次遍历逆序输出，还有利用栈的“括号匹配”思想。 二叉树的基本结构是，父结点都是操作符，子节点都是数字。 对于给出的序列， 从左到右遍历，遇到代表数字的小写则建立一个无儿子的树，然后把根结点指针入栈， 遇到代表操作符的大写字母，则从栈中弹出两个根结点，然后建立一个以大写字母为根，弹出的两个操作数为左右儿子的树，再把这个新树的根结点指针压入栈。如此循环下去。 最后，在栈顶的那个指针就是最后建成的树的根结点。 然后对这颗树进行层次遍历把字母取出来，最后逆序输出即可。

样例输入：

2
xyPzwIM
abcABdefgCDEF

样例输出：

wzyxIPM
gfCecbDdAaEBF

代码：

1. 数组版

10278049

11234

Expressions

Accepted

C++

1.512

2012-07-01 12:59:01

#include<iostream>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<stack>
#include<queue>
using namespace std;

class Node{
public:
    char data;
    int left;
    int right;
};

stack<int>st;
queue<int>qu;
Node arr[10005];
char str[10005];
int result[10005], resultIndex;


// 进行广搜层次遍历
void bfs(int root){
    while(!qu.empty()) qu.pop();
    
    qu.push(root);
    result[resultIndex++]=arr[root].data;
    
    while(!qu.empty()){
        int t = qu.front();
        qu.pop();
        if(arr[t].left != -1){
            result[resultIndex++] = arr[arr[t].left].data;
            qu.push(arr[t].left);
        }
        if(arr[t].right != -1){
            result[resultIndex++] = arr[arr[t].right].data;
            qu.push(arr[t].right);
        }
    }
}

void Solve(){
    while(!st.empty()) st.pop();
    
    for(int i=0; i<strlen(str); ++i){
        if(islower(str[i])){
            st.push(i);
            arr[i].data  = str[i];
            arr[i].left  = -1;
            arr[i].right = -1;
        }
        else{
            int right = st.top();
            st.pop();
            int left  = st.top();
            st.pop();
            arr[i].data = str[i];
            arr[i].left = left;
            arr[i].right = right;
            st.push(i);     
        }
    }  
    // 按层次遍历，把字母存在一个栈上（为了逆序输出），然后输出   
    resultIndex = 0;
    bfs(st.top());   

    // 按广搜结果的逆序输出
    for(int i=resultIndex-1; i>=0; --i)
        printf("%c",result[i]);
    printf("\n");
}

int main(){
    freopen("input.txt","r",stdin);
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%s",str);
        Solve();
    }
    return 0;
}

2. 指针动态内存分配版

#include<iostream>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<stack>
#include<queue>
using namespace std;

class Node{
public:
    char data;
    Node* left;
    Node* right;
};

stack<Node*>st;
queue<Node*>qu;
char str[10005];
int result[10005], resultIndex;

// 进行广搜层次遍历
void bfs(Node* root){
    while(!qu.empty()) qu.pop();
    
    qu.push(root);
    result[resultIndex++]=root->data;
    
    while(!qu.empty()){
        Node* t = qu.front();
        qu.pop();
        if(t->left != NULL){
            result[resultIndex++] = t->left->data;
            qu.push(t->left);
        }
        if(t->right != NULL){
            result[resultIndex++] = t->right->data;
            qu.push(t->right);
        }
    }
}

void Solve(){
    while(!st.empty()) st.pop();
    
    for(int i=0; i<strlen(str); ++i){
        if(islower(str[i])){
            Node *temp = new Node;
            temp->data = str[i];
            temp->left = NULL;
            temp->right = NULL;
            st.push(temp);
        }
        else{
            Node* right = st.top();
            st.pop();
            Node* left  = st.top();
            st.pop();
            Node* parent = new Node;
            parent->data = str[i];
            parent->left = left;
            parent->right = right;
            st.push(parent);     
        }
    }  
    // 按层次遍历，把字母存在一个栈上（为了逆序输出），然后输出   
    resultIndex = 0;
    bfs(st.top());   

    // 按广搜结果的逆序输出
    for(int i=resultIndex-1; i>=0; --i)
        printf("%c",result[i]);
    printf("\n");
}

int main(){
    freopen("input.txt","r",stdin);
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%s",str);
        Solve();
    }
    return 0;
}

—— 生命的意义，在于赋予它意义。

原创http://blog.csdn.net/shuangde800，By D_Double