题解 P1087 【FBI树】

本人蒟蒻，初学二叉树，于是发一个朴素的解法： 建树，遍历，循规蹈矩…… **But：我在这里要给大家介绍非递归后序遍历的写法！** 程序运行时，函数调用的代价十分昂贵，而我们知道（不知道的你现在也知道了）所有递归程序都可以**非递归**的写，从而节省了许多开销 ~~在这个人心不古出题人经常卡常数的时代~~学会非递归的遍历方法是很有必要的，这种思路日后也会很有用（然而我建树还是递归的[滑稽]） 虽然这道题不建树也能做，但我们还是建树吧~~（我才不会告诉你其实是本蒟蒻只会建树的写法）~~ 首先我们知道每个根节点的值由一个区间决定，我们可以使用递归函数来表示这个连续递进的过程（别吐槽我） 在给出建树代码之前，我先展示我定义的结构体（免得和我一样的蒟蒻看不懂） ``` typedef struct node; typedef node* tree; struct node { char data; tree lchild,rchild; node()//这是构造函数，在创建一个node时自动运行，没有它会炸，当然可以用别的方式代替 { lchild=rchild=NULL; } }; ``` 建FBI树的函数： ``` void build(tree& bt,int b,int e)//将要建的树的根节点是bt bt->data 的值由a[b]~a[e]的区间决定 { bt=new node; char c; int count0=0,count1=0; for(int i=b;i<=e;i++) a[i]=='0'?count0++:count1++;//计数以判断节点 if(count0&&count1) c='F'; else if(count0) c='B'; else c='I'; bt->data=c; if(b==e) return;//边界条件 build(bt->lchild,b,(b+e)/2);//继续建树 build(bt->rchild,((b+e)/2)+1,e); } ``` 上面的建树过程应该不难理解，无非是不断切割区间 ### OK , Next : 遍历 通常的写法： ``` void postorder(tree& bt)//这是递归的 { if(bt) { postorder(bt->lchild); postorder(bt->rchild); cout<<bt->data } } ``` 非递归后序遍历写法： ``` void great_postorder(tree &bt) { tree s[2000],p=bt;//s是栈，栈顶指针是top，指向将要被遍历的节点 int top=-1,tag[2000];//tag数组起到标记的作用，与前序遍历，中序遍历不同 while(p||top>=0)//对于每一个节点当tag为 0那么处于就等待遍历右子树的状态 { while(p)//对于每一个节点当tag为 1那么处于就等待遍历根节点的状态 { s[++top]=p; tag[top]=0; p=p->lchild; } while(top>=0&&tag[top]==1)//注意这个while与下面的if顺序不能换，换了就变成中序遍历了（福利） cout<<s[top--]->data; if(top>=0) { p=s[top]; tag[top]=1; p=p->rchild; } } } ``` 还有不懂的可以问我（不嫌弃本蒟蒻的话） 这里给出完整代码（1<<n为位运算，就是2^n的意思） ``` #include<bits/stdc++.h> using namespace std; typedef struct node; typedef node* tree; struct node { char data; tree lchild,rchild; node() { lchild=rchild=NULL; } }; tree root; int n,k=1; char a[5000]; void build(tree& bt,int b,int e)//将要建的树的根节点是bt bt->data 的值由a[b]~a[e]的区间决定 { bt=new node; char c; int count0=0,count1=0; for(int i=b;i<=e;i++) a[i]=='0'?count0++:count1++;//计数以判断节点 if(count0&&count1) c='F'; else if(count0) c='B'; else c='I'; bt->data=c; if(b==e) return;//边界条件 build(bt->lchild,b,(b+e)/2);//继续建树 build(bt->rchild,((b+e)/2)+1,e); } void great_postorder(tree &bt) { tree s[2000],p=bt;//s是栈，栈顶指针是top，指向将要被遍历的节点 int top=-1,tag[2000];//tag数组起到标记的作用，与前序遍历，中序遍历不同 while(p||top>=0)//对于每一个节点当tag为 0那么处于就等待遍历右子树的状态 { while(p)//对于每一个节点当tag为 1那么处于就等待遍历根节点的状态 s[++top]=p,tag[top]=0,p=p->lchild; while(top>=0&&tag[top]==1)//注意这个while与下面的if顺序不能换，换了就变成中序遍历了（福利） cout<<s[top--]->data; if(top>=0) p=s[top],tag[top]=1,p=p->rchild; } } int main() { scanf("%d%s",&n,a+1); build(root,1,1<<n); great_postorder(root); cout<<endl; return 0; } ```