天天看點
傳回

UVa 122 - Trees on the level

解題思路：

方法一：

題目意思很明白，就是一顆二叉樹的層序周遊，那麼我看到這道題立即産生的一種想法就是，根據題目輸入對每個節點做一個映射，這顆二叉樹的每個節點我們都用一個字元串來做它的唯一辨別，那麼比如某個父節點的字元串是str，那麼它的兩個孩子節點所對應的字元串就分别是str+”L”(左孩子)和str+”R”(右孩子)，根據題目的輸入我們可以讓每個字元串映射一個整型的值，代表這個字元串所辨別的那個節點所儲存的内容(值)。然後我們用bfs層序周遊即可。（根節點所對應的字元串是空字元串，即str=”“是根節點的唯一辨別。）

這道題的輸入也比較複雜，我們需要從每個輸入的字元串當中截取出我們所需要的整數值和它所對應的字元串，見下面幾行代碼。

int v;

sscanf(&s[1],”%d”,&v);

char *ss=strchr(s,’,’)+1;

char Mystr[maxn]=”“;

sscanf(ss, “%[^)]”,Mystr);

string Mystring=Mystr;

注釋：比如輸入的字元串是”(11,LL)”，那麼&s[1] 指的就是”11,LL)”,sscanf(&s[1],”%d”,&v)意思是截取出字元串”11,LL)”中整數的值儲存到變量v中,即v=11, strchr(s,’,’)意思是傳回字元串s中字元’,’第一次出現的指針的位置，是以字元串ss=”LL)”，sscanf(ss, “%[^)]”,Mystr)意思是截取出字元串ss=”LL)”中不是字元’)’的字元儲存到變量Mystr中，即Mystr=”LL”.

接下來貼代碼：

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <ctype.h>
#include <iostream>
#include <map>
#include <list>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#define eps 1e-8
#define INF 0x7fffffff
#define PI acos(-1.0)
#define seed 31//131,1313
#define MAXV 50010
#define maxn 300
#define ALL(x) x.begin(),x.end()
#define INS(x) inserter(x,x.begin())
typedef long long LL;
typedef unsigned long long ULL;
using namespace std;
int flag=;
char s[maxn];
int longmax=;
bool read_input(map<string,int>& Mymap){
  flag=;
  longmax=;
  while(){
    if(scanf("%s",s)!=)
      return  false;
    if(!strcmp(s,"()"))
      break;
    int v;
    sscanf(&s[],"%d",&v);
    char *ss=strchr(s,',')+;
    char Mystr[maxn]="";
    sscanf(ss, "%[^)]",Mystr);
    string Mystring=Mystr;
    int len=strlen(Mystr);
    if(len>longmax) longmax=len;
    if(!Mymap.count(Mystring))
        Mymap[Mystring]=v;
    else flag=;
  }
  return true;
}
bool bfs(vector<int>& ans,map<string,int>& Mymap){
  queue<string>q;
  ans.clear();
  string a="";
  q.push(a);
  while(!q.empty()){
    string b=q.front();
    if(b.length()>longmax) break;
    string c=b+"L";
    string d=b+"R";
    q.pop();
    q.push(c);
    q.push(d);
    if(!Mymap.count(b)){
      if(Mymap.count(c)||Mymap.count(d))
        return false;
    }
    else ans.push_back(Mymap[b]);
  }
  return true;
}
int main()
{
    vector<int>ans;
    while(){
        map<string,int>Mymap;
        if(read_input(Mymap)==false) break;
        if(!bfs(ans,Mymap))
          flag=;
        if(flag==) printf("not complete\n");
        else{
          for(int i=;i<ans.size();i++){
             if(i==ans.size()-)
                printf("%d\n",ans[i]);
             else
                printf("%d ",ans[i]);
          }
        }
    }
    return ;
}

方法二：

這種方法就是劉汝佳那本書上所用的方法，先根據輸入将二叉樹建好，然後再用bfs層序周遊。

直接給代碼吧：

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <ctype.h>
#include <iostream>
#include <map>
#include <list>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#define eps 1e-8
#define INF 0x7fffffff
#define PI acos(-1.0)
#define seed 31//131,1313
#define MAXV 50010
#define maxn 300
#define ALL(x) x.begin(),x.end()
#define INS(x) inserter(x,x.begin())
typedef long long LL;
typedef unsigned long long ULL;
using namespace std;
int flag=;
char s[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; //調用u的析構函數并釋放u結點本身的記憶體
}
void addnode(int v,char *s){
  int len=strlen(s);
  Node *u=root; //從根結點開始往下走
  for(int i=;i<len;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)
    flag=;
  u->v=v;
  u->have_value=true;
}
bool read_input(){
  flag=;
  remove_tree(root);
  root=newnode();
  while(){
    if(scanf("%s",s)!=)
      return  false;
    if(!strcmp(s,"()"))
      break;
    int v;
    sscanf(&s[],"%d",&v);
    addnode(v, strchr(s,',')+);
  }
  return true;
}
bool bfs(vector<int>& ans){
  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);
    if(u->Left!=NULL){
      q.push(u->Left);
    }
    if(u->Right!=NULL){
      q.push(u->Right);
    }
  }
  return true;
}
int main()
{
    vector<int>ans;
    while(read_input()){
        if(!bfs(ans))
          flag=;
        if(flag==) printf("not complete\n");
        else{
          for(int i=;i<ans.size();i++){
             if(i==ans.size()-)
                printf("%d\n",ans[i]);
             else
                printf("%d ",ans[i]);
          }
        }
    }
    return ;
}

方法三：

和方法二差不多，隻不過這種方法是用數組來實作二叉樹的，看了劉汝佳書上給出了這種思路于是就試着敲了一下，在方法二的基礎上改了改，結果讓我足足調bug調了一上午，原因是他書上有句代碼寫錯了呀！！！坑爹呀！！！

二叉樹并不一定要用指針實作。接下來，把指針完全去掉。首先還是給每個結點編号，但不是按照從上到下從左到右的順序，而是按照結點的生成順序。用計數器cnt表示已存在的結點編号的最大值，是以new node函數需要改成這樣：

const int root = 1;

int cnt;

void newtree() {

left[root] = right[root] = 0;

have_value[root] = false;

}

int newnode() {

int u = ++cnt;

left[u] = right[u] = 0;

have_value[u]=false; //劉汝佳的書在這塊把u錯寫成root，大家注意

return u;

}

上面的newtree()是用來代替前面的“remove_tree(root)”和“root = newnode()”兩條語句的：由于沒有了動态記憶體的申請和釋放，隻需要重置結點計數器和根結點的左右子樹了。接下來，把所有的Node*類型改成int類型，然後把結點結構中的成員變量改成全局數組（例如，u->left和u->right分别改成left[u]和right[u]），除了char*外，整個程式就沒有任何指針了。

接下來貼代碼:

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <ctype.h>
#include <iostream>
#include <map>
#include <list>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#define eps 1e-8
#define INF 0x7fffffff
#define PI acos(-1.0)
#define seed 31//131,1313
#define MAXV 50010
#define maxn 300
#define ALL(x) x.begin(),x.end()
#define INS(x) inserter(x,x.begin())
typedef long long LL;
typedef unsigned long long ULL;
using namespace std;
int flag=;
char s[maxn];
bool have_value[maxn];
int Left[maxn],Right[maxn],V[maxn];
const int root=;
int cnt;
void newtree(){
  Left[root]=Right[root]=;
  have_value[root]=false;
  cnt=root;
}
int newnode(){
  int u=++cnt;
  Left[u]=Right[u]=;
  have_value[u]=false;
  return u;
}
void addnode(int v,char *s){
  int len=strlen(s);
  int u=root; //從根結點開始往下走
  for(int i=;i<len;i++){
    if(s[i]=='L'){
      if(Left[u]==)
        Left[u]=newnode();
      u=Left[u];
    }
    else if(s[i]=='R'){
      if(Right[u]==)
        Right[u]=newnode();
      u=Right[u];
    }
  }
  if(have_value[u])
    flag=;
  V[u]=v;
  have_value[u]=true;
}
bool read_input(){
  flag=;
  memset(Left,,sizeof(Left));
  memset(Right,,sizeof(Right));
  memset(V,,sizeof(V));
  newtree();
  while(){
    if(scanf("%s",s)!=)
      return  false;
    if(!strcmp(s,"()"))
      break;
    int v;
    sscanf(&s[],"%d",&v);
    addnode(v, strchr(s,',')+);
  }
  return true;
}
bool bfs(vector<int>& ans){
  queue<int>q;
  ans.clear();
  q.push(root);
  while(!q.empty()){
    int u=q.front();
    q.pop();
    if(!have_value[u])
      return false;
    ans.push_back(V[u]);
    if(Left[u]!=){
      q.push(Left[u]);
    }
    if(Right[u]!=){
      q.push(Right[u]);
    }
  }
  return true;
}
int main()
{
    vector<int>ans;
    while(read_input()){
        if(!bfs(ans))
          flag=;
        if(flag==) printf("not complete\n");
        else{
          for(int i=;i<ans.size();i++){
             if(i==ans.size()-)
                printf("%d\n",ans[i]);
             else
                printf("%d ",ans[i]);
          }
        }
    }
    return ;
樹和二叉樹
上一篇: leetcode 1579. 保證圖可完全周遊題目描述分析代碼
下一篇: 傳統機器學習筆記4——決策樹前沿一.核心思想1.1.發展史二.決策樹的生長與最優屬性的選擇2.2.最優屬性選擇

繼續閱讀