[数据结构与算法]二叉树的前序递归建立及其四种遍历方式（层序遍历完全手写树结点的链表和链式队列）

二叉树的前序递归建立，及其四种遍历方式（层序遍历完全手写树结点的链表和链式队列，没用stl里的queue）代码很规范

#include<iostream>
using namespace std;


struct ElemType
{
    int value;
};
typedef struct BiTNode
{
    ElemType data;
    struct BiTNode *lchild,*rchild;
    
}BiTNode,*BiTree;

//链式队列结点
typedef struct LinkNode
{
    BiTNode *b;             //存的是指针不是结点
    struct LinkNode *next;
}LinkNode;

typedef struct{
    LinkNode *front;
    LinkNode *rear;
}LinkQueue;


//按先序顺序输入二叉树的值
void CreateBiTree(BiTree &T,char a[],int &i){
    if(a[i]=='#'){
        T=NULL;
    }
    else{
        T=(BiTNode*)malloc(sizeof(BiTNode));
        T->data.value=a[i];
        
        CreateBiTree(T->lchild,a,++i);
        CreateBiTree(T->rchild,a,++i);
    }
    
}
void visit(BiTNode* &N){
    cout<<N->data.value<<" ";
}

//树的前序遍历
void PreOrder(BiTree T){
    if(T!=NULL){
        visit(T);
        PreOrder(T->lchild);
        PreOrder(T->rchild);
    }
}

//树的中续遍历
void InOrder(BiTree T){
    if(T!=NULL){
        PreOrder(T->lchild);
        visit(T);
        PreOrder(T->rchild);
    }
}
void PostOrder(BiTree T){
    if(T!=NULL){
        PreOrder(T->lchild);
        PreOrder(T->rchild);
        visit(T);
    }
}
//初始化辅助队列
void InitQueue(LinkQueue &Q){
    Q.front=Q.rear=(LinkNode*)malloc(sizeof(LinkNode));
    Q.front->next=NULL;
}
//入队操作
void EnQueue(LinkQueue &Q,BiTree x){
    LinkNode *p=(LinkNode *)malloc(sizeof(LinkNode));
    p->b=x;
    p->next=NULL;
    Q.rear->next=p;
    Q.rear=p;
}
//出队操作
bool DeQueue(LinkQueue &Q,BiTree &x){
    if(Q.front==Q.rear)
        return false;
    LinkNode *p=(LinkNode*)malloc(sizeof(LinkNode));
    p=Q.front->next;
    x=p->b;
    Q.front->next=p->next;
    if(Q.rear==p)
        Q.rear=Q.front;
    free(p);
    return true;
}

//判空操作
bool IsEmpty(LinkQueue Q){
    if(Q.front==Q.rear)
        return true;
    else
        return false;
}

//层序遍历
void levelOrder(BiTree T){
    LinkQueue Q;
    InitQueue(Q);
    BiTree p;
    EnQueue(Q,T);
    while(!IsEmpty(Q)){
        DeQueue(Q,p);
        visit(p);
        if(p->lchild!=NULL)
            EnQueue(Q,p->lchild);
        if(p->rchild!=NULL)
            EnQueue(Q,p->rchild);
    }
}


int main(){
    char a[]={4, 1, 0, '#', '#', 2, '#', 3, '#', '#', 7, 5, '#', 6, '#', '#', 8, '#', 9, '#', '#'};
    int i=0;
    BiTree T;
    CreateBiTree(T,a,i);
    cout<<"树的前序遍历为"<<endl;
    PreOrder(T);
    cout<<endl;
    cout<<"树的中序遍历为"<<endl;
    InOrder(T);
    cout<<endl;
    cout<<"树的后序遍历为"<<endl;
    PostOrder(T);
    cout<<endl;
    cout<<"树的层序遍历为"<<endl;
    levelOrder(T);

    system("pause");
    return 0;
}