赞
踩
以二叉链表作存储结构,建立一棵二叉树。 输出该二叉树的先序、中序、后序遍历序列,求出该二叉树的深度,并统计其叶子结点数。
二叉链表的类型描述:
- typedef char ElemType;
- typedef struct BiNode
- { ElemType data;
- struct BiNode *lchild,*rchild;
- }BiNode,*BiTree;
输入一个二叉树的先序序列,孩子为空的位置以#
替代。
输出分五行
其中遍历过程中按访问顺序打印出结点的内容时,字符间均无间隔。
具体格式参看输出样例。
ABD##FE###CG#H##I##
- PreOrder:ABDFECGHI
- InOrder:DBEFAGHCI
- PostOrder:DEFBHGICA
- Depth:4
- Leaf:4
代码长度限制
16 KB
时间限制
400 ms
内存限制
64 MB
代码:
#include<stdio.h>
typedef char ElemType;
typedef struct BiNode
{ ElemType data;
struct BiNode *lchild,*rchild;
}BiNode,*BiTree;
BiTree creatB(){
BiTree T;
char c;
scanf("%c",&c);
if(c=='#') T=NULL;
else{
T=(BiTree)malloc(sizeof(BiNode));
T->data=c;
T->lchild=creatB();
T->rchild=creatB();
}
return T;
}
void visit(BiTree T){
if(T!=NULL)
printf("%c",T->data);
}
void visitX(BiTree T){
if(T!=NULL){
visit(T);
visitX(T->lchild);
visitX(T->rchild);
}
}
void visitZ(BiTree T){
if(T!=NULL){
visitZ(T->lchild);
visit(T);
visitZ(T->rchild);
}
}
void visitH(BiTree T){
if(T!=NULL){
visitH(T->lchild);
visitH(T->rchild);
visit(T);
}
}
int getDepth(BiTree T){
if(T==NULL) return 0;
int m=getDepth(T->lchild);
int n=getDepth(T->rchild);
if(m>n) return m+1;
else return n+1;
}
int getLeaf(BiTree T){
int i=0;
if(T!=NULL){
if((T->lchild==NULL)&&(T->rchild==NULL))
i++;
i+=getLeaf(T->lchild);
i+=getLeaf(T->rchild);
}
return i;
}
int main(){
BiTree T;
T=creatB();
printf("PreOrder:");
visitX(T);
printf("\n");
printf("InOrder:");
visitZ(T);
printf("\n");
printf("PostOrder:");
visitH(T);
printf("\n");
printf("Depth:%d\n",getDepth(T));
printf("Leaf:%d",getLeaf(T));
return 0;
}
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。