/*调试环境VS2008、VC++6.0*//*关于二叉树的一些操作，包括二叉树的建立，输出，遍历*//*判断是否为完全二叉树，求二叉树的层数，求叶子结点数*/#include#include#include#defineMAX(x,y)(x)>(y)?(x):(y)typedefstructBiTNode{intdata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;BiTreeCreateBiTree(BiTreeT){//按先序次序输入二叉树中结点的值(int类型)//构造二叉链表表示的二叉树T，结点值为int型，表示空（子）树intnum;scanf("%d",&num);if(0==num)//空T=NULL;else{T=(BiTree)malloc(sizeof(BiTNode));if(!T)exit(0);T->data=num;//生成根结点printf("请输入结点%d的左子结点:",T->data);T->lchild=CreateBiTree(T->lchild);//构造左子树printf("请输入结点%d的右子结点:",T->data);T->rchild=CreateBiTree(T->rchild);//构造右子树}returnT;}voidPrintBiTree(BiTreeT){//先序遍历输出二叉树，其中NULL表示空结点//输出其嵌套括号表示格，即形如A(T1,T2)，其中A为根结点，T1，T2分别为A的左子树和右子树if(T!=NULL){printf("%d",T->data);//若结点非空，输出结点的值if(T->lchild!=NULL||T->rchild!=NULL){printf("(");PrintBiTree(T->lchild);//判断左子树，非空则输出根结点的值printf(",");if(T->rchild!=NULL)PrintBiTree(T->rchild);//判断右子树，非空则输出根结点的值elseprintf("NULL");printf(")");}}elseprintf("NULL");}intFullBiTree(BiTreeT){//判断二叉树是否为完全二叉树，完全二叉树需满足两个条件//一是某结点缺失左或右孩子，则其后续结点均无孩子结点//二是某结点无左孩子，则一定无右孩子//需按层次遍历二叉树，故设一队列，用queue表示该队列//用bj表示是否所以结点均有左孩子和右孩子，若是bj=1,否则bj=0BiTreequeue[50],p;intfirst=0,rear=0,cm=1,bj=1;if(T!=NULL){queue[++rear]=T;//根结点入队while(first!=rear){p=queue[++first];//p按入队先后顺序依次指向队列中的结点if(p->lchild==NULL){bj=0;//p的左孩子为空，bj=0if(p->rchild!=NULL){//p的左孩子为空，右孩子却不为空，不可能是完全二叉树了`cm=0;break;}}else{cm=bj;if(!cm)break;queue[++rear]=p->lchild;//p的左孩子不为空，入队if(p->rchild==NULL)//p的左孩子非空，右孩子空，则其左孩子必须无后续结点bj=0;//否则不可能为完全二叉树elsequeue[++rear]=p->rchild;//p的右孩子非空，入队}}returncm;}return1;}voidpreorder(BiTreeT){//先序遍历二叉树并输出if(T!=NULL){printf("%d",T->data);preorder(T->lchild);preorder(T->rchild);}}voidinorder(BiTreeT){//中序遍历二叉树并输出if(T!=NULL){preorder(T->lchild);printf("%d",T->data);preorder(T->rchild);}}voidpostorder(BiTreeT){//后序遍历二叉树并输出if(T!=NULL){preorder(T->lchild);preorder(T->rchild);printf("%d",T->data);}}voidlayorder(BiTreeT){//按层次遍历二叉树，利用队列先进先出性质即可inthead=0,tail=0;BiTreequeue[50],p;p=T;if(p!=NULL)queue[tail++]=p;while(head!=tail){if(p->lchild!=NULL)queue[tail++]=p->lchild;if(p->rchild!=NULL)queue[tail++]=p->rchild;printf("%d",p->data);p=queue[++head];}}intleaf_num(BiTreeT){//计算叶子结点数，并输出叶子结点//f(T)=0,如果T=NULL//f(T)=1,如果T->lchild=T->rchild=NULL//f(T)=f(T->lchild)+f(T->rchild),其他情况intnum1,num2;if(T==NULL)return0;elseif(T->lchild==NULL&&T->rchild==NULL){printf("结点%d",T->data);return1;}else{num1=leaf_num(T->lchild);num2=leaf_num(T->rchild);return(num1+num2);}}intlayer_num(BiTreeT){//f(T)=0,如果T=NULL//f(T)=1,如果T->lchild=T->rchild=NULL//f(T)=max{f(T->lchild)+1,f(T->rchild)+1},其他情况intnum1,num2;if(T==NULL)return0;elseif(T->lchild==NULL&&T->rchild==NULL)return1;else{num1=layer_num(T->lchild)+1;num2=layer_num(T->rchild)+1;returnMAX(num1,num2);}}intmain(void){intk;BiTreeT=NULL;printf("\n建立二叉树\n请输入树的根结点：");T=CreateBiTree(T);printf("\n输出二叉树：\n");PrintBiTree(T);if(FullBiTree(T))printf("\n\n这是一棵完全二叉树");elseprintf("\n\n这不是一棵完全二叉树");printf("\n\n先序遍历二叉树：");preorder(T);printf("\n\n中序遍历二叉树：");inorder(T);printf("\n\n后序遍历二叉树：");postorder(T);printf("\n\n按层次遍历二叉树：");layorder(T);printf("\n\n二叉树的叶子结点为：");k=leaf_num(T);printf("，共%d个",k);printf("\n\n二叉树的层数为：%d层\n\n",layer_num(T));return0;}以图1所示的二叉树为例，程序的运行结果如图2、图3所示图1图2图3
