编辑代码

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

typedef char E;

struct twoTree {
    E element;
    struct twoTree *leftNode;
    struct twoTree *rightNode;
};

typedef struct twoTree *TreeNode;

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

// 二叉树的中序遍历 栈的实现
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;
}

// 二叉树的中序遍历 栈的实现
// 通过栈的先进后出的特性，将前面的root-> right 存入栈
void inOrder2(TreeNode root) {
    struct LNode stack;
    initStack(&stack);  //初始化栈
    do {
        while (root) {
            pushStack(&stack, root);// 右子树
            root = root->leftNode;
        }
        root = popStack(&stack);    //遍历完左子树将右子树出栈
        printf("%c", root->element);  // 左子树
        root = root->rightNode;
    } while (root || !isEmpty(&stack)); //栈空则退出前序遍历循环
}

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;

    inOrder2(a);
};