算法：数据结构二叉树的层次建树和前序、中序、后序、层序遍历

建立functio.h文件用于存放数据结构类型和函数定义声明

#ifndef TREE_FUNCTION_H
#define TREE_FUNCTION_H
#include <stdio.h>
#include <stdlib.h>

typedef char BiElemType;
typedef struct BiTNode{
    BiElemType c;//c 就是书籍上的 data
    struct BiTNode *lchild;
    struct BiTNode *rchild;
}BiTNode,*BiTree;

typedef struct tag{
    BiTree p;//树的某一个结点的地址值
    struct tag *pnext;
}tag_t,*ptag_t;


//队列的相关数据结构
typedef BiTree ElemType;
typedef struct LinkNode{
    ElemType data;
    struct LinkNode *next;
}LinkNode;

typedef struct{
    LinkNode *front,*rear;
}LinkQueue;
void InitQueue(LinkQueue &Q);
bool IsEmpty(LinkQueue Q);
void EnQueue(LinkQueue &Q,ElemType x);
bool DeQueue(LinkQueue &Q,ElemType &x);
#endif //TREE_FUNCTION_H

建立queue.cpp文件，二叉树的层序遍历需要用一个队列来辅助取数据

#include "function.h"
void InitQueue(LinkQueue &Q)
{
    Q.front=Q.rear=(LinkNode*)malloc(sizeof(LinkNode));//头和尾指向同一个结点
    Q.front->next=NULL;//头结点的 next 指针为 NULL
}

bool IsEmpty(LinkQueue Q)
{
    if(Q.front==Q.rear)
        return true;
    else
        return false;
}
//入队 ，尾部插入法
void EnQueue(LinkQueue &Q,ElemType x)
{
    LinkNode *s=(LinkNode *)malloc(sizeof(LinkNode));
    s->data=x;s->next=NULL;
    Q.rear->next=s;//rear 始终指向尾部
    Q.rear=s;
}
//出队   头部删除法
bool DeQueue(LinkQueue &Q,ElemType &x)
{
    if(Q.front==Q.rear) return false;//队列为空
    LinkNode *p=Q.front->next;//头结点什么都没存 ，所以头结点的下一个节点才有数据
    x=p->data;
    Q.front->next=p->next;//断链
    if(Q.rear==p)//删除的是最后一个元素
        Q.rear=Q.front;//队列置为空
    free(p);
    return true;
}

最后是main.cpp文件 

#include "function.h"
//递归实现
//abdhiejcfg   前序遍历 ，前序遍历就是深度优先遍历
void PreOrder(BiTree p)
{
    if(p!=NULL)
    {
        putchar(p->c);//等价于 visit 函数
        PreOrder(p->lchild);
        PreOrder(p->rchild);
    }
}
//中序遍历   hdibjeafcg
void InOrder(BiTree p)
{
    if(p!=NULL)
    {
        InOrder(p->lchild);
        putchar(p->c);
        InOrder(p->rchild);
    }
}
//hidjebfgca   后序遍历
void PostOrder(BiTree p)
{
    if(p!=NULL)
    {
        PostOrder(p->lchild);
        PostOrder(p->rchild);
        putchar(p->c);
    }
}
//层次遍历,层序遍历 ，广度优先遍历
void LevelOrder(BiTree T)
{
    LinkQueue Q;//辅助队列
    InitQueue(Q);//初始化队列
    BiTree p;
    EnQueue(Q,T);//树根入队
    while(!IsEmpty(Q))
    {
        DeQueue(Q,p);//出队当前结点并打印
        putchar(p->c);
        if(p->lchild!=NULL) //入队左孩子
            EnQueue(Q,p->lchild);
        if(p->rchild!=NULL)   //入队右孩子
            EnQueue(Q,p->rchild);
    }
}
//《王道 C 督学营》课程
//二叉树的建树（层次建树）
int main()
{
    BiTree pnew;//用来指向新申请的树结点
    char c;
    BiTree tree=NULL;//树根
//phead 就是队列头 ，ptail 就是队列尾
    ptag_t phead=NULL,ptail=NULL,listpnew=NULL,pcur=NULL;
//输入内容为 abcdefghij
    while(scanf("%c",&c))
    {
        if(c=='\n')
        {
            break;
        }
        pnew=(BiTree)calloc(1,sizeof(BiTNode));//calloc 申请空间并对空间进行初始化 ，赋值为 0
        pnew->c=c;//数据放进去
        listpnew=(ptag_t)calloc(1,sizeof(tag_t));//给队列结点申请空间
        listpnew->p=pnew;
        if(NULL==tree)
        {
            tree=pnew;//树的根
            phead=listpnew;//队列头
            ptail=listpnew;//队列尾
            pcur=listpnew;
            continue;
        }else{
            ptail->pnext=listpnew;//新结点放入链表 ，通过尾插法
            ptail=listpnew;//ptail 指向队列尾部
        }//pcur 始终指向要插入的结点的位置
        if(NULL==pcur->p->lchild)//如何把新结点放入树
        {
            pcur->p->lchild=pnew;//把新结点放到要插入结点的左边
        }else if(NULL==pcur->p->rchild)
        {
            pcur->p->rchild=pnew;//把新结点放到要插入结点的右边
            pcur=pcur->pnext;//左右都放了结点后 ，pcur 指向队列的下一个
        }
    }

    printf("--------qian----------\n");//也叫先序遍历 ，先打印当前结点 ，打印左孩子 ，打印右孩子
            PreOrder(tree);
    printf("\n--------zhong------------\n");//先打印左孩子 ，打印父亲 ，打印右孩子
    InOrder(tree);
    printf("\n--------hou------------\n");//先打印左孩子 ，打印右孩子 ，最后打印父亲
    PostOrder(tree);
    printf("\n--------ceng-----------\n");
    LevelOrder(tree);
    printf("\n");
    return 0;
}