ACM: 122 – Trees on the level

這題是用文字給出二元樹，檢查是否是完整的樹，如果是完整的樹即輸出廣度優先搜尋(BFS, Bread First Search)的結果。

我用的方法是用quicksort先對字串排序(eg, L, R, LL, LR, RL, RR,…)，接著檢查是否是完整的樹，最後再照字串順序輸出該node的數字。Runtime 0.008，程式碼也相當龐大，在這題來說顯然有更快更精簡的方法，也許可以考慮使用struct, C++的STL函式庫，也許會有更好的表現。

CODE

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

#define MAX_LEN 300
#define MAX_NODE 256

int total, num[MAX_NODE], len[MAX_NODE];
char line[MAX_NODE][MAX_NODE];
bool rep;

void sort_tree(int left, int right);
bool isbigger(int a, int b);
void swapnode(int a, int b);
bool valid_tree(void);

int main(){
  char c, snum[MAX_LEN], sline[MAX_LEN];
  int p, pnum, pline;
  int i;
  
  rep = false;
  total = 0;
  for(i=0; i<MAX_NODE; i++)
    num[i] = -1;
    
  while( (c = getchar()) != EOF ){
    if( c == '(' ){
      p = pnum = pline = 0;
    }
    else if( c == ')' ){
      if( p == 0 ){        
        sort_tree(0, total-1);
        
        if( valid_tree() ){
          cout << num[0];
          for(i=1; i<total; i++)
            cout << ' ' << num[i];
          cout << endl;
        }
        else
          cout << "not complete" << endl;
        //initialize
        rep = false;
        total = 0;
        for(i=0; i<MAX_NODE; i++)
          num[i] = -1;
      }//end of tree
      else{
        if( pnum > 0 ){
          snum[pnum] = '\0';
          sscanf(snum, "%d", &num[total]);
          
          for(i=0; i<pline; i++)
            line[total][i] = sline[i];
          line[total][pline] = '\0';
          len[total] = pline;
        }//if pnum > 0
        total++;
      }//end of node
    }
    else if( c == ',' ){
      p++;
    }
    else if( c >= '0' && c <= '9' ){
      snum[pnum++] = c;
      p++;
    }
    else if( c == 'L' || c == 'R' ){
      sline[pline++] = c;
      p++;
    }
    else ;
  }//while
  
  return 0;
}

void sort_tree(int left, int right){
  if( left < right ){
    int i = left + 1;
    int j = right;
    
    while(1){
      for(i; (isbigger(i, left)==false) && (i<=right); i++);
      for(j; (isbigger(j, left)==true) && (j>left); j--);
      if( i >= j )
        break;
      swapnode(i, j);
      i++;
      j--;
    }//while
    
    swapnode(left, j);
    sort_tree(left, j-1);
    sort_tree(j+1, right);
  }
}

//return true if a > b, return false if a <= b
bool isbigger(int a, int b){
  if( a == b )
    return false;
  if( len[a] > len[b] )
    return true;
  if( len[a] < len[b] )
    return false;
  
  for(int i=0; i<len[a]; i++){
    if( line[a][i] > line[b][i] )
      return true;
    else if( line[a][i] < line[b][i] )
      return false;
  }
  
  rep = true;
  return false;
}

void swapnode(int a, int b){
  swap(num[a], num[b]);
  swap(len[a], len[b]);
  
  char tmps[MAX_LEN];
  strcpy(tmps, line[a]);
  strcpy(line[a], line[b]);
  strcpy(line[b], tmps);
}

bool valid_tree(void){  
  if( (num[0] == -1) || (len[0] != 0) )
    return false;
  if( rep )
    return false;
  
  int i, j;
  bool flag;
  char tmps[MAX_LEN];
  for(i=1; len[i]<=1 && i<total; i++)
    if( num[i] == -1 )
      return false;
  for(i; i<total; i++){
    if( num[i] == -1 )
      return false;
      
    flag = false;
    for(j=0; j<(len[i]-1); j++)
      tmps[j] = line[i][j];
    tmps[j] = '\0';
    for(j=(i-1); (j>=0) && (len[j]>=(len[i]-1)); j--)
      if( strcmp(line[j], tmps) == 0 ){
        flag = true;
        break;
      }

    if( !flag )
      return false;
  }//i
  
  return true;
}