UVA-122 Trees on the level（树的遍历）

题目：

给出一棵树的表示，判断这棵树是否输入正确，如果正确就按层次遍历输出所有的结点，错误的话就输出not complete。

思路：

根据字符串中树的路径先将树建起来，在增加结点和层次遍历树的时候判断这棵树是不是输入正确。

错误的两种情况：

1.同一个结点被输入的两次

2.这个结点的孩子有值，但这个结点没有被输入值。

判断方法：

根据字符串中给出的路径，将整棵树先建起来，每个结点中设一个是否被访问过的标志vis

增加结点时如果这个结点的vis已经为true则为错误的情况1。

遍历树的时候，如果这个结点已经建起来了，但是value没有被赋值，则为错误情况2。

最后利用队列对树进行层次遍历，并输出。

代码：

C++

#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define MAX 1e9;
#define FRE() freopen("in.txt","r",stdin)
#define FRO() freopen("out.txt","w",stdout)
using namespace std;
typedef long long ll;
const int maxn = 4000010;
struct Node{
    Node* rt;
    Node* lt;
    int value;
    bool vis;
    Node(){
        rt = lt = NULL;
        value = 0;
        vis = false;
    }
};
bool fail = false;
Node* root = new Node();

void removeTree(Node* u){//释放树占的内存空间
    if(u==NULL) {return;}
    removeTree(u->lt);
    removeTree(u->rt);
    delete u;
}

int makeNum(string str){//提取字符串中的数字
    int ans = 0;
    for(int i = 1; str[i]!=','; i++){
        ans = ans*10 + str[i]-'0';
    }
    return ans;
}

void addNode(Node* root,int value,string str){
    Node* p = root;
    for(int i = 0; i<str.length(); i++){//忽略字符串中不是L和R的字符
        if(str[i]=='L'){//L则向左建树
            if(p->lt==NULL){
                p->lt = new Node();
            }
            p = p->lt;
        }else if(str[i]=='R'){//R则向右建树
            if(p->rt==NULL){
                p->rt = new Node();
            }
            p = p->rt;
        }
    }
    if(p->vis){//如果这个结点已经被赋值，则是错误输入情况1
        fail = true;
    }
    p->value = value;//赋值
    p->vis = true;//标记已经访问过
}

void printTree(Node* root){
    vector<int> ans;
    queue<Node*> que;
    que.push(root);
    while(!que.empty()){
        Node* temp = que.front();
        que.pop();
        if(!temp->vis) fail = true;//如果这个结点被建出来，但是没有被赋值，则是错误情况2
        ans.push_back(temp->value);
        if(temp->lt) que.push(temp->lt);
        if(temp->rt) que.push(temp->rt);
    }
    if(fail){
        cout<<"not complete"<<endl;
    }else{
        cout<<ans[0];
        for(int i = 1; i<ans.size(); i++){
            cout<<" "<<ans[i];
        }
        cout<<endl;
    }
}

int main(){
    string str;
    while(cin>>str){
        if(str=="()"){//这棵树输入结束，打印树
            printTree(root);
            removeTree(root);
            root = new Node();
            fail = false;
        }else{
            int value = makeNum(str);
            //cout<<str<<" "<<value<<endl;
            addNode(root, value, str);
        }
    }
    return 0;
}

View Code

Java

import java.io.*;
import java.util.*;

class Node{
    Node rt;
    Node lt;
    int value;
    boolean vis;
    public Node() {
        rt = null;lt = null;
        value = 0;vis = false;
    }
}

public class Main {
    public static boolean fail = false;
    public static void printTree(Node root) {
        Queue<Node> que = new LinkedList<>();
        LinkedList<Integer> list = new LinkedList<>();
        if(root==null) {
            fail = true;
        }else {
            que.offer(root);
            while(!que.isEmpty()) {
                Node temp = que.peek();que.poll();
                if(!temp.vis) {fail = true;}
                list.add(temp.value);
                if(temp.lt!=null)
                    que.offer(temp.lt);
                if(temp.rt!=null)
                    que.offer(temp.rt);
            }
        }
        if(!fail) {
            System.out.print(list.get(0));
            for(int i = 1; i<list.size(); i++) {
                System.out.print(" "+list.get(i));
            }
            System.out.println();
        }else {
            System.out.println("not complete");
        }
    }
    
    public static void addNode(Node root, int value, String str) {
        Node p = root;
        for(int i = 0; i<str.length(); i++) {
            if(str.charAt(i)=='L') {
                if(p.lt==null) {
                    p.lt = new Node();
                }
                p = p.lt;
            }else if(str.charAt(i)=='R') {
                if(p.rt==null) {
                    p.rt = new Node();
                }
                p = p.rt;
            }
        }
        if(p.vis) {
            fail = true;
        }
        p.value = value;
        p.vis = true;
    }
    
    public static int makeNum(String str) {
        int num = 0;
        for(int i = 1; str.charAt(i)!=','; i++) {
            num = num*10 + str.charAt(i)-'0';
        }
        return num;
    }
    
    public static void main(String[] args) {
        Node root = new Node();
        Scanner scan = new Scanner(System.in);
        String str=null;
        while(scan.hasNext()) {
            str = scan.next();
            if(str.equals("()")) {
                printTree(root);
                root = new Node();
                fail = false;
            }else {
                int value = makeNum(str);
                addNode(root, value, str);
            }
        }
        scan.close();
    }
}

View Code

用java做这个题的时候，利用split方法来处理字符串，结果一直是RE，找不出来了，就换了中方法（如上述代码中的）来实现，AC。