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;
}