用C语言编写一个程序实现在二叉树的中序遍历递归和非递归

实现。

非递归中序遍历二叉树的算法如下：

1. 新建一个栈，用来存储遍历的节点。

2. 初始化当前节点为根节点。

3. 当前节点不为空或者栈不为空时，进行循环。在循环中：

a. 循环将当前节点及其左子树中的所有节点入栈，直到当前节点为空。

b. 弹出栈顶节点，访问该节点。

c. 将当前节点指向栈顶节点的右儿子，回到步骤 3。

C语言代码实现如下：

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

// 定义二叉树结构体
typedef struct node {
    int data;
    struct node *lchild;
    struct node *rchild;
} Node;

// 入栈操作
void push(Node **stack, int *top, Node *node) {
    stack[++(*top)] = node;
}

// 出栈操作
Node *pop(Node **stack, int *top) {
    return stack[(*top)--];
}

// 非递归中序遍历二叉树
void inorderTraversal(Node *root) {
    // 初始化栈和栈顶指针
    Node *stack[100];
    int top = -1;
    Node *cur = root;
    // 当前节点不为空或栈不为空时进行循环
    while (cur != NULL || top != -1) {
        // 将当前节点及其左子树中的所有节点入栈
        while (cur != NULL) {
            push(stack, &top, cur);
            cur = cur->lchild;
        }
        // 弹出栈顶元素，访问该节点，并将当前节点指向右子树
        Node *node = pop(stack, &top);
        printf("%d ", node->data);
        cur = node->rchild;
    }
}

// 递归中序遍历二叉树
void inorderTraversalRecursive(Node *root) {
    if (root == NULL) {
        return;
    }
    inorderTraversalRecursive(root->lchild);
    printf("%d ", root->data);
    inorderTraversalRecursive(root->rchild);
}

int main() {
    // 新建二叉树
    Node *a = (Node*)malloc(sizeof(Node));
    Node *b = (Node*)malloc(sizeof(Node));
    Node *c = (Node*)malloc(sizeof(Node));
    Node *d = (Node*)malloc(sizeof(Node));
    Node *e = (Node*)malloc(sizeof(Node));
    Node *f = (Node*)malloc(sizeof(Node));
    a->data = 1;
    b->data = 2;
    c->data = 3;
    d->data = 4;
    e->data = 5;
    f->data = 6;
    a->lchild = b;
    a->rchild = c;
    b->lchild = d;
    b->rchild = e;
    c->lchild = f;
    c->rchild = NULL;
    d->lchild = NULL;
    d->rchild = NULL;
    e->lchild = NULL;
    e->rchild = NULL;
    f->lchild = NULL;
    f->rchild = NULL;
    // 非递归中序遍历二叉树
    printf("非递归中序遍历二叉树：\n");
    inorderTraversal(a);
    printf("\n");
    // 递归中序遍历二叉树
    printf("递归中序遍历二叉树：\n");
    inorderTraversalRecursive(a);
    printf("\n");
    return 0;
}

输出结果为：

非递归中序遍历二叉树：
4 2 5 1 6 3 
递归中序遍历二叉树：
4 2 5 1 6 3