题目见紫书
6.3.2 二叉树的层次遍历
1.二叉树的实现：
a.用指针实现：用结构体记录结点，利用指针访问结点
其中变量left，right的值 new的返回值都是地址
/*二叉树的结点定义和操作*/ //结点类型 struct Node{ bool have_value; //是否被赋值过 int v; //结点值 Node *left,*right; Node():v(-1),have_value(false),left(NULL),right(NULL){}//构造函数 };
Node* newnode(){return new Node()}; //申请新结点的函数
b.用数组实现：
计数器cnt为已存在的节点数（编号最大值），用编号代替地址访问结点，用数组 [编号]来访问节点，其中left[u],right[u]都是记录的编号，结构体中的成员变量成了全局数组。
int newnode(){ int u=++cnt; left[u]=right[u]=0; have_value[root]=false; return u; }
其中指针是利用动态内存实现，需要一直申请新内存（new），为防止内存泄漏，需要释放内存
Node* newnode(){return new Node()}; //申请新结点的函数
而数组是静态内存实现，编程简单，容易调试，不需释放动态内存，只要重置结点计数器和根结点的左有子树就行了.
可以用静态数组配合空闲列表实现一个简单的内存池，防止内存溢出(不太懂，先不学，以后再看，紫书154页)
二叉树的bfs要用队列来实现
//二叉树的bfs 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; //输入正确 }
其他：
· 可以用new运算符申请空间并执行构造函数。如果返回值为NULL，说明空间不足，申请失败。
· strchr
strchr是计算机编程语言的一个函数，原型为extern char *strchr(const char *s,char c)，可以查找字符串s中首次出现字符c的位置。
指针实现如下：
注： u->v 其中u是结构指针；
任何指针都不能为空指针！包括结构指针 Node * root； 若无root=newnode（）； root就是空指针，错都不知道错到哪了；
if(!strcmp(s,"()"))break;字符串比较就这样比较
//二叉树的动态实现与层次遍历 //new和delete是运算符，没有头文件 #include<cstdio> #include<cstdlib> #include<cstring> #include<vector> #include<queue> using namespace std; const int maxn=256+10; bool failed; struct Node{ bool have_valued; int v; Node* left,*right; Node():have_valued(false),left(NULL),right(NULL){}; }; Node* root; // 此时root为空指针 Node* newnode(){return new Node;} bool addnode(int v,char* 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->have_valued)failed=true; else u->v=v; u->have_valued=true; return true; } void remove(Node* u){ if(u==NULL)return; if(u->right!=NULL)remove(u->right); if(u->left!=NULL)remove(u->left); delete u; } char s[maxn]; bool input_read(){ failed = false; root = newnode(); int v; for(;;){ if(scanf("%s",s)!=1)return false; if(!strcmp(s,"()"))break; sscanf(&s[1],"%d",&v); addnode(v,strchr(s,',')+1); } return true; } bool bfs(vector<int>& ans){ ans.clear(); queue <Node* > q; Node* u=root; q.push(u); while(!q.empty()){ if(u->have_valued) ans.push_back(u->v); else return false; q.pop(); if(u->left!=NULL)q.push(u->left); if(u->right!=NULL)q.push(u->right); u=q.front(); } return true; } int main(){ vector <int> ans; while(input_read()){ if(!bfs(ans))failed=true; if(failed)printf("not complete "); else {for(int i=0;i<ans.size();i++){ if(i!=0)printf(" "); printf("%d",ans[i]); }printf(" "); } } return 0; }
数组实现也差不多，用left【】right【】储存指针域，跟链表似的：
//二叉树的静态（数组）实现与层次遍历 #include<cstdio> #include<cstdlib> #include<cstring> #include<vector> #include<queue> using namespace std; const int maxn=256+10; const int root=1; bool failed; int cnt=1; int left[maxn]; int right[maxn]; int value[maxn]; bool have_value[maxn]; int newnode(){int u=++cnt;left[u]=0; right[u]=0;have_value[u]=false; return u;} bool addnode(int v,char* s){ int n=strlen(s),t=root; for(int i=0;i<n;i++){ if(s[i]=='L'){ if(left[t]==0)left[t]=newnode(); t=left[t]; } if(s[i]=='R'){ if(right[t]==0)right[t]=newnode(); t=right[t]; } } // printf("have value[%d]=%d ",t,have_value[t]); if(have_value[t]==true)failed=true; else have_value[t]=true; value[t]=v; return true; } void newtree(){ //相当于动态里newnode结构体拆开，因为是静态数组，无需申请内存 cnt=root; right[root]=0; left[root]=0; have_value[root]=false; } char s[maxn]; bool input_read(){ failed = false; newtree(); int v; for(;;){ if(scanf("%s",s)!=1)return false; if(!strcmp(s,"()"))break; sscanf(&s[1],"%d",&v); //printf("%s ",strchr(s,',')+1); addnode(v,strchr(s,',')+1); } return true; } bool bfs(vector<int>& ans){ ans.clear(); queue <int> qcnt; int u=1; qcnt.push(u); while(!qcnt.empty()){ u=qcnt.front();//printf("bfs-%d ",u); if(have_value[u]==false){return false;} qcnt.pop(); ans.push_back(value[u]); if(left[u]!=0)qcnt.push(left[u]); if(right[u]!=0)qcnt.push(right[u]); } return true; } int main(){ memset(have_value,false,sizeof(have_value)); memset(left,0,sizeof(left)); memset(right,0,sizeof(right)); vector <int> ans; while(input_read()){ if(!bfs(ans))failed=true; if(failed)printf("not complete "); else {for(int i=0;i<ans.size();i++){ if(i!=0)printf(" "); printf("%d",ans[i]); }printf(" "); } } return 0; }