二叉树，前中后遍历，层遍历-白红宇

二叉树，前中后遍历，层遍历

阅读量：3525 次

发布时间：2019-05-20

本文共 2499 字，大约阅读时间需要 8 分钟。

data.h

#include 
   
    #include 
    
     #include 
     
      #ifndef _DATA_H_#define _DATA_H_typedef struct bitnode{	int data;	struct bitnode *lchild, *rchild;}bitnode, *bitree;#endif

create.c

#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"#include 
   
    typedef 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);  }

main.c

#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/

你可能感兴趣的文章

Java基础入门 StringBuffer类

查看>>

Java基础入门 currentTimeMillis方法

查看>>