[UVa] 548 - Tree

參考入門經典一書的程式碼
改以struct建構樹的方式進行改寫
許多細節需要注意

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <queue>
#include <vector>
#include <string>
#include <cstdio>
#include <iostream>
#include <sstream>
using namespace std;
bool failed;
const int maxn = 10010;
int i=0,inorder[maxn], postorder[maxn];

struct Node{
    bool have_value;
    int v;
    Node *left, *right;
    Node():have_value(false),left(NULL),right(NULL){};
};
Node *root;

Node* newnode(){
    return new Node();
}

void remove_tree(Node* u){
    if(u==NULL)return;
    remove_tree(u->left);
    remove_tree(u->right);
    delete u;
}

Node* buildtree(int L1, int R1, int L2, int R2){
    if(L1>R1)return NULL;
    Node* u = newnode();
    u->v = postorder[R2];
    u->have_value = true;
    int p = L1;
    while(inorder[p] != u->v)p++;
    int count = p-L1; //nodes of left tree

    u->left = buildtree(L1,p-1,L2,L2+count-1);
    u->right = buildtree(p+1,R1,L2+count,R2-1);
    return u;
}

int best_sum, best;
void dfs(Node* u, int sum){
    sum = sum + u->v;
    if(u->right==NULL && u->left==NULL)
        if(sum<best_sum || (sum==best_sum && u->v < best)){
            best_sum = sum;
            best = u->v;
        }
    if(u->right){
        dfs(u->right, sum);
    }
    if(u->left){
        dfs(u->left, sum);
    }

}

/*
//顯示樹有無建立成功使用
int n=0;
vector<int> ans;
bool bfs(){
    queue<Node*> q;
    ans.clear();
    q.push(root);
    while(!q.empty()){
        Node* u = q.front(); q.pop();
        if(!u->have_value) return false;
        ans.push_back(u->v);
        n++;
        if(u->left != NULL)q.push(u->left);
        if(u->right != NULL)q.push(u->right);
    }
    return true;
}
*/

int main(){
    string line;
    while(getline(cin,line)){
        i=0;
        int x;
        stringstream ss(line);
        while(ss>>x){
            inorder[i]=x;
            i++;
        }
        int L1=0,R1=i-1;
        //for(int k=0;k<i;k++)printf("%d\n",inorder[k]);
        i=0;
        getline(cin,line);
        stringstream ss2(line);
        while(ss2>>x){
            postorder[i]=x;
            i++;
        }
        int L2=0,R2=i-1;
        //for(int k=0;k<i;k++)printf("%d\n",postorder[k]);
       
        root = buildtree(L1,R1,L2,R2);
        best_sum = 10000000;

        dfs(root,0);
        printf("%d\n",best);
        remove_tree(root);
        /*
        bfs();
        for(int j=0;j<ans.size()-1;j++){
            printf("%d ",ans[j]);
        }
        */
    }

    return 0;
}

[UVa] 122 - Trees on the level

也是參考《入門經典》一書的方法
用結構和指標去建立樹的節點

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <queue>
#include <vector>
#include <string>
#include <cstdio>
#include <iostream>
using namespace std;
const int maxn = 300;
bool failed;
char s[maxn];
struct Node{
    bool have_value; //是否已建立
    int v; //值
    Node *left, *right; //left and right node
    Node():have_value(false),left(NULL),right(NULL){}; //建構函數
};
Node *root; //root of tree

//申請新節點的函數
Node* newnode(){
    return new Node();
}

void addnode(int v, char* s){
    int n = strlen(s);
    Node* u = root; // u 從根節點往下
    for(int i=0;i<n;i++){
        if(s[i]=='L'){
            if(u->left==NULL)u->left = newnode(); //不存在則建立新節點
            u = u->left; //往左
        }else if(s[i]=='R'){
            if(u->right==NULL)u->right = newnode();
            u = u->right;
        }
    }
    if(u->have_value)failed = true;
    u->v = v;
    u->have_value = true;
}

void remove_tree(Node* u){
    if(u==NULL) return;
    remove_tree(u->left);
    remove_tree(u->right);
    free(u);
}






//讀取資料
bool read_input(){
    failed = false;
    remove_tree(root);
    root = newnode(); //建立根節點
    while(1){
        if(scanf("%s", s)!=1) return false;
        if(!strcmp(s,"()"))break; // End
        int v;
        sscanf(&s[1], "%d", &v); //讀入節點值(數字)
        addnode(v, strchr(s,',')+1);
    }
    return true;
}

int n=0;
vector<int> ans;
bool bfs(){
    queue<Node*> q;
    ans.clear();
    q.push(root);
    while(!q.empty()){
        Node* u = q.front(); q.pop();
        if(!u->have_value) return false; //錯誤
        ans.push_back(u->v); //增加到輸出尾部
        n++;
        if(u->left != NULL)q.push(u->left);
        if(u->right != NULL)q.push(u->right);
    }
    return true;
}

int main(){
    while(read_input()){
        if(!bfs())failed=1;
        if(failed)printf("not complete\n");
        else {
            for(int i=0;i<ans.size()-1;i++){
                printf("%d ",ans[i]);
            }
            printf("%d",ans[ans.size()-1]);
            printf("\n");
        }
    }
    return 0;
}