通过例题学习对树的相关操作，为BFS和DFS打好基础，以刘佬给的代码为准，加些解释以便理解。（本题刘佬提出内存泄漏的情况，本文未提及，若有需要请自行阅读书本）
文章目录
- 前言
- 一、题目
- 二、问题分析
- 三、完整代码
前言
第五章：大致码完书上STL的题（不会的看题解，最起码题解看懂，看不懂也没事）先理解STL的一些基本内容就好后面刷题再补
第六章：6.1和6.2 快速过一遍，看例题，自己动手敲敲就好了
6.3就是梦的开始，BFS与DFS用的地方很广，我个人认为这一章DFS和BFS最为重要，看的时候要扣好每个细节。
一、题目
树状结构在电脑科学的许多领域中都相当重要。本问题牵涉到建立树及遍历树。
下为输入输出的案例：
输入：
(11,LL) (7,LLL) (8,R) (5,) (4,L) (13,RL) (2,LLR) (1,RRR) (4,RR) () (3,L) (4,R) ()
输出：
5 4 8 11 13 4 7 2 1 not complete
二、问题分析
该题需要注意的是，我们不仅仅只是构造树然后遍历输出
题目指出，输入的数据可能不构成树（分为两种情况）：
-
有某些该有的节点没有给
-
有某些节点重复给
数据读入即为一个难点
我们在读入节点的时候，将其存到树中，下面为“数据读入函数”
char s[maxn];bool read_input()
{failed = false; //root = newnode(); //创造树的根节点for(;;) //每组数据为一个循环，如（11，LL）{ if(scanf("%s", s) != 1) return false; //scanf只要读入字符串，函数结果就为1，读入空则为0，使得每次循环处理一个数据if(!strcmp(s, "()")) break; //结束标志int v; sscanf(&s[1], "%d", &v); //该处sscanf函数为从字符串中提取第一个数字存到v中，即将要处理的数据给vaddnode(v, strchr(s, ',')+1); //addnode函数需要我们定义，将需要处理的数据按“，”后面的字母（如“L”）进行处理}return true;
}关于树的建立如下
struct Node {bool have_value; //作为一个标记，判断该结点是否被赋值int num; //该结点存入的数据Node *left,*right; Node() //养成结点初始化为空的习惯{have_value=false;left=NULL;right=NULL;}; }；
在每次处理一个新数据时，我们需要对树进行扩展，因此，我们还需要一个构造树结点的函数（用到new函数，申请空间并构造函数，如果空间不足则返回NULL）：
Node* newnode（）
{return new Node（）；
}
对于“数据读入函数”中的addnode函数，我们进行如下定义：
void addnode(int v,char* s) //传入处理的数据v和字符串s（s是从原s的逗号后面第一个字符开始的）{int n=strlen(s); //n为长度Node* u=root; //根结点root的地址为ufor(int i=0; i<n; i++){if(s[i]=='L') //读到”L“时候，当前结点的左结点若为空，则建一个，当前的u为之前的u指向的左结点{if(u->left==NULL) u->left=newnode;u=u->left;}else{if(s[i]=='R') //读到”R“时同理{if(u->right==NULL)u->right=newnode();u=u->right;}}}if(u->have_value) failed=true; //若该结点已被赋值u->num=v; //当前u为数据v应该在的位置，数据v赋给它对应u结构体的数据numu->have_value=true; //别忘了标记该结点为已赋值}最难的部分已经结束了，现在只要用队列实现BFS离AC不远了
bool BFS(vector<int>& ans) //用ans来存输出数据{queue<Node*> q;ans.clear(); //ans清空别忘了q.push(root); //队列q，从根结点root开始排队while(!q.empty()){Noede* u=q.front(); //对即将出队的头部结点的子结点进行遍历q.pop();if(!u->have_value) return false; //如果该结点没有赋值，则说明输入有误ans.push_back(u->num); //父结点访问if(u->left!=NULL) q.push(u->left); //如果左结点非空，则将其入队if(u->right!=NULL) q.push(u->right);}return true;}三.完整代码
#include <iostream>
#include<vector>
#include<queue>
#include<cstring>
#define maxn 1001000
using namespace std;struct Node
{bool have_value;int num;Node *left,*right;Node(){have_value=false;left=NULL;right=NULL;};
};
char s[maxn];
bool failed=false;
int num;
Node* root;
Node* newnode()
{return new Node();
}bool BFS(vector<int>& ans) //用ans来存输出数据
{queue<Node*> q;ans.clear(); //ans清空别忘了q.push(root); //队列q，从根结点root开始排队while(!q.empty()){Node* u=q.front(); //对即将出队的头部结点的子结点进行遍历q.pop();if(!u->have_value) return false; //如果该结点没有赋值，则说明输入有误ans.push_back(u->num); //父结点访问if(u->left!=NULL) q.push(u->left); //如果左结点非空，则将其入队if(u->right!=NULL) q.push(u->right);}return true;
}void addnode(int v,char* s) //传入处理的数据v和字符串s（s是从原s的逗号后面第一个字符开始的）
{int n=strlen(s); //n为长度Node* u=root; //根结点root的地址为ufor(int i=0; i<n; i++){if(s[i]=='L') //读到”L“时候，当前结点的左结点若为空，则建一个，当前的u为之前的u指向的左结点{if(u->left == NULL) u->left=newnode();u=u->left;}else{if(s[i]=='R') //读到”R“时同理{if(u->right==NULL)u->right=newnode();u=u->right;}}}if(u->have_value) failed=true; //若该结点已被赋值u->num=v; //当前u为数据v应该在的位置，数据v赋给它对应u结构体的数据numu->have_value=true; //别忘了标记该结点为已赋值
}bool read_input()
{failed =false;root = newnode();for(;;){if(scanf("%s", s) != 1) return false;if(!strcmp(s, "()")) break;int v;sscanf(&s[1], "%d", &v);addnode(v, strchr(s, ',')+1);}return true;
}int main()
{vector<int> ans;while(read_input()){if(failed||!BFS(ans)){cout<<"not complete";}else{for(vector<int>::iterator t=ans.begin(); t!=ans.end(); t++){if(t!=ans.end()-1){cout<<*t<<" ";}else cout<<*t;}}cout<<endl;}return 0;
}
虽然很好理解树的概念，但一上手就写不了了
