假设二叉数的数据元素为字符，采用二叉链式存储结构。请编码实现二叉树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：退出
例如:
| 输入 |
Result |
C
1
ABC##DE#G##F###
H
L
N
1
2
3
4
F
A
P
X
|
Created success!
Height=5
Leaves=3
Nodes=7
Preorder 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 1
The tree is:
A
B
C
D
E
G
F
|
#include <iostream>
#include <queue>
#include <stack>
using namespace std;
int cnt=0,leaves=0,nodes=0;
typedef struct node
{
struct node *lchild,*rchild;
char data;
} BiNode,*BiTree;
void creat(BiTree &T)///前序
{
char c;
cin>>c;
if(c=='#')
{
T=NULL;
}
else
{
T= new BiNode();
T->data=c;
creat(T->lchild);
creat(T->rchild);
}
}
///由前序序列和中序序列建立二叉树的过程
/* 算法
1、通过先序遍历找到根结点A，再通过A在中序遍历的位置找出左子树，右子树
2、在A的左子树中，找左子树的根结点（在先序中找），重新开始步骤1
3、在A的右子树中，找右子树的根结点（在先序中找），重新开始步骤1
*/
BiTree creat1(char *pre, char *in, int n)//pre存放前序序列，in存放中序序列，n为序列的长度
{
int i=0;
int n1=0,n2=0;
int m1=0,m2=0;
BiTree node = NULL;
char lchild_pre[100],rchild_pre[100] ;//lchild_pre[N] 存放前序序列中的左子树；rchild_pre[N]存放前序序列中的右子树
char lchild_in[100],rchild_in[100]; //lchild_in[N]存放中序序列中的左子树；rchild_in[N]存放中序序列中的右子树
if(n==0)
{
return NULL;
}
node = new BiNode();
if(node==NULL)
{
return NULL;
}
node->data = pre[0]; //前序序列的第一个元素一定是根节点
for(i=0; i<n; i++)
{
//求前序序列中的左子树和右子树
if((i<=n1)&&(in[i]!=pre[0]))
{
lchild_in[n1++]=in[i];
}
else if(in[i]!=pre[0])
{
rchild_in[n2++] = in[i];
}
}
for(i=1; i<n; i++)
{
//求中序序列中的左子树和右子树
if(i<(n1+1))
{
lchild_pre[m1++]=pre[i];
}
else
{
rchild_pre[m2++]=pre[i];
}
}
//使用递归，分别插入左子树和右子树
node->lchild =creat1(lchild_pre,lchild_in,n1);
node->rchild =creat1(rchild_pre,rchild_in,n2);
return node;
}
void Preorder(BiTree T) ///前序遍历
{
if(T!=NULL)
{
cout<<T->data<<' ';
Preorder(T->lchild);
Preorder(T->rchild);
}
}
void Inorder (BiTree T) ///中序遍历
{
if(T!=NULL)
{
Inorder(T->lchild);
cout<<T->data<<' ';
Inorder(T->rchild);
}
}
void Postorder(BiTree T) ///后序遍历
{
if(T!=NULL)
{
Postorder(T->lchild);
Postorder(T->rchild);
cout<<T->data<<' ';
}
}
void BFSorder(BiTree T) ///广序遍历
{
if(T!=NULL)
{
queue<BiTree>my;
BiTree p=T;
my.push(p);
while(!my.empty())
{
p=my.front();
cout<<p->data<<' ';
my.pop();
if(p->lchild!=NULL)
{
my.push(p->lchild);
}
if(p->rchild!=NULL)
{
my.push(p->rchild);
}
}
}
}
void Find(BiTree T,char ch=' ') ///广序遍历 只查找不输出
{
leaves=0;nodes=0;
if(T!=NULL)
{
queue<BiTree>my;
BiTree p=T;
my.push(p);
while(!my.empty())
{
p=my.front();
nodes++;
if(p->data==ch) cnt++;
my.pop();
if(p->lchild!=NULL)
{
my.push(p->lchild);
}
if(p->rchild!=NULL)
{
my.push(p->rchild);
}
if(p->lchild==NULL&&p->rchild==NULL)
{
leaves++;
}
}
}
}
int getHeight(BiTree T)
{
if(T==NULL)
{
return 0;
}
int leftheight=getHeight(T->lchild);
int rightheight=getHeight(T->rchild);
return max(leftheight, rightheight)+1;
}
void Print(BiTree T) /*用缩格文本形式表示二叉树*/
{
BiTree stack[100],p;
int level[100],top,n,i;
if (T)
{
top=1;
stack[top]=T;
level[top]=0;
while(top>0)
{
p=stack[top];
n=level[top];
for (i=1; i<=n; i++)
cout<<" ";
cout<<p->data<<endl;
top--;
if (p->rchild!=NULL)
{
top++;
stack[top]=p->rchild;
level[top]=n+2;
}
if (p->lchild!=NULL)
{
top++;
stack[top]=p->lchild;
level[top]=n+2;
}
}
}
}
int main()
{
char ch;
BiTree T;
while(1)
{
cin>>ch;
switch (ch)
{
case 'C':
char ch1;
cin>>ch1;
if(ch1=='1')
{
creat(T);
cout<<"Created success!"<<endl;
}
else
{
int n;
char ch[50],ch1[50];
cin>>n;
cin>>ch;
cin>>ch1;
T=creat1(ch,ch1,n);
cout<<"Created success!"<<endl;
}
break;
case 'H':
cout<<"Height="<<getHeight(T)<<endl;
break;
case 'L':
Find(T);
cout<<"Leaves="<<leaves<<endl;
break;
case 'N':
Find(T);
cout<<"Nodes="<<nodes<<endl;
break;
case '1':
cout<<"Preorder is:";
Preorder(T);
cout<<'.'<<endl;
break;
case '2':
cout<<"Inorder is:";
Inorder(T);
cout<<'.'<<endl;
break;
case '3':
cout<<"Postorder is:";
Postorder(T);
cout<<'.'<<endl;
break;
case '4':
cout<<"BFSorder is:";
BFSorder(T);
cout<<'.'<<endl;
break;
case 'F':
char ch2;
cin>>ch2;
Find(T,ch2);
cout<<"The count of "<<ch2<<" is "<<cnt<<endl;
break;
case 'P':
cout<<"The tree is:"<<endl;
Print(T);
break;
case 'X':
return 0;
}
}
return 0;
}
