编辑代码

#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;

// 二叉树的后序遍历 递归实现
void postOrder(TreeNode root) {
    if (root == NULL) return;
    postOrder(root->leftNode);
    postOrder(root->rightNode);
    printf("%c", root->element);
}

// 二叉树的中序遍历 栈的实现
struct LNode {
    TreeNode element;
    struct LNode *Next;
};

// 引入我们之前写的栈
typedef struct LNode *Node;

// 栈的初始化方法
BOOL initStack(Node node) {
    node->Next = NULL;
}

BOOL pushStack(Node head, TreeNode tree) {
    // 动态申请内存
    Node node = malloc(sizeof(struct LNode));
    if (node == NULL) return 0;
    node->element = tree;
    // 往栈top添加元素
    node->Next = head->Next;
    head->Next = node;
    return 1;
}

BOOL isEmpty(Node node) {
    // 判断栈内是否有元素
    return node->Next == NULL;
}

TreeNode popStack(Node head) {
    //获取栈top元素，并且释放多余空间
    Node tmp = head->Next;
    head->Next = tmp->Next;
    TreeNode e = tmp->element;
    free(tmp);  //释放tmp空间
    return e;
}

TreeNode peakStack(Node head){
    return head->Next->element;
}
// 二叉树的后序遍历 栈的实现
// 通过栈的先进后出的特性，将前面的root-> right 存入栈
void postOrder2(TreeNode root) {
    struct LNode stack;
    initStack(&stack);  //初始化栈

    while (root || !isEmpty(&stack)) {//栈空则退出前序遍历循环
        while (root) {
            pushStack(&stack, root);// 子树
            root->flag = 0;         // 左子树遍历标记
            root = root->leftNode;
        }
        root = peakStack(&stack);
        if (root->flag == 0){
            root->flag = 1;     //右子树遍历标记
            root = root->rightNode;
        } else{
            printf("%c",root->element);
            popStack(&stack);   //将栈顶元素删除
            root = NULL;
        }
    }
}

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);
}