我有一份文档，你自己看看//头文件#include "stdio.h"#include "conio.h"#include "stdlib.h"//预定义宏常量#define OK 1#define ERROR -1#define ENDFLAG'#'typedef char TelemType;typedef intstatus;//二叉树的存储结构typedef struct BiTNode{ TelemType data; struct BiTNode *lchild,*rchild;}BiTNode,*BiTree;//全局变量，表示叶子个数int m=0;//二叉树的创建statusCreateBiTree(BiTree *T){// 先序创建 TelemType ch; scanf("%c",&ch); if(ch==ENDFLAG) *T=NULL; else {if(!(*T=(BiTNode *)malloc(sizeof(BiTNode)))){ printf("\nOut of space.");
getch();
exit(0);}(*T)->data=ch; //生成根结点
CreateBiTree(&((*T)->lchild));//左子树
CreateBiTree(&((*T)->rchild));//右子树 } return OK;}//先序遍历status PreOrderTraverse(BiTree T){ if(T) {printf("%c",T->data);PreOrderTraverse(T->lchild);PreOrderTraverse(T->rchild); } return OK; }/*//中序status InOrderTraverse(BiTree T){ if(T) {InOrderTraverse(T->lchild);printf("%c",T->data);InOrderTraverse(T->rchild); } return OK; }//后序status PostOrderTraverse(BiTree T){ if(T) {PostOrderTraverse(T->lchild);PostOrderTraverse(T->rchild); printf("%c",T->data); } return OK; }*//* 用队列 层次遍历*///存储定义typedef char QElemType;//typedef int status;typedef struct Queue{QElemType data; struct Queue *next; }Queue;//头指针和尾指针typedef struct{ Queue*front;
Queue*rear; }LinkQueue; //初始化队列status InitQueue(LinkQueue *q){ q->front=q->rear =NULL; //----无头结点return OK;}/*判断队列是否为空*/ status QueueEmpty(LinkQueue *Q) {
return (Q->front==NULL)&&(Q->rear==NULL); /*实际上只须判断队头指针是否为空即可*/ } //入队void EnQueue(LinkQueue *q,QElemType e){ Queue *p;
p=(Queue *)malloc(sizeof(Queue));/*申请新结点*/p->data=e;p->next=NULL; if(QueueEmpty(q))q->front=q->rear=p; else {/*x插入非空队列的尾*/ q->rear->next=p;/*p链到原队尾结点后*/
q->rear=p;/*队尾指针指向新的尾*/}}//出队QElemType DeQueue(LinkQueue *q){
Queue *p; QElemType e;
if(QueueEmpty(q))
{
printf("Queue underflow\n");/*下溢*/
exit(1) ;
}p=q->front;/*指向对头结点*/e=p->data;/*保存对头结点的数据*/q->front=p->next;/*将对头结点从链上摘下*/ if(q->rear==p)/*原队中只有一个结点，删去后队列变空，此时队头指针已为空*/ q->rear=NULL;
free(p);/*释放被删队头结点*/return e;/*返回原队头数据*/}/*层次遍历思想 递归a.根结点入队列b.原队左子树的左右孩子（非空）入队列c.原队右子数的左右孩子（非空）入队列*///层次遍历入队列status Arrange(BiTree T,LinkQueue *Q){ if(T) {EnQueue(Q,T->data);Arrange(T->lchild,Q);Arrange(T->rchild,Q); } return OK;}//从队列中输出各元素status ArrangementTraverse(BiTree T){ char e;
LinkQueue Q;
InitQueue(&Q); if(T) {
Arrange(T,&Q);//递归调用while(!QueueEmpty(&Q)){ e=DeQueue(&Q);
printf("%c",e);
} } return OK;}//求二叉树的叶结点个数status NumberLeaves(BiTree T){//先序遍历得到叶结点的数目 //m=0; if(T) {if(T->lchild==NULL&&T->rchild==NULL) m++;
NumberLeaves(T->lchild);
NumberLeaves(T->rchild); }return OK;}//一个比较函数status Max(int m, int n) {
if (m > n)
return m;
else
return n; } //获取二叉树的高度status HighBitree(BiTree t){ if (t == NULL)
return 0;
else
return 1 + Max(HighBitree(t->lchild), HighBitree(t->rchild)); }//主函数void main(){ BiTree T; printf("请创建二叉树：\n"); CreateBiTree(&T);
NumberLeaves(T); printf("叶节点个数为："); printf("%d",m);
printf("\n二叉树的高度为:");
printf("%d",HighBitree(T));
printf("\n先序遍历:\n");
PreOrderTraverse(T); /* printf("\n中序遍历:\n"); InOrderTraverse(T); printf("\n后序遍历:\n"); PostOrderTraverse(T);*/printf("\n层次遍历\n"); ArrangementTraverse(T);
printf("\n");} |
