UVA 122（二叉樹的層次周遊 ，鍊式表示）

​​UVA 122​​

題意

就是給你給你一顆二叉樹的每一個節點的大小，以及到達它的順序。（可能重複給出節點，或者少給節點），讓你輸出二叉樹的層次周遊。如果不能構成，輸出not complete.例如：

Sample Input

(11,LL) (7,LLL) (8,R)

(5,) (4,L) (13,RL) (2,LLR) (1,RRR) (4,RR) ()

(3,L) (4,R) ()

Sample Output

5 4 8 11 13 4 7 2 1

分析

• 先按照題目給出的節點建樹，空節點也要建，隻不過不指派
• 然後利用bfs層次周遊輸出順序
• 重點，在建樹的時候判斷是否重複給節點，在周遊的時候判斷是否少了節點。 利用全局變量failed判斷。

下述代碼二叉樹采用鍊式表示，有詳細注釋

#include<bits/stdc++.h>
using namespace std;
const int N = 256 + 10;

struct node{
  bool flag;        //是否被指派過
  int v;          //節點的值
  node *left, *right;
  node():flag(false), left(NULL), right(NULL){}  //構造函數
}*root;       //根節點

node *newnode() { return new node(); }    //申請節點

bool failed;    //重複指派标記

void free(node *u)
{
  if(u == NULL)
    return;
  free(u->left);
  free(u->right);
  delete u;
}
void add(int v, char* s)      //v >>> 節點數；s >>> 節點順序
{
  node *u = root;       //從根節點往下走
  int n = strlen(s);
  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->flag)
    failed = true;    //某個節點重複給出，做标記，輸出-1
  u->v = v;        //指派
  u->flag = 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->flag)
      return false;   //有節點沒被指派，直接傳回
    ans.push_back(u->v);
    if(u->left)      //把左右節點放入隊列（如果有的話）
      q.push(u->left);
    if(u->right)
      q.push(u->right);
  }
  return true;    //輸入沒有少值的，正确
}

bool input()
{
  failed = false;
  free(root);           //釋放上一顆樹的記憶體
  root = newnode();
  char s[N];
  while(1){
    if(scanf("%s", s) != 1) 
      return false;     //整個輸入部分結束
    if(!strcmp(s, "()"))
      break;          //一顆樹讀入結束
    int v;
    sscanf(&s[1], "%d", &v);  //讀入括号裡的數，&s[1]代表從第二個字元後面的字元串
    add(v, strchr(s, ',') + 1); // strchr(s, ',') + 1代表逗号後面的字元串
  }
  return true;
}

int main()
{
  vector<int> ans;      //存放節點編号
  while(input()){       //每次輸入一棵樹
    if(!bfs(ans))
      failed = true;
    if(failed)
      printf("not complete\n");
    else{
      for (int i = 0; i < ans.size(); i++){
        printf("%d%c", ans[i], " \n"[i==(ans.size()-1)]);
      }
    }
  }
  return 0;
}