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

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

1人问答

问题描述：

建立二叉树的二叉链表表示，实现二叉树的先序、中序、后序和按层次遍历，统计并输出结点个数。

1）采用二叉链表存储结构建立二叉树，从键盘按先序输入二叉树的结点序列。如，建立如右图所示的二叉树，建立时按先序输入的结点序列为：abc###de#f##g##，其中“#”表示空格字符，用来代表空树。

（2）二叉树的建立、先序遍历、中序遍历、后序遍历均采用递归方式实现。

（3）层序遍历采用非递归方式实现。

（4）利用后序遍历算法统计结点个数。

李淑菁回答：

网友采纳

　　typedefstructnode 　　{ 　　chardata; 　　structnode*lchild,*rchild; 　　}bitree; 　　bitree*root=NULL; 　　//创建树　　bitree*CreateTree(char*sInPut) 　　{ 　　bitree*root,*s; 　　bitree*Q[128]; 　　intfront,rear; 　　root=NULL; 　　front=1; 　　rear=0; 　　chartemp[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; 　　} 　　returnroot; 　　} 　　//释放树　　voidfreetree(bitree*root) 　　{ 　　if(root!=NULL) 　　{ 　　freetree(root->lchild); 　　freetree(root->rchild); 　　free(root); 　　} 　　} 　　//前序遍历　　voidpreorder(bitree*root) 　　{ 　　if(root!=NULL) 　　{ 　　printf("%ct",root->data); 　　preorder(root->lchild,sOutPut); 　　preorder(root->rchild,sOutPut); 　　} 　　} 　　//中序遍历　　voidinorder(bitree*root) 　　{ 　　if(root!=NULL) 　　{ 　　inorder(root->lchild,sOutPut); 　　printf("%ct",root->data); 　　inorder(root->rchild,sOutPut); 　　} 　　} 　　//后序遍历　　voidpostorder(bitree*root) 　　{ 　　if(root!=NULL) 　　{ 　　postorder(root->lchild,sOutPut); 　　postorder(root->rchild,sOutPut); 　　printf("%ct",root->data); 　　} 　　} 　　//层次遍历　　voidPrintTree(bitree*root) 　　{ 　　CStringsOutPut; 　　chartemp[128]; 　　bitree*Q[128],*s; 　　intfront,rear; 　　front=0; 　　rear=0; 　　sOutPut.Empty(); 　　Q[rear++]=root; 　　while(rear>front) 　　{ 　　printf("%ct",Q[front]->data); 　　sOutPut=temp; 　　s=Q[front++]; 　　if(s->lchild!=NULL) 　　Q[rear++]=s->lchild; 　　if(s->rchild!=NULL) 　　Q[rear++]=s->rchild; 　　} 　　} 　　//树叶子数　　voidcountleaf(bitree*root,int&count) 　　{if(root!=NULL) 　　{if((root->lchild==NULL)&&(root->rchild==NULL)) 　　{count++; 　　return; 　　} 　　countleaf(root->lchild,count); 　　countleaf(root->rchild,count); 　　} 　　} 　　//树深度　　voidtreedepth(bitree*root,intl,int&h) 　　{if(root!=NULL) 　　{l=l+1; 　　if(l>h)h=l; 　　treedepth(root->lchild,l,h); 　　treedepth(root->rchild,l,h); 　　} 　　}