[C++知识库]实现二叉树先序、中序、后序，层次遍历代码（C语言）

???????? 快期考了，大家数据结构复习的怎么样了呢，这里我复习了一下二叉树的先序、中序、后序，层次遍历，合上书自己挑战了下能不能Coding出来，结果发现自己不太记得各种遍历的函数名字了（悲），其他方面都还余裕。各位不妨挑战一下自己能不能码出来吧，下面的代码我只测试了一组例子，仅供参考，代码里的备注已经很详细了，这里我就不在做补充了。

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAXSIZE 32

//二叉树
typedef struct TreeNode{
    int data;
    struct TreeNode *Lchild;
    struct TreeNode *Rchild;
}Tree;

//循环队列
typedef struct {
    Tree* queue[MAXSIZE];
    int front;
    int rear;
}Queue;

//初始化树并给节点赋值
Tree *InitTree(int data){
    Tree *t;
    t = (Tree*)malloc(sizeof(Tree));
    t->data = data;
    t->Lchild = NULL;
    t->Rchild = NULL;
    return t;
}

//初始化循环队列
Queue *InitQueue(){
    Queue *q;
    q = (Queue*)malloc(sizeof(Queue));
    q->front = 0;
    q->rear = 0;
    return q;
}

//判断队列是否满
bool QueueStatusFull(Queue *q){
    if((q->front + 1) % MAXSIZE == q->rear)
        return 1;
    return 0;
}

//判断队列是否空
bool QueueStatusEmpty(Queue *q){
    if(q->front == q->rear)
        return 1;
    return 0;
}

//入队列
bool PushQueue(Queue *q, Tree *t){
    //若队列不为满
    if (QueueStatusFull(q)){
        printf("Push Queue Error : Full Queue\n");
        return 0;
    }
    //若树结点不为空
    if (t){
        q->queue[q->front++] = t;
        return 1;
    }
    //此时树节点为NULL,无法入队，但也不算错误情况
    return 0;
}

//出队列
Tree *PopQueue(Queue *q){
    //若队列不为空
    if (QueueStatusEmpty(q)){
        printf("Pop Queue Error : Empty Queue\n");
        return NULL;
    }
    return q->queue[q->rear++];
}

//插入叶子节点
bool GiveBirth(Tree *t, int Row, int No, int data){
    //大前提判断，传参是否正确
    if(Row < 1 || No < 1){
        printf("GiveBirth Error : Wrong Row or No\n");
        return 0;
    }
    int i;
    //定义一个Bool类型的数组存放路径信息
    bool Path[Row];
    //根据编号提取路径信息
    for(i = Row - 1;i >= 0; --i){
        Path[i] = (No + 1) % 2;
        No = (No + 1) / 2;
    }
    for(i = 0; i < Row  - 1; ++i){
        if (!Path[i]){
            //若往左
            //若左孩子为空，则无法继续索引，GiveBirth失败
            if(t->Lchild == NULL){
                printf("GiveBirth Error On Row:%d Empty LeftChild\n",i);
                return 0;
            }
            t = t->Lchild;
            continue;
        }
        //若往右
        //若右孩子为空，则无法继续索引，GiveBirth失败
        if(t->Rchild == NULL){
            printf("GiveBirth Error On Row:%d Empty RightChild\n",i);
            return 0;
        }
        t = t->Rchild;
    }
    //若成功索引到了正确的位置，但索引到了的位置已经被占用，GiveBirth失败
    if((!Path[Row - 1] && t->Lchild != NULL) || (Path[Row - 1] && t->Rchild != NULL)){
        printf("GiveBirth Error : Space Occupied\n");
        return 0;
    }
    //否则即成功GiveBirth
    Tree *NewChild = InitTree(data);
    if(!Path[Row - 1]){
        t->Lchild = NewChild;
    }else{
        t->Rchild = NewChild;
    }
    printf("GiveBirth Success\n");
    return 1;
}

//先序遍历树
void PreOrder(Tree *t){
    if(t){
        printf("%d ",t->data);
        PreOrder(t->Lchild);
        PreOrder(t->Rchild);
    }
}

//中序遍历树
void InOrder(Tree *t){
    if(t){
        PreOrder(t->Lchild);
        printf("%d ",t->data);
        PreOrder(t->Rchild);
    }
}

//后序遍历树
void PostOrder(Tree *t){
    if(t){
        PreOrder(t->Lchild);
        PreOrder(t->Rchild);
        printf("%d ",t->data);
    }
}

//打印树
void PrintTree(Tree *t, int status){
    if (!status)
        PreOrder(t);
    if (status == 1)
        InOrder(t);
    if (status == 2)
        PostOrder(t);
    printf("\n");
}

//层序遍历树(目前最多支持5行的满二叉树，可以通过修改MAXSIZE实现更高行的支持)
void LayerOrder(Tree *t, Queue *q){
    PushQueue(q, t);
    while(!QueueStatusEmpty(q)){
        Tree *p = PopQueue(q);
        printf("%d ",p->data);
        PushQueue(q, p->Lchild);
        PushQueue(q, p->Rchild);
    }
    printf("\n");
}

//主函数
int main(){
    Tree *t = InitTree(1);
    Queue *q = InitQueue();
    //根节点规定为第0行，编号从1开始(即Row和No都从1开始)
    GiveBirth(t, 1, 2, 3);
    GiveBirth(t, 1, 1, 2);

    //下面为错误测试样例
    GiveBirth(t, 0, 1, 4);
    GiveBirth(t, 3, 1, 4);
    GiveBirth(t, 2, 0, 4);
    GiveBirth(t, 1, 1, 4);
    //以上为错误测试样例

    GiveBirth(t, 2, 1, 4);
    GiveBirth(t, 2, 2, 5);
    GiveBirth(t, 2, 3, 6);
    GiveBirth(t, 2, 4, 7);
    GiveBirth(t, 3, 1, 8);
    GiveBirth(t, 3, 8, 9);

    printf("The result of PreOrder:\n");
    PrintTree(t, 0);
    printf("The result of InOrder:\n");
    PrintTree(t, 1);
    printf("The result of PostOrder:\n");
    PrintTree(t, 2);
    printf("The result of LayerOrder:\n");
    LayerOrder(t, q);

    return 0;
}