编辑代码

#include <stdio.h>
#include "windows.h"

typedef char E;

struct twoTree {
    E element;
    struct twoTree *leftNode;
    struct twoTree *rightNode;
    int flag;   //增加flag来判断是否左右都遍历过了
};

typedef struct twoTree *TreeNode;
// 二叉树的层序遍历 队列的实现
// 引入我们之前写的栈
struct LNode {
    TreeNode element;
    struct LNode *Next;
};

typedef struct LNode *Node;

struct Queue {
    Node front, rear;
};

typedef struct Queue *LQueue;

BOOL initQueue(LQueue queue) {
    queue->front = queue->rear = malloc(sizeof(struct LNode));
    if (queue->front == NULL) return 0;
    return 1;
}

// 链表队push方法
BOOL pushQueue(LQueue queue, TreeNode element) {
    Node NewNode = malloc(sizeof(struct LNode));    //  申请Node空间
    if (NewNode == NULL) return 0;  //空间不足返回Null
    NewNode->element = element;
    queue->rear->Next = NewNode;
    queue->rear = NewNode; //rear加指向NewNode
    return 1;
}

// 判断链表队是否为空
BOOL isEmpty(LQueue queue) {
    return queue->rear == queue->front;
}

TreeNode popQueue(LQueue queue) {
    if (isEmpty(queue)) return NULL; //判断队是否空，队空则返回-1
    queue->front = queue->front->Next;
    return queue->front->element;
}

// 二叉树的层序遍历 队列的实现
// 通过队列的先进先出的特性，依次将将元素出队并将子节点从左到右入队
void postOrder2(TreeNode root) {
    struct Queue queue;
    initQueue(&queue);
    pushQueue(&queue, root);    //先将根节点入队

    while (!isEmpty(&queue)) {
        root = popQueue(&queue);    //根节点出队
        if (root->leftNode != NULL)     //左子节点不为空则入队
            pushQueue(&queue, root->leftNode);
        if (root->rightNode != NULL)       //右子节点不为空则入队
            pushQueue(&queue, root->rightNode);
        printf("%c", root->element);    //并打印此节点
    }
}

int main() {
    TreeNode a = malloc(sizeof(struct twoTree));
    TreeNode b = malloc(sizeof(struct twoTree));
    TreeNode c = malloc(sizeof(struct twoTree));
    TreeNode d = malloc(sizeof(struct twoTree));
    TreeNode e = malloc(sizeof(struct twoTree));
    TreeNode f = malloc(sizeof(struct twoTree));

    a->element = 'A';
    b->element = 'B';
    c->element = 'C';
    d->element = 'D';
    e->element = 'E';
    f->element = 'F';

    a->leftNode = b;
    a->rightNode = c;
    b->leftNode = d;
    b->rightNode = e;
    c->rightNode = f;
    c->leftNode = NULL;
    d->leftNode = d->rightNode = NULL;
    e->leftNode = e->rightNode = NULL;
    f->leftNode = f->rightNode = NULL;

    postOrder2(a);
}