数据结构-二叉树四种遍历实现

头文件Queue.h(为实现层次遍历)

#include
#include
#include
#include
struct BinTreeNode;
typedef BinTreeNode*  EType;
typedef struct QueueNode {
	BinTreeNode* data;
	struct QueueNode *next;
}QueueNode;
typedef struct LinkQueue {
	QueueNode *front;
	QueueNode *tail;
}LinkQueue;

void InitQueue(LinkQueue *Q);
void EnQueue(LinkQueue *Q, EType x);
void DeQueue(LinkQueue *Q);
bool IsEmptyQueue(LinkQueue *Q);
void ShowQueue(LinkQueue *Q);
void GetHead(LinkQueue *Q, EType *v);
int Length(LinkQueue *Q);
void Clear(LinkQueue *Q);
void Destroy(LinkQueue *Q);

void InitQueue(LinkQueue *Q) {
	QueueNode *s = (QueueNode*)malloc(sizeof(QueueNode));
	assert(s != NULL);
	Q->front = Q->tail = s;
	Q->tail->next = NULL;
}

bool IsEmptyQueue(LinkQueue *Q) {
	return Q->front == Q->tail;
}

void EnQueue(LinkQueue *Q, EType x) {
	QueueNode *s = (QueueNode*)malloc(sizeof(QueueNode));
	assert(s != NULL);
	s->data = x;
	s->next = NULL;
	Q->tail->next = s;
	Q->tail = s;
}

void DeQueue(LinkQueue *Q) {
	if (Q->front == Q->tail)
		return;
	QueueNode *p = Q->front->next;
	Q->front->next = p->next;
	free(p);
	if (p == Q->tail)
		Q->tail = Q->front;
}

void ShowQueue(LinkQueue *Q) {
	QueueNode *p = Q->front->next;
	printf("Front:>");
	while (p != NULL) {
		printf("%d ", p->data);
		p = p->next;
	}
	printf("<:Tail");
}

void GetHead(LinkQueue *Q, EType *v) {
	if (Q->front == Q->tail)
		return;
	QueueNode *p = Q->front->next;
	*v = p->data;
}

int Length(LinkQueue *Q) {
	int len = 0;
	QueueNode *p = Q->front->next;
	while (p != NULL) {
		len++;
		p = p->next;
	}
	return len;
}

void Clear(LinkQueue *Q) {
	QueueNode *p = Q->front->next;
	if (Q->front == Q->tail)
		return;
	while (p != NULL) {
		Q->front->next = p->next;
		free(p);
		p = Q->front->next;
	}
	Q->tail = Q->front;
}

void Destroy(LinkQueue *Q) {
	Clear(Q);
	free(Q->front);
	Q->front = Q->tail = NULL;
}

头文件BinTree.h

#include
#include
#include

typedef  char  ElemType;
typedef struct BinTreeNode 
{
	//二叉树结点类型
	ElemType data;
	struct BinTreeNode *lchild;
	struct 	BinTreeNode *rchild;
}BinTreeNode;
typedef struct BinTree {
	//二叉树类型
	BinTreeNode *root;
	ElemType refvalue;//停止的标志
}BinTree;

InitBinTree(BinTree *bt, ElemType ref);
void CreateBinTree_1(BinTree *bt);
BinTreeNode * CreateBinTree_2(BinTree *bt);
void PreOrder(BinTree* bt);
void PreOrder_1(BinTreeNode* t);
void InOrder(BinTree* bt);
void InOrder_1(BinTreeNode* t);
void PostOrder(BinTree* bt);
void PostOrder_1(BinTreeNode* t);
void LevelOrder(BinTree* bt);
void LevelOrder_1(BinTreeNode* t);

函数实现BinTree.c

#include"BinTree.h"
#include"Queue.h"
InitBinTree(BinTree *bt, ElemType ref) {
	bt->refvalue = ref;
	bt->root = NULL;
}
void CreateBinTree_1(BinTree *bt) {
	bt->root = CreateBinTree_2(bt);
}
BinTreeNode *CreateBinTree_2(BinTree *bt) {
	ElemType Item;
	scanf_s("%c", &Item);//输入二叉树的节点值
	if (Item == bt->refvalue)
		return NULL;
	else
	{
		BinTreeNode *t = (BinTreeNode*)malloc(sizeof(BinTreeNode));
		assert(t != NULL);
		t->data = Item;
		t->lchild = CreateBinTree_2(bt);
		t->rchild = CreateBinTree_2(bt);
		return t;
	}
}

void PreOrder(BinTree* bt) {
	PreOrder_1(bt->root);
}
void PreOrder_1(BinTreeNode*t) {
	if (t!= NULL) {
		printf("%c ",t->data);//先序遍历结果
		PreOrder_1(t->lchild);
		PreOrder_1(t->rchild);
	}
}

void InOrder(BinTree* bt) {
	InOrder_1(bt->root);
}
void InOrder_1(BinTreeNode*t) {
	if (t != NULL) {
		InOrder_1(t->lchild);
		printf("%c ", t->data);//中序遍历结果
		InOrder_1(t->rchild);
	}
}

void PostOrder(BinTree* bt) {
	PostOrder_1(bt->root);
}
void PostOrder_1(BinTreeNode*t) {
	if (t != NULL) {
		PostOrder_1(t->lchild);
		PostOrder_1(t->rchild);
		printf("%c ", t->data);//后序遍历结果
	}
}

void LevelOrder(BinTree* bt) {
	LevelOrder_1(bt->root);
}
void LevelOrder_1(BinTreeNode* t) {
	BinTreeNode*v;
	if (t != NULL) {
		LinkQueue Q;
		InitQueue(&Q);
		EnQueue(&Q,t);//层次遍历入队的是结点的地址
		while (!IsEmptyQueue(&Q)) {
			GetHead(&Q, &v);
			DeQueue(&Q);
			printf("%c ", v->data);
			if (v->lchild != NULL)
				EnQueue(&Q, v->lchild);
			if (v->rchild != NULL)
				EnQueue(&Q, v->rchild);
		}

	}
}

测试函数Main.c

#include"BinTree.h"
int main() {
	BinTree mytree;
	InitBinTree(&mytree, '#');
	CreateBinTree_1(&mytree);
	printf("先序遍历序列:n");
	PreOrder(&mytree);
	printf("n");
	printf("中序遍历序列:n");
	InOrder(&mytree);
	printf("n");
	printf("后序遍历序列:n");
	PostOrder(&mytree);
	printf("n");
	printf("层次遍历序列:n");
	LevelOrder(&mytree);
	printf("n");
	
	
}