递归和非递归实现二叉树中序遍历c

递归实现二叉树中序遍历的C代码如下：

void inorderTraversal(struct TreeNode* root){
    if(root){
        inorderTraversal(root->left);
        printf("%d ",root->val);
        inorderTraversal(root->right);
    }
}

非递归实现二叉树中序遍历的C代码如下：

void inorderTraversal(struct TreeNode* root){
    struct TreeNode* stack[1000];
    int top = -1;
    while(root || top != -1){
        while(root){
            stack[++top] = root;
            root = root->left;
        }
        if(top != -1){
            root = stack[top--];
            printf("%d ", root->val);
            root = root->right;
        }
    }
}

其中，我们使用一个栈来模拟递归过程，先将root的所有左子树节点入栈，然后再逐个弹出并访问栈顶节点，最后再访问右子树即可。

相关问题

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

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

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

struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

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

// 递归后续遍历
void postorderTraversalRecursive(struct TreeNode* root) {
    if (root == NULL) return;
    postorderTraversalRecursive(root->left);
    postorderTraversalRecursive(root->right);
    printf("%d ", root->val);
}

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

// 非递归后续遍历
void postorderTraversalNonRecursive(struct TreeNode* root) {
    struct TreeNode* stack[100];
    int top = -1;
    struct TreeNode* lastVisit = NULL;
    while (root || top != -1) {
        while (root) {
            stack[++top] = root;
            root = root->left;
        }
        root = stack[top];
        if (root->right == NULL || root->right == lastVisit) {
            printf("%d ", root->val);
            lastVisit = root;
            root = NULL;
            top--;
        } else {
            root = root->right;
        }
    }
}

int main() {
    struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->val = 1;
    root->left = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->left->val = 2;
    root->left->left = NULL;
    root->left->right = NULL;
    root->right = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->right->val = 3;
    root->right->left = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->right->left->val = 4;
    root->right->left->left = NULL;
    root->right->left->right = NULL;
    root->right->right = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->right->right->val = 5;
    root->right->right->left = NULL;
    root->right->right->right = NULL;

    printf("递归中序遍历: ");
    inorderTraversalRecursive(root);
    printf("\n");

    printf("递归后续遍历: ");
    postorderTraversalRecursive(root);
    printf("\n");

    printf("非递归中序遍历: ");
    inorderTraversalNonRecursive(root);
    printf("\n");

    printf("非递归后续遍历: ");
    postorderTraversalNonRecursive(root);
    printf("\n");

    return 0;
}

输出结果如下：

递归中序遍历: 2 1 4 3 5 
递归后续遍历: 2 4 5 3 1 
非递归中序遍历: 2 1 4 3 5 
非递归后续遍历: 2 4 5 3 1 

请用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;
}