二叉树层次建树前序中序后序遍历层序遍历代码

二叉树的建树，层次建树，深度优先遍历，广度优先遍历

二叉树前序、中序、后序遍历

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

// 定义一个二叉树结构体
typedef char BiElemType;
typedef struct BiTNode {
    BiElemType c;
    struct BiTNode *lchild;
    struct BiTNode *rchild;
} BiTNode, *BiTree;

// tag结构体是辅助队列使用的
typedef struct tag {
    BiTree p; // 树的某一个节点的地址值
    struct tag *pnext;
} tag_t, *ptag_t;

// 前序遍历，深度优先遍历
void preOrder(BiTree p) {
    // 判断是否满足条件
    if (NULL != p) {
        printf("%c", p->c);
        preOrder(p->lchild); // 打印左子树
        preOrder(p->rchild); // 打印右子树
    }
}

// 中序遍历
void inOrder(BiTree p) {
    // 判断是否满足条件
    if (NULL != p) {
        inOrder(p->lchild); // 打印左子树
        printf("%c", p->c);
        inOrder(p->rchild); // 打印右子树
    }
}

// 后续遍历
void posOrder(BiTree p) {
    // 判断是否满足条件
    if (NULL != p) {
        posOrder(p->lchild); // 打印左子树
        posOrder(p->rchild); // 打印右子树
        printf("%c", p->c);
    }
}

// 队列
typedef BiTree ElemType;
typedef struct LinkNode {
    ElemType data;
    struct LinkNode *next;
} LinkNode;

typedef struct {
    LinkNode *front, *rear;
} LinkQueue; // 先进先出

// 队列的初始化，使用的是带头节点的链表来实现的
void initQueue(LinkQueue &Q) {
    Q.front = Q.rear = (LinkNode *) malloc(sizeof(LinkNode));
    Q.front->next = NULL; // 头指针指向
}

// 判断队列是否为空
bool isEmptyQueue(LinkQueue Q) {
    return Q.front == Q.rear;
}

// 入队，尾插法
void enQueue(LinkQueue &Q, ElemType e) {
    LinkNode *p = (LinkNode *) malloc(sizeof(LinkNode));
    p->data = e;
    p->next = NULL;   // next指向NULL
    Q.rear->next = p; // 尾指针的 next指向p，因为要从尾部入队
    Q.rear = p;       // rear要指向新的尾部
}

// 出队,头部删除方法
bool deQueue(LinkQueue &Q, ElemType &e) {
    // 判断队列为空
    if (Q.front == Q.rear) {
        return false;
    }
    LinkNode *p = Q.front->next;
    e = p->data;
    Q.front->next = p->next;//断链
    if (Q.rear == p) {//删除的是最后一个元素
        Q.rear = Q.front;//队列置为空
    }
    free(p);
    return true;
}

// 层次遍历、层序便来，广度优先遍历
void levelOrder(BiTree T) {
    LinkQueue Q;
    initQueue(Q);
    BiTree p; // 存储出队的节点
    // 把根节点入队
    enQueue(Q, T);
    // 判断队列是否为空
    while (!isEmptyQueue(Q)) {
        deQueue(Q, p);
        putchar(p->c);  // 等价于 printf("%c",c);
        // 入队
        if (p->lchild != NULL) {
            enQueue(Q, p->lchild);
        }
        if (p->rchild != NULL) {
            enQueue(Q, p->rchild);
        }
    }
}

// 二叉树的建树，层次建树
int main() {
    BiTree pnew; // 申请一个树的新节点
    BiTree tree = NULL;  // 指向树根，代表树
    char c;
    // phead就是队列头，ptail就是队列尾
    ptag_t phead = NULL, ptail = NULL, listpnew = NULL, pcur;
    while (scanf("%c", &c)) {
        if (c == '\n') {
            break;  // 读到换行结束
        }
        // calloc申请的空间大小是两个参数直接相乘，并对空间进行初始化，赋值为0
        pnew = (BiTree) calloc(1, sizeof(BiTNode));
        // 数据放进去
        pnew->c = c;
        // 给队列申请空间
        listpnew = (ptag_t) calloc(1, sizeof(tag_t));
        listpnew->p = pnew;
        // 如果是树的第一个节点
        if (NULL == tree) {
            tree = pnew;  // tree指向树的根节点
            phead = listpnew; // 第一个节点即是队列头，也是队列尾
            ptail = listpnew; // 队列尾
            pcur = listpnew; // pcur 要指向要进入树的父亲元素
        } else {
            // 让元素先入队列
            ptail->pnext = listpnew;
            ptail = listpnew;
            if (NULL == pcur->p->lchild) {
                pcur->p->lchild = pnew; // 左孩子为空，就放入左孩子
            } else if (NULL == pcur->p->rchild) {
                pcur->p->rchild = pnew;
                pcur = pcur->pnext; //当前节点左右孩子都有了，pcur就指向下一个
            }
        }
    }

    // 二叉树前序、中序、后续遍历
    printf("--------------preOrder()----------------\n");
    preOrder(tree);
    printf("\n");
    // 中序遍历
    printf("--------------inOrder()-----------------\n");
    inOrder(tree);
    printf("\n");
    // 后续遍历
    printf("--------------posOrder()-----------------\n");
    posOrder(tree);

    printf("\n");
    // 层次遍历，广度优先遍历
    printf("--------------levelOrder()-----------------\n");
    levelOrder(tree);
    printf("\n");
    return 0;
}