本文共 2499 字,大约阅读时间需要 8 分钟。
data.h
#includecreate.c#include #include #ifndef _DATA_H_#define _DATA_H_typedef struct bitnode{ int data; struct bitnode *lchild, *rchild;}bitnode, *bitree;#endif
#include "data.h"bitree create(bitree t){ int data; printf("Input data:"); scanf("%d",&data); if (data == 0) return NULL; else { t = (bitree)malloc(sizeof(bitnode)); t->data = data; t->lchild = create(t->lchild); t->rchild = create(t->rchild); } return t;}order.c
#include "data.h"void preorder(bitree t){ if (t) { printf("%d ",t->data); preorder(t->lchild); preorder(t->rchild); }}void midorder(bitree t){ if (t) { midorder(t->lchild); printf("%d ",t->data); midorder(t->rchild); }}void postorder(bitree t){ if (t) { postorder(t->lchild); postorder(t->rchild); printf("%d ",t->data); }}layerorder.c
#include "data.h"#includemain.ctypedef struct _QNode{ bitree data; struct _QNode* next;}QNode;typedef struct _queue{ QNode* front; QNode* rear;}Queue;/* 初始化队列 */void InitQueue(Queue* q){ q->front = q->rear = (QNode*)malloc(sizeof(QNode)); q->front->next = NULL;}/* 判断队列是否为空 */int isQueueEmpty(Queue* q){ /* 是空 */ if(q->front == q->rear) return 1; else return 0;}/* 入队列 */void EnQueue(Queue* q, bitree data){ QNode* pNode; pNode = (QNode*)malloc(sizeof(QNode)); pNode->data = data; pNode->next = NULL; q->rear->next = pNode; q->rear = pNode;}/* 出队列 */bitree DeQueue(Queue* q){ QNode* pNode; bitree pData; pNode = q->front->next; q->front->next = pNode->next; if(q->rear == pNode) q->rear = q->front; pData = pNode->data; free(pNode); return pData;}/* 销毁队列 */void DestroyQueue(Queue* q){ while(NULL != q->front) { q->rear = q->front->next; free(q->front); q->front = q->rear; }}/* 二叉树的层次遍历,使用队列实现 */void LayerOrderTraverse(bitree T){ Queue q; if(NULL == T) return; /* 1.创建一个队列 */ InitQueue(&q); /* 2.将树或者子树的根节点放入队列 */ EnQueue(&q,T); /* 重复步骤3至步骤5,直至队列为空 */ while(!isQueueEmpty(&q)) { /* 3.如果队列非空,则取出一个元素访问 */ T = DeQueue(&q); printf("%d ",T->data); /* 4. 如果该元素左子树非空,则放入队列 */ if(T->lchild) EnQueue(&q,T->lchild); /* 5. 如果该元素右子树非空,则放入队列 */ if(T->rchild) EnQueue(&q,T->rchild); } DestroyQueue(&q); }
#include "data.h"extern bitree create(bitree t);extern void preorder(bitree t);extern void midorder(bitree t);extern void postorder(bitree t);extern void LayerOrderTraverse(bitree T);int main(){ bitree t; t = create(t); preorder(t); printf("\n"); midorder(t); printf("\n"); postorder(t); printf("\n"); LayerOrderTraverse(t); printf("\n"); return 0;}
转载地址:http://uauhj.baihongyu.com/