题目描述
输入
(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
思路1:指针方式实现二叉树 (链式存储)
首先定义一个结构体，然后定义一个结构体指针root，作为整棵树的根节点。如果需要用到左右节点则申请一个空间，也就是用不到的就不申请，以节省空间。
遍历方式是广度优先遍历(BFS)，从根节点依次拓展子节点，如果有子节点就入队，然后根节点出队。继续拓展，直到队列为空，即遍历完整棵树。
因为指针丢失以后会造成内存泄露，所以在每次读取二叉树之前都要释放掉上一棵树申请的内存，二叉树的删除也是递归删除的。
参考代码
#include<bits/stdc++.h> using namespace std; const int maxn = 256+10; bool failed; char s[maxn]; struct Node{ bool have_value;//标记是否赋过值 int v; Node *left,*right; Node():have_value(false),left(NULL),right(NULL){} ;//构造方法,以便进行初始化 }; Node *root;//根节点 void remove_tree(Node *u){ if(u==NULL){ return; } remove_tree(u->left); remove_tree(u->right); delete u; } Node *newnode(){//创建新节点. return new Node();//我在这里是不是可以创建一个局部变量,然后把地址返回.. 不能,因为这是一个函数,一旦执行完,里面所有的局部变量全部被销毁. //所以如果需要一个指针类型的结构体变量,应该动态分配内存. } void addnode(int v,char*s){ int n = strlen(s); Node* u = root; 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->have_value){//如果已经赋过值了则标记发生变化. failed = true; } u->v = v;//给当前节点进行赋值. u->have_value = true;//标记发生变化. } bool read_input(){ failed = false; remove_tree(root);//因为有多个案例,所以先释放上一次根节点的内存. root = newnode(); while(1){ //gets(s); if(scanf("%s",&s)!=1){ return false; } if(!strcmp(s,"()")) break; int v; sscanf(&s[1],"%d",&v);//从字符串中提取处整数.如(11,LL) 则把11放到v中 addnode(v,strchr(s,',')+1);// strchr(s,','):返回从左到右第一次出现的指针;如(11,LL) strchr(s,',')+1: "LL)" } 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)) failed = 1; if(failed){ printf("not complete\n"); } else{ for(int i = 0; i < ans.size(); i++){ if(i!=0){ cout<<" "; } cout<<ans[i]; } cout<<endl; } } return 0; }
思路2:数组方式实现二叉树 (对应着顺序存储)
每新建一个节点计数器cnt就自增1
#include<bits/stdc++.h> using namespace std; const int maxn = 300; const int root = 1; char s[maxn]; bool have_value[maxn], failed; int L[maxn], R[maxn], val[maxn], cnt; vector<int> ans; void newtree() {//新建树 L[root] = R[root] = 0; have_value[root] = false; cnt = root; } int newnode()//创建新节点 { int u = ++cnt; L[u] = R[u] = 0; have_value[u] = false; return u; } void addnode(int v, char* s) { int u = root;//辅助变量 for (int i = 0; i < strlen(s); i++) { if (s[i] == 'L') { if (L[u] == 0) L[u] = newnode(); u = L[u]; } else if (s[i] == 'R') { if (R[u] == 0) { R[u] = newnode(); } u = R[u]; } } if (have_value[u])//如果一个节点有多次赋值,则做标记 failed = true; val[u] = v; have_value[u] = true; } bool read_input() { failed = false; newtree(); while (1) { //scanf("%s",s); if(scanf("%s", s) != 1)//这里应该进行判断,到文件结束了还没到"()",那么就结束程序.避免陷入死循环 { //cout<<"hahahhh"<<endl; return false; } if(!strcmp(s,"()")){ break; } int v; sscanf(&s[1], "%d", &v); addnode(v, strchr(s,',')+1); } return true; } bool BFS() { 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(val[u]); //把索引对应的值放进去 if (L[u] != 0) { q.push(L[u]);// } if (R[u] != 0) { q.push(R[u]); } } return true; } int main() { while (read_input()) { if (failed || !BFS()) { cout << "not complete" << endl; } else { cout << ans[0]; for (int i = 1; i < ans.size(); i++) { cout << " " << ans[i]; } cout << endl; } } return 0; }
注意:
二叉树存储有两种方式.牵涉到查询节点位置的一般用顺序,插入删除结点的一般用链式.
对于scanf输入最好对返回值进行判断一下,防止文件读取完毕了,程序还没有停止.
字符串的读入既可以使用string又可以使用字符数组,使用字符数组时,参数传递字符指针.而且使用字符数组,读取效率会更高,而使用string则很难用scanf读取.到时根据需要进行选择.
最后附上我用string稍微改造了下,但是提交会TLE,所以最好还是使用字符数组,然后scanf既可以判断又可以提高效率.
#include<bits/stdc++.h> using namespace std; const int maxn = 300; const int root = 1; string s; bool have_value[maxn], failed; int L[maxn], R[maxn], val[maxn], cnt; vector<int> ans; void newtree() {//新建树 L[root] = R[root] = 0; have_value[root] = false; cnt = root; } int newnode()//创建新节点 { int u = ++cnt; L[u] = R[u] = 0; have_value[u] = false; return u; } void addnode(int v, string& s) { int u = root;//辅助变量 for (int i = 0; i < s.size(); i++) { if (s[i] == 'L') { if (L[u] == 0) L[u] = newnode(); u = L[u]; } else if (s[i] == 'R') { if (R[u] == 0) { R[u] = newnode(); } u = R[u]; } } if (have_value[u])//如果一个节点有多次赋值,则做标记 failed = true; val[u] = v; have_value[u] = true; } bool read_input() { failed = false; newtree(); while (1) { cin>>s; if (s.compare("()")==0) {//这个函数的返回值是个整数,所以判断条件要写清. break; } int v; sscanf(&s[1], "%d", &v); addnode(v, s);//这里不能使用字符串截取,因为当这个函数执行完这个临时变量就不存在了. } return true; } bool BFS() { 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(val[u]); //把索引对应的值放进去 if (L[u] != 0) { q.push(L[u]);// } if (R[u] != 0) { q.push(R[u]); } } return true; } int main() { while (read_input()) { if (failed || !BFS()) { cout << "not complete" << endl; } else { cout << ans[0]; for (int i = 1; i < ans.size(); i++) { cout << " " << ans[i]; } cout << endl; } } return 0; }
