运用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语言用递归实现二叉树中序遍历

二叉树的中序遍历递归实现比较简单，具体步骤如下：

1. 对当前节点的左子树进行中序遍历。
2. 访问当前节点。
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;
    }

    inorderTraversal(root->left);
    printf("%d ", root->val);
    inorderTraversal(root->right);
}

// 测试
int main() {
    TreeNode *root = (TreeNode *)malloc(sizeof(TreeNode));
    root->val = 1;

    root->left = (TreeNode *)malloc(sizeof(TreeNode));
    root->left->val = 2;

    root->right = (TreeNode *)malloc(sizeof(TreeNode));
    root->right->val = 3;

    root->left->left = NULL;

    root->left->right = (TreeNode *)malloc(sizeof(TreeNode));
    root->left->right->val = 4;

    root->left->right->left = (TreeNode *)malloc(sizeof(TreeNode));
    root->left->right->left->val = 5;
    root->left->right->left->left = NULL;
    root->left->right->left->right = NULL;

    root->left->right->right = NULL;

    root->right->left = NULL;

    root->right->right = (TreeNode *)malloc(sizeof(TreeNode));
    root->right->right->val = 6;

    root->right->right->left = NULL;

    root->right->right->right = NULL;

    inorderTraversal(root);
    printf("\n");

    return 0;
}

其中，TreeNode是结点的结构体。该算法的时间复杂度为O(n)，空间复杂度为O(h)，其中h为二叉树的高度。

用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函数分别是中序遍历和后序遍历的非递归算法。在非递归算法中，我们使用了栈来模拟递归的过程。