数据结构 c语言实现 二叉树的层次遍历（linux下实现）

测试序列：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?