假设二叉数的数据元素为字符，采用二叉链式存储结构。请编码实现二叉树ADT，其中包括创建二叉树、遍历二叉树（深度、广度）、求二叉树的深度（高度）、计算二叉树的元素个数、计算二叉树的叶子数、二叉树的格式输出等。
根据输入的符号，执行相应的操作。如下：
C：创建二叉树，创建成功输出 “Created success!”。要求实现两种创建算法。输入数字“1" ，是根据完全前序序列创建二叉树，#表示空结点（空子树）；下一行输入二叉树的完全前序序列。 输入数字“2”，是根据二叉树的前序和中序序列创建二叉树，后面有三行，分别输入元素个数、前序序列和中序序列。
H：求二叉树的高度； 输出： Height=高度
L：计算二叉树的叶子数；输出：Leaves=叶子个数
N：计算二叉树中元素总个数；输出：Nodes=结点个数
1：先序遍历二叉树；输出：Preorder is:序列 .
2：中序遍历二叉树；输出：Inorder is:序列 .
3：后序遍历二叉树；输出：Postorder is:序列 .
4：广度遍历二叉树；输出：BFSorder is:序列 .
F：查找值为x的结点个数；输出：The count of x is 个数 .
P：以目录缩格文本形式输出所有节点。输出：The tree is:（换行，下面各行是输出的二叉树）
X：退出
测试用例：
输入：
test1：
C1ABC##DE#G##F###HLN1234FAPX
result1：
Created success!Height=5Leaves=3Nodes=7Preorder is:A B C D E G F .Inorder is:C B E G D F A .Postorder is:C G E F D B A .BFSorder is:A B C D E F G .The count of A is 1The tree is:ABCDEGF
test2：
C1+-*1##2##-3##4##/+5##6##*7##8##HLN1234F+PX
result2：
Created success!Height=4Leaves=8Nodes=15Preorder is:+ - * 1 2 - 3 4 / + 5 6 * 7 8 .Inorder is:1 * 2 - 3 - 4 + 5 + 6 / 7 * 8 .Postorder is:1 2 * 3 4 - - 5 6 + 7 8 * / + .BFSorder is:+ - / * - + * 1 2 3 4 5 6 7 8 .The count of + is 2The tree is:+-*12-34/+56*78
test3：
C26abdcefdbaecfHLN1234F+PX
result3：
Created success!Height=3Leaves=3Nodes=6Preorder is:a b d c e f .Inorder is:d b a e c f .Postorder is:d b e f c a .BFSorder is:a b c d e f .The count of + is 0The tree is:abdcef
题意：
题目中比较难理解的是那个‘P’：“以目录缩格文本形式输出所有节点”，观察样例我们可以发现：按行输出的顺序来看，其实是按先根序列的顺序输出，然后每个节点前带上当前节点所在的层数l*2-2的空格
思路：
由先序和中序序列建树可以参考这篇文章，
节点数我们可以在建树时就求出，叶子数和树高可以使用层序遍历求出，查找操作也可以通过层序遍历完成。
#include <iostream>#include <queue>#include <cstdio>using namespace std;struct node{char x;node* lson;node* rson;int l;node(){l=-1;}};char pre[1000],in[1000];int Height=0,Nodes=0,Leaves=0;void creat(node* &root,int l)///完全先序序列建树{root=new node;char c;cin>>c;if(c=='#') root=NULL;else{root->x=c;Nodes++;Height=max(l,Height);///计算层高creat(root->lson,l+1);creat(root->rson,l+1);}}node* recreat(int prel,int prer,int inl, int inr)///先序中序建树{if(prel>prer) return NULL;node *root=new node;root->x=pre[prel];int k;for(k=inl;k<inr;k++){if(in[k]==pre[prel])break;}int num=k-inl;root->lson=recreat(prel+1,prel+1+num-1,inl,k-1);root->rson=recreat(prel+num+1,prer,k+1,inr);return root;}void order(node* Node,int type)///先中后序遍历{if(Node==NULL) return;if(type==1)cout<<Node->x<<" ";order(Node->lson,type);if(type==2)cout<<Node->x<<" ";order(Node->rson,type);if(type==3)cout<<Node->x<<" ";}int Findcnt=0;char sign;void LayerOrder(node* e,int type)///type=0计算层高和叶子数，type=1层序遍历输出，type=2查找sign有几个{if(type==1) cout<<"BFSorder is:";if(e==NULL) return;e->l=1;queue<node*> q;q.push(e);while(!q.empty()){node* temp=q.front();if(type==2&&temp->x==sign) Findcnt++;q.pop();if(type==1)printf("%c ",temp->x);if(temp->lson){temp->lson->l=temp->l+1;if(type==1)Height=max(Height,temp->lson->l);q.push(temp->lson);}if(temp->rson){temp->rson->l=temp->l+1;if(type==0)Height=max(Height,temp->rson->l);q.push(temp->rson);}if(type==0&&!temp->rson&&!temp->lson)///没有左右孩子，说明到叶子节点Leaves++;}if(type==1) cout<<".\n";return;}void Porder(node* Node)///以目录缩格文本形式输出所有节点{if(Node==NULL) return;for(int i=1;i<=Node->l*2-2;i++) cout<<' ';cout<<Node->x<<'\n';Porder(Node->lson);Porder(Node->rson);}int main(){node* root;char c;for(int i=1;i<=11;i++){cin>>c;if(c=='C'){Nodes=Leaves=Height=0;int t;cin>>t;if(t==1) creat(root,1);if(t==2){int n;cin>>n;Nodes=n;for(int i=0;i<n;i++) cin>>pre[i];for(int i=0;i<n;i++) cin>>in[i];root=recreat(0,n-1,0,n-1);///注意区间是(0,n-1),不是(0,n);否则会多0出来}LayerOrder(root,0);///计算层高和叶子数cout<<"Created success!"<<endl;}if(c=='H') cout<<"Height="<<Height<<endl;if(c=='L') cout<<"Leaves="<<Leaves<<endl;if(c=='N') cout<<"Nodes="<<Nodes<<endl;if(c=='1'||c=='2'||c=='3'){if(c=='1')cout<<"Preorder is:";if(c=='2')cout<<"Inorder is:";if(c=='3')cout<<"Postorder is:";order(root,c-'0');cout<<".\n";}if(c=='4') LayerOrder(root,1);if(c=='F'){cin>>sign;Findcnt=0;LayerOrder(root,2);cout<<"The count of "<<sign<<" is "<<Findcnt<<endl;}if(c=='P'){cout<<"The tree is:"<<endl;Porder(root);}if(c=='X')return 0;}return 0;}
数据结构与算法实验 实验6：二叉树ADT的二叉链式实现 （由完全前序序列创建二叉树 / 求二叉树的节点数/树高/叶子节点数 /先序中序后序层序遍历）
