中序遍历二叉树 c语言

中序遍历是一种常见的二叉树遍历方法，它按照“左-根-右”的顺序访问二叉树的节点。在C语言中，我们可以使用递归或栈来实现这个过程。以下是中序遍历的C语言实现：

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

// 中序遍历函数
void inorderTraversal(TreeNode* root) {
    if (root != NULL) { // 当前节点非空
        inorderTraversal(root->left); // 遍历左子树
        printf("%d ", root->val); // 访问当前节点
        inorderTraversal(root->right); // 遍历右子树
    }
}

在这个函数中，我们首先检查根节点是否为空，如果为空则返回；如果不为空，就先递归地遍历左子树，然后访问当前节点，最后遍历右子树。

相关问题

非递归中序遍历二叉树C语言

非递归中序遍历二叉树通常涉及到栈的数据结构。在C语言中，你可以使用一个栈来保存待访问的节点，按照"左-根-右"的顺序遍历二叉树。以下是实现的一个简单版本：

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

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

// 助手函数：用于入栈
void push(TreeNode* node) {
    if (node == NULL) return;
    stack.push(node);
}

// 助手函数：用于出栈并访问当前节点
TreeNode* popAndVisit() {
    if (stack.isEmpty()) return NULL;
    TreeNode* temp = stack.pop();
    printf("%d ", temp->val); // 访问节点值
    return temp;
}

// 中序遍历非递归实现
void inorderTraversal(TreeNode* root) {
    Stack stack; // 创建空栈
    TreeNode* current = root;

    while (current != NULL || !stack.isEmpty()) {
        // 当前节点未访问完且栈不为空
        while (current != NULL) {
            push(current);
            current = current->left;
        }
        current = popAndVisit(); // 出栈并访问节点，然后将右子节点压入栈
        current = current->right;
    }
}

int main() {
    // 假设你已经有了一个二叉树实例root
    inorderTraversal(root);
    return 0;
}

二叉树中序遍历c语言

以下是C语言实现二叉树中序遍历的代码：

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

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

// 定义栈结构体
struct Stack {
    struct TreeNode **data;
    int top;
    int size;
};

// 初始化栈
void initStack(struct Stack *s, int size) {
    s->data = (struct TreeNode **)malloc(sizeof(struct TreeNode *) * size);
    s->top = -1;
    s->size = size;
}

// 判断栈是否为空
int isEmpty(struct Stack *s) {
    return s->top == -1;
}

// 判断栈是否已满
int isFull(struct Stack *s) {
    return s->top == s->size - 1;
}

// 入栈
void push(struct Stack *s, struct TreeNode *node) {
    if (isFull(s)) {
        return;
    }
    s->data[++s->top] = node;
}

// 出栈
struct TreeNode *pop(struct Stack *s) {
    if (isEmpty(s)) {
        return NULL;
    }
    return s->data[s->top--];
}

// 中序遍历
void inorderTraversal(struct TreeNode *root) {
    if (root == NULL) {
        return;
    }
    struct Stack s;
    initStack(&s, 100);
    struct TreeNode *p = root;
    while (p != NULL || !isEmpty(&s)) {
        while (p != NULL) {
            push(&s, p);
            p = p->left;
        }
        if (!isEmpty(&s)) {
            p = pop(&s);
            printf("%d ", p->val);
            p = p->right;
        }
    }
}

// 创建二叉树
struct TreeNode *createTree() {
    int val;
    scanf("%d", &val);
    if (val == -1) {
        return NULL;
    }
    struct TreeNode *node = (struct TreeNode *)malloc(sizeof(struct TreeNode));
    node->val = val;
    node->left = createTree();
    node->right = createTree();
    return node;
}

int main() {
    struct TreeNode *root = createTree();
    inorderTraversal(root);
    return 0;
}