运用c语言用递归算法实现二叉树的中序遍历

好的，我来回答你的问题。

首先，让我们定义二叉树的结构体：

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

其中，`val` 表示节点的值，`left` 表示左子树，`right` 表示右子树。

接下来，我们就可以使用递归算法来实现中序遍历了：

void inorder(struct node *root) {
    if (root != NULL) {
        inorder(root->left);
        printf("%d ", root->val);
        inorder(root->right);
    }
}

这个函数接收一个二叉树的根节点作为参数，如果根节点不为空，就先递归遍历左子树，然后输出当前节点的值，最后递归遍历右子树。

这样，就能实现二叉树的中序遍历了。

相关问题

用C语言实现二叉树中序遍历非递归算法

在C语言中，实现二叉树的非递归中序遍历通常需要借助栈数据结构。非递归的方法可以分为三个步骤：

1. 创建一个空栈，并将根节点压入栈中。
2. 当栈不为空时，执行循环：
a. 弹出栈顶元素，访问该元素（即当前节点）。
b. 如果当前节点有左子节点，将左子节点压入栈中。
c. 如果当前节点有右子节点，因为我们要按照"左-根-右"的顺序访问，跳过右子节点直接处理下一个节点（即检查下一个栈顶元素）。
3. 当栈为空且所有节点都已访问完，遍历结束。

以下是C语言的一个示例代码：

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

// 定义二叉树节点结构体
typedef struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

// 非递归中序遍历函数
void inorderTraversal(TreeNode* root) {
    if (root == NULL) return; // 如果根节点为空，直接返回

    Stack<TreeNode*> stack; // 使用栈来辅助遍历
    TreeNode* curr = root; // 初始化当前节点

    while (curr != NULL || !stack.isEmpty()) { // 循环直到栈为空且当前节点也为空
        while (curr != NULL) {
            stack.push(curr); // 将当前节点压栈
            curr = curr->left; // 转向左子节点
        }

        curr = stack.pop(); // 弹出栈顶节点并访问
        printf("%d ", curr->val); // 打印节点值
        curr = curr->right; // 移动到右子节点
    }
}

int main() {
    // 示例二叉树
    TreeNode* root = malloc(sizeof(TreeNode));
    root->val = 1;
    root->left = malloc(sizeof(TreeNode));
    root->left->val = 2;
    root->right = malloc(sizeof(TreeNode));
    root->right->val = 3;
    root->left->left = malloc(sizeof(TreeNode));
    root->left->left->val = 4;
    root->left->right = malloc(sizeof(TreeNode));
    root->left->right->val = 5;

    inorderTraversal(root);
    return 0;
}

运行此程序会打印出：`4 2 5 1 3`，这是二叉树 `1 - 2(4 5) - 3` 的中序遍历结果。

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

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

// 二叉树结点结构体
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

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

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

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

// 中序遍历非递归算法
void inorderTraversal(struct TreeNode* root){
    if(root == NULL) return;
    struct TreeNode* stack[1000];
    int top = 0;
    struct TreeNode* p = root;
    while(p != NULL || top > 0){
        if(p != NULL){
            stack[top++] = p;
            p = p->left;
        }else{
            p = stack[--top];
            printf("%d ", p->val);
            p = p->right;
        }
    }
}

// 后序遍历非递归算法
void postorderTraversal(struct TreeNode* root){
    if(root == NULL) return;
    struct TreeNode* stack[1000];
    int top = 0;
    struct TreeNode* p = root;
    struct TreeNode* last = NULL;
    while(p != NULL || top > 0){
        if(p != NULL){
            stack[top++] = p;
            p = p->left;
        }else{
            struct TreeNode* temp = stack[top - 1];
            if(temp->right != NULL && temp->right != last){
                p = temp->right;
            }else{
                printf("%d ", temp->val);
                last = temp;
                top--;
            }
        }
    }
}

非递归算法的实现利用了栈的数据结构，对于中序遍历算法，我们需要先将当前节点的所有左子节点入栈，然后弹出栈顶节点并输出，再将当前节点指向该节点的右子节点；对于后序遍历算法，我们需要在弹出栈顶节点时，判断该节点的右子节点是否已经被访问过，如果没有，将其右子节点入栈，否则我们可以输出该节点并将其标记为已访问。