建立二叉树与层次遍历二叉树程序.doc

#include /*I/O函数*/#include conio.h#include stdlib.h#define QUEUESIZE 100 /*队列初始容量*/#define TRUE 1#define FALSE !TRUE#define Statu int#define BitTreeElementType int#define SHUJU %d#define END -1typedef struct Bitnode/*树的链式存储*/BitTreeElementType data;struct Bitnode *lchild;/*左孩子 */struct Bitnode *rchild;/*右孩子*/BTnode,*BitTree;typedef BitTree QueueElemtype;typedef struct/*定义数据结构*/QueueElemtype dataQUEUESIZE;int front;/*队列的头指针*/int rear;/*队列的尾指针*/queue;int CreateQueue(queue *q);/*创建队列*/int EnQueue(queue *q, QueueElemtype c);/*向队尾插入元素c*/Statu DeQueue(queue *q, QueueElemtype *reb);/*队头元素出队用reb返回其值*/Statu CreateBitTree(BitTree *T);/*初始化二叉树*/Statu LayerTravelBitTree(BitTree T);/*层次遍历二叉树*/Statu VisitData(BitTreeElementType data);void main()BitTree t;printf(Input data to create bittree and );printf(SHUJU,END);printf( will make null tree.n);/*输入根结点 */CreateBitTree(&t);/*初始化二叉树*/printf(Layer order travel the tree:n);/*层次遍历二叉树*/LayerTravelBitTree(t);/*层次遍历二叉树*/Statu CreateBitTree(BitTree *T)/*初始化二叉树*/BitTreeElementType inputdata;*T = (BitTree )malloc(sizeof(BTnode);printf(Enter Data:);/*输入数据*/fflush(stdin);scanf(SHUJU,&inputdata);if ( inputdata = END) T = NULL; return FALSE;else(*T)-data = inputdata;/*将输入的数据存入结点*/ printf(Create left sub tree.lchild);/*递归循环输入左子树*/ printf(Create right sub tree.rchild);/*递归循环输入右子树*/ return TRUE;Statu LayerTravelBitTree(BitTree T)/*层次遍历二叉树*/queue tq;/*队列tq*/QueueElemtype res;/*用来返回对头元素*/CreateQueue(&tq);/*创建队列*/EnQueue(&tq,T);/*将T插入队尾*/while ( DeQueue(&tq,&res) = TRUE)/*当队头元素不空时执行while循环*/if (res) ;/*访问队头元素*/ if(res-lchild-data != -1) EnQueue(&tq,res-lchild); /*将结点左孩子插入队尾*/VisitData(res-data); if(res-rchild-data != -1) EnQueue(&tq,res-rchild);/*将结点右孩子插入队尾*/ return TRUE;int CreateQueue(queue *q)q-front = -1;q-rear = -1;return TRUE;int EnQueue(queue *q, QueueElemtype c)/*将元素c插入队尾*/q-rear+;/*尾指针加1*/if (q-rear = QUEUESIZE)/*若尾指针超出队列长度则提示错误*/ printf(Queue overflow!n); exit(0);q-dataq-rear = c;return 1;Statu DeQueue(queue *q, QueueElemtype *ret)/*队头元素出队并用ret返回其值*/if (q-front = q-rear)/*若队列为空，则返回错误提示*/ return FALSE;q-front+;/*头指针加1*/*ret