测试序列：AB#CD###E#FGH##K###
一.链式队列头文件linkqueue.h
#ifndef __LINKQUEUE_H__
#define __LINKQUEUE_H__
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include"btree.h"
typedef btree_pnode datatype;
typedef struct linkqueuenode
{
datatype data;
struct linkqueuenode *next;
}linkqueue_node,*linkqueue_pnode;
//头尾节点封装
typedef struct linkqueue
{
linkqueue_pnode front,rear;
}link_queue,*link_pqueue;
extern void init_linkqueue(link_pqueue *Q);
extern bool is_full_linkqueue(link_pqueue q);
extern bool in_linkqueue(datatype data,link_pqueue q);
extern bool is_empty_linkqueue(link_pqueue q);
extern bool out_linkqueue(link_pqueue q,datatype *D);
//extern void show_linkqueue(link_pqueue q);
#endif
二.链式队列函数实现
#include"linkqueue.h"
void init_linkqueue(link_pqueue *Q)
{
//申请front rear 空间
*Q = (link_pqueue)malloc(sizeof(link_queue));
if(NULL == (*Q))
{
perror("malloc");
exit(-1);
}
//申请头结点
(*Q) -> front = (linkqueue_pnode)malloc(sizeof(linkqueue_node));
if(NULL == (*Q)->front)
{
perror("malloc");
exit(-1);
}
(*Q)->front->next = NULL;
(*Q)->rear = (*Q)->front;
}
bool in_linkqueue(datatype data,link_pqueue q)
{
linkqueue_pnode new;
new = (linkqueue_pnode)malloc(sizeof(linkqueue_node));
if(NULL == new)
{
printf("入队失败\n");
return false;
}
new -> data = data;
new -> next = q->rear->next;
q->rear->next = new;
q->rear = q->rear->next;
return true;
}
bool is_empty_linkqueue(link_pqueue q)
{
if(q->rear == q->front)
return true;
else
return false;
}
bool out_linkqueue(link_pqueue q,datatype *D)
{
linkqueue_pnode t;
if(is_empty_linkqueue(q))
{
printf("队列为空\n");
return false;
}
//队列非空 出队
t = q->front;
q->front = q->front->next;
*D = q->front->data;
free(t);
return true;
}
#if 0
void show_linkqueue(link_pqueue q)
{
linkqueue_pnode p;
for(p = q->front->next;p != NULL;p = p->next)
{
printf("%d\t",p->data);
}
puts("");
}
#endif
三.二叉树btree.h实现
#ifndef __BTREE_H__
#define __BTREE_H__
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
typedef char datatype_bt;
typedef struct btreenode
{
datatype_bt data;
struct btreenode *lchild,*rchild;
}btree_node,*btree_pnode;
extern void create_btree(btree_pnode *T);
extern void pre_order(btree_pnode t);
extern void mid_order(btree_pnode t);
extern void last_order(btree_pnode t);
extern void level_order(btree_pnode t);
#endif
四.二叉树函数实现btree.c
#include"btree.h"
#include"linkqueue.h"
void create_btree(btree_pnode *T)
{
datatype_bt ch;
scanf("%c",&ch);
if('#' == ch)
*T = NULL;
else
{
*T = (btree_pnode)malloc(sizeof(btree_node));
if(NULL == *T)
{
perror("malloc");
exit(1);
}
(*T)->data = ch;
create_btree(&(*T)->lchild);
create_btree(&(*T)->rchild);
}
}
//先序遍历
void pre_order(btree_pnode t)
{
if(t != NULL)
{
//访问根结点
printf("%c",t->data);
//先序遍历左子树
pre_order(t->lchild);
//先序遍历右子树
pre_order(t->rchild);
}
}
//中序遍历
void mid_order(btree_pnode t)
{
if(t != NULL)
{
//先序遍历左子树
mid_order(t->lchild);
printf("%c",t->data);
//先序遍历右子树
mid_order(t->rchild);
}
}
//后序遍历
void last_order(btree_pnode t)
{
if(t != NULL)
{
//先序遍历左子树
last_order(t->lchild);
printf("%c",t->data);
//先序遍历右子树
last_order(t->rchild);
}
}
//层次遍历
void level_order(btree_pnode t)
{
link_pqueue q;
init_linkqueue(&q); //初始化队列
while(t != NULL)
{
//访问结点
printf("%c",t->data);
//左指针不空则入队
if(t->lchild != NULL)
{
in_linkqueue(t->lchild,q);
}
if(t->rchild != NULL)
{
in_linkqueue(t->rchild,q);
}
//队列不为空则出队
if(!is_empty_linkqueue(q))
out_linkqueue(q,&t);
else
break;
}
}
五.测试程序包含main函数test.c
#include"btree.h"
int main()
{
btree_pnode t;
create_btree(&t);
printf("先序遍历 ");
pre_order(t);
puts("");
printf("中序遍历 ");
mid_order(t);
puts("");
printf("后序遍历 ");
last_order(t);
puts("");
printf("层次遍历 ");
level_order(t);
puts("");
return 0;
}
六.makefile
CC = gcc
CFLAGS = -Wall -g -O0
SRC = btree.c test.c linkqueue.c
OBJS = test
$(OBJS):$(SRC)
$(CC) $(CFLAGS) -o $@ $^
clean:
$(RM) $(OBJS) .*.sw?