在C语言中实现二叉树中序遍历，如何分别采用递归和非递归方法？

在C语言中实现二叉树的中序遍历，涉及到递归和非递归两种方法。对于递归方法，你需要定义一个递归函数，该函数按照先左子树、再根节点、最后右子树的顺序进行访问。下面是一个递归中序遍历的示例代码：

参考资源链接：[北航991数据结构与C语言历年真题解析](https://wenku.csdn.net/doc/64fmi1ksq0?spm=1055.2569.3001.10343)

    void InOrderTraversal(struct TreeNode* root) {
        if (root == NULL) {
            return;
        }
        InOrderTraversal(root->left);
        printf(

参考资源链接：[北航991数据结构与C语言历年真题解析](https://wenku.csdn.net/doc/64fmi1ksq0?spm=1055.2569.3001.10343)

相关问题

用C语言编程实现二叉树中序遍历和后续遍历的递归算法和非递归算法。

下面是C语言实现二叉树中序遍历和后序遍历的递归算法和非递归算法的代码示例：

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAXSIZE 100

// 二叉树结构体
typedef struct TreeNode {
    int data;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode, *PtrToNode;

// 栈结构体
typedef struct Stack {
    PtrToNode data[MAXSIZE];
    int top;
} Stack, *PtrToStack;

// 初始化栈
void InitStack(PtrToStack S) {
    S->top = -1;
}

// 判断栈是否为空
bool IsEmpty(PtrToStack S) {
    return S->top == -1;
}

// 判断栈是否已满
bool IsFull(PtrToStack S) {
    return S->top == MAXSIZE - 1;
}

// 入栈
void Push(PtrToStack S, PtrToNode X) {
    if (IsFull(S)) {
        printf("栈已满\n");
        return;
    }
    S->data[++S->top] = X;
}

// 出栈
PtrToNode Pop(PtrToStack S) {
    if (IsEmpty(S)) {
        printf("栈已空\n");
        return NULL;
    }
    return S->data[S->top--];
}

// 中序遍历递归算法
void InOrderTraversal(PtrToNode root) {
    if (root) {
        InOrderTraversal(root->left);
        printf("%d ", root->data);
        InOrderTraversal(root->right);
    }
}

// 中序遍历非递归算法
void InOrderTraversal2(PtrToNode root) {
    Stack S;
    InitStack(&S);
    PtrToNode p = root;
    while (p || !IsEmpty(&S)) {
        if (p) {
            Push(&S, p);
            p = p->left;
        } else {
            p = Pop(&S);
            printf("%d ", p->data);
            p = p->right;
        }
    }
}

// 后序遍历递归算法
void PostOrderTraversal(PtrToNode root) {
    if (root) {
        PostOrderTraversal(root->left);
        PostOrderTraversal(root->right);
        printf("%d ", root->data);
    }
}

// 后序遍历非递归算法
void PostOrderTraversal2(PtrToNode root) {
    Stack S;
    InitStack(&S);
    PtrToNode p = root;
    PtrToNode r = NULL;
    while (p || !IsEmpty(&S)) {
        if (p) {
            Push(&S, p);
            p = p->left;
        } else {
            p = S.data[S.top];
            if (p->right && p->right != r) {
                p = p->right;
                Push(&S, p);
                p = p->left;
            } else {
                p = Pop(&S);
                printf("%d ", p->data);
                r = p;
                p = NULL;
            }
        }
    }
}

// 创建二叉树
void CreateTree(PtrToNode *root) {
    int data;
    scanf("%d", &data);
    if (data == -1) {
        *root = NULL;
    } else {
        *root = (PtrToNode)malloc(sizeof(TreeNode));
        (*root)->data = data;
        CreateTree(&((*root)->left));
        CreateTree(&((*root)->right));
    }
}

int main() {
    PtrToNode root;
    printf("请输入二叉树的前序遍历序列，-1表示空节点：\n");
    CreateTree(&root);
    printf("中序遍历递归算法：");
    InOrderTraversal(root);
    printf("\n中序遍历非递归算法：");
    InOrderTraversal2(root);
    printf("\n后序遍历递归算法：");
    PostOrderTraversal(root);
    printf("\n后序遍历非递归算法：");
    PostOrderTraversal2(root);
    printf("\n");
    return 0;
}

其中，CreateTree函数用于创建二叉树，InOrderTraversal和PostOrderTraversal函数分别是中序遍历和后序遍历的递归算法，InOrderTraversal2和PostOrderTraversal2函数分别是中序遍历和后序遍历的非递归算法。在非递归算法中，我们使用了栈来模拟递归的过程。

请用C语言编程实现二叉树中序遍历和后续遍历的递归算法和非递归算法

以下是C语言实现二叉树中序遍历和后续遍历的递归算法和非递归算法的代码：

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

typedef struct Node {
    int data;
    struct Node* left;
    struct Node* right;
} Node;

// 递归中序遍历
void inorderRecursive(Node* root) {
    if (root == NULL) {
        return;
    }
    inorderRecursive(root->left);
    printf("%d ", root->data);
    inorderRecursive(root->right);
}

// 递归后序遍历
void postorderRecursive(Node* root) {
    if (root == NULL) {
        return;
    }
    postorderRecursive(root->left);
    postorderRecursive(root->right);
    printf("%d ", root->data);
}

// 非递归中序遍历
void inorderIterative(Node* root) {
    Node* stack[100];
    int top = -1;
    Node* current = root;
    while (current != NULL || top != -1) {
        while (current != NULL) {
            stack[++top] = current;
            current = current->left;
        }
        current = stack[top--];
        printf("%d ", current->data);
        current = current->right;
    }
}

// 非递归后序遍历
void postorderIterative(Node* root) {
    Node* stack1[100];
    Node* stack2[100];
    int top1 = -1;
    int top2 = -1;

    stack1[++top1] = root;
    while (top1 != -1) {
        Node* current = stack1[top1--];
        stack2[++top2] = current;

        if (current->left != NULL) {
            stack1[++top1] = current->left;
        }
        if (current->right != NULL) {
            stack1[++top1] = current->right;
        }
    }

    while (top2 != -1) {
        Node* current = stack2[top2--];
        printf("%d ", current->data);
    }
}

int main() {
    Node* root = (Node*)malloc(sizeof(Node));
    root->data = 1;
    root->left = (Node*)malloc(sizeof(Node));
    root->right = (Node*)malloc(sizeof(Node));
    root->left->data = 2;
    root->left->left = NULL;
    root->left->right = NULL;
    root->right->data = 3;
    root->right->left = (Node*)malloc(sizeof(Node));
    root->right->right = NULL;
    root->right->left->data = 4;
    root->right->left->left = NULL;
    root->right->left->right = NULL;

    printf("递归中序遍历：\n");
    inorderRecursive(root);
    printf("\n");

    printf("递归后序遍历：\n");
    postorderRecursive(root);
    printf("\n");

    printf("非递归中序遍历：\n");
    inorderIterative(root);
    printf("\n");

    printf("非递归后序遍历：\n");
    postorderIterative(root);
    printf("\n");

    return 0;
}