博客

二叉树的先序遍历，中序遍历和后序遍历采用的都是

函数递归

的思想

BinaryTree.h文件

完全二叉树的相关函数

注：实现

层序遍历

的方法使用到了

队列

的思想——定义

链式队列

将树的结点作为数据入队，然后再循环出队，打印出的出队顺序就是树的层序遍历顺序。

实现层序遍历的链式队列结构体定义

将链式队列的数据类型定义为操作二叉树结点的指针类型(地址传递)

typedef struct BinaryTreeNode *LLNDataType;

（使用到了链式队列的三个函数:队列初始化，入队和出队）

typedef struct BinaryTreeNode * LLNDataType;
typedef struct LinkListNode
{
    LLNDataType data;
    struct LinkListNode *next;
} LLN, *LL;

typedef struct LinkQueue
{
    LL front;
    LL rear;
} LQ;

#ifndef _BINARYTREE_H_
#define _BINARYTREE_H_

#include<stdio.h>
#include<stdlib.h>

typedef struct BinaryTreeNode
{
    int data;
    struct BinaryTreeNode *Lchild;
    struct BinaryTreeNode *Rchild;
} BTN, *BT;
typedef struct BinaryTreeNode * LLNDataType;
typedef struct LinkListNode
{
    LLNDataType data;
    struct LinkListNode *next;
} LLN, *LL;

typedef struct LinkQueue
{
    LL front;
    LL rear;
} LQ;

BT BTInit(int n, int i);
void PreOrder(BT root);
void InOrder(BT root);
void PostOrder(BT root);
int LQInQueue(LQ *PQ, LLNDataType data);
LLNDataType LQOutQueue(LQ *PQ);
LQ *LQInit();
void LevelOrder(BT root);
#endif

BinaryTree.c文件

#include"BinaryTree.h"

BT BTInit(int n, int i)
{
    BT root = (BT)malloc(sizeof(BTN));
    if (NULL == root)
    {
        printf("BTInit failed, root malloc err.\n");
        return NULL;
    }
    root->data = i;
    if (2 * i <= n)
        root->Lchild = BTInit(n, 2 * i);
    else
        root->Lchild = NULL;
    if (2 * i + 1 <= n)
        root->Rchild = BTInit(n, 2 * i + 1);
    else
        root->Rchild = NULL;
    return root;
}

void PreOrder(BT root)
{
    if (NULL == root)
    {
        return;
    }
    printf("%d ", root->data);
    if (root->Lchild)
        PreOrder(root->Lchild);
    if (root->Rchild)
        PreOrder(root->Rchild);
}

void InOrder(BT root)
{
    if (NULL == root)
    {
        return;
    }
    if (root->Lchild)
        InOrder(root->Lchild);
    printf("%d ", root->data);
    if (root->Rchild)
        InOrder(root->Rchild);
}

void PostOrder(BT root)
{
    if (NULL == root)
    {
        return;
    }

    if (root->Lchild)
        PostOrder(root->Lchild);
    if (root->Rchild)
        PostOrder(root->Rchild);
    printf("%d ", root->data);
}

int LQInQueue(LQ *PQ, LLNDataType data)
{
    LL PNew = (LL)malloc(sizeof(LLN));
    if (NULL == PNew)
    {
        printf("LQInQueue failed, PNew malloc err.\n");
        return -1;
    }
    PNew->data = data;
    PNew->next = NULL;
    PQ->rear->next = PNew;
    PQ->rear = PNew;
    return 0;
}

LLNDataType LQOutQueue(LQ *PQ)
{

    if (PQ->front == PQ->rear)
    {
        printf("LQOutQueue failed, LQ is empty.\n");
        return NULL;
    }
    LL PDel = PQ->front;
    PQ->front = PQ->front->next;
    free(PDel);
    PDel = NULL;
    return PQ->front->data;
}

LQ *LQInit()
{
    LQ *PQ = (LQ *)malloc(sizeof(LQ));
    if (NULL == PQ)
    {
        printf("LQInit failed, PQ malloc err.\n");
        return NULL;
    }
    PQ->front = PQ->rear = (LL)malloc(sizeof(LLN));
    if (NULL == PQ->front)
    {
        printf("LQInit failed, PQ->front or PQ->rear malloc err.\n");
        return NULL;
    }
    PQ->front->next = NULL;
    return PQ;
}

void LevelOrder(BT root)
{
    LQ *PQ = LQInit();
    if(root)
        LQInQueue(PQ,root);
    while(PQ->front != PQ->rear)
    {
        root = LQOutQueue(PQ);
        printf("%d ",root->data);
        if(root->Lchild)
            LQInQueue(PQ,root->Lchild);
        if(root->Rchild)
            LQInQueue(PQ,root->Rchild);
    }
}

test.c文件(主函数)

#include"BinaryTree.h"

int main(int argc, char const *argv[])
{
    BT root = BTInit(13, 1);
    printf("先序遍历：");
    PreOrder(root);
    putchar(10);
    printf("中序遍历：");
    InOrder(root);
    putchar(10);
    printf("后序遍历：");
    PostOrder(root);
    putchar(10);
    printf("层序遍历：");
    LevelOrder(root);
    putchar(10);
    return 0;
}

运行结果

makefile文件

CC=gcc
OBJS=test.o BinaryTree.o
CFLAGS=-c -g -Wall
test:$(OBJS)
	$(CC) -o test $(OBJS)
%.o:%.c
	$(CC) $(CFLAGS) $< -o $@
.PHONY:clean
clean:
	$(RM) *.o test