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