建立二叉树的二叉链表表示，实现二叉树的先序、中序、后序和按层次遍历，统计并输出结点个数。1）采用二叉链表存储结构建立二叉树，从键盘按先序输入二叉树的结点序列。如，建立如

Question

建立二叉树的二叉链表表示，实现二叉树的先序、中序、后序和按层次遍历，统计并输出结点个数。
1）采用二叉链表存储结构建立二叉树，从键盘按先序输入二叉树的结点序列。如，建立如右图所示的二叉树，建立时按先序输入的结点序列为： abc###de#f##g##，其中“#”表示空格字符，用来代表空树。
（2）二叉树的建立、先序遍历、中序遍历、后序遍历均采用递归方式实现。
（3）层序遍历采用非递归方式实现。
（4）利用后序遍历算法统计结点个数。

Answer 1

typedef struct node
{
char data;
struct node *lchild,*rchild;
}bitree;
bitree *root=NULL;
//创建树
bitree *CreateTree(char *sInPut)
{
bitree *root,*s;
bitree *Q[128];
int front,rear;
root=NULL;
front=1;
rear=0;
char temp[128],*p;
memset(temp,0,128);
strcpy(temp,sInPut);
p=temp;
while(strlen(p)>0)
{
s=NULL;
if(*p!='@')
{
s=(bitree*)malloc(sizeof(bitree));
s->data=*p;
s->lchild=NULL;
s->rchild=NULL;
}
rear++;
Q[rear]=s;
if(rear==1)
{
root=s;
}
else
{
if(s && Q[front])
{
if(rear%2==0)
Q[front]->lchild=s;
else
Q[front]->rchild=s;
}
if(rear%2==1) front++;
}
p+=2;
}
return root;
}
//释放树
void freetree(bitree *root)
{
if(root!=NULL)
{
freetree(root->lchild);
freetree(root->rchild);
free(root);
}
}
//前序遍历
void preorder(bitree *root)
{
if(root!=NULL)
{
printf("%c\t",root->data);
preorder(root->lchild,sOutPut);
preorder(root->rchild,sOutPut);
}
}
//中序遍历
void inorder(bitree *root)
{
if(root!=NULL)
{
inorder(root->lchild,sOutPut);
printf("%c\t",root->data);
inorder(root->rchild,sOutPut);
}
}
//后序遍历
void postorder(bitree *root)
{
if(root!=NULL)
{
postorder(root->lchild,sOutPut);
postorder(root->rchild,sOutPut);
printf("%c\t",root->data);
}
}
//层次遍历
void PrintTree(bitree *root)
{
CString sOutPut;
char temp[128];
bitree *Q[128],*s;
int front,rear;
front=0;
rear=0;
sOutPut.Empty();
Q[rear++]=root;
while(rear>front)
{
printf("%c\t",Q[front]->data);
sOutPut=temp;
s=Q[front++];
if(s->lchild!=NULL)
Q[rear++]=s->lchild;
if(s->rchild!=NULL)
Q[rear++]=s->rchild;
}
}
//树叶子数
void countleaf(bitree *root,int &count)
{ if(root!=NULL)
{ if((root->lchild==NULL)&&(root->rchild==NULL))
{ count++;
return;
}
countleaf(root->lchild,count);
countleaf(root->rchild,count);
}
}
//树深度
void treedepth(bitree *root,int l,int &h)
{ if(root!=NULL)
{ l=l+1;
if(l>h) h=l;
treedepth(root->lchild,l,h);
treedepth(root->rchild,l,h);
}
}