c语言如何实现二叉树的中序遍历

在C语言中，可以通过递归或迭代的方式来实现二叉树的中序遍历。这里给出两种方法的代码示例：

方法一：递归

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

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

// 中序遍历的递归函数
void inorderTraversal(struct TreeNode* node) {
    if (node == NULL) {
        return;
    }
    inorderTraversal(node->left);  // 遍历左子树
    printf("%d ", node->val);       // 访问根节点
    inorderTraversal(node->right); // 遍历右子树
}

// 创建新节点的辅助函数
struct TreeNode* newNode(int val) {
    struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

int main() {
    // 创建示例二叉树
    struct TreeNode* root = newNode(1);
    root->right = newNode(2);
    root->right->left = newNode(3);

    // 执行中序遍历
    inorderTraversal(root);

    return 0;
}

方法二：迭代（使用栈）

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

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

// 中序遍历的迭代函数
void inorderTraversal(struct TreeNode* root) {
    if (root == NULL) {
        return;
    }

    struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack));
    struct TreeNode* currentNode = root;

    while (currentNode != NULL || !isEmpty(stack)) {
        // 遍历左子树，将节点压入栈中
        while (currentNode != NULL) {
            stackPush(stack, currentNode);
            currentNode = currentNode->left;
        }

        // 弹出栈顶元素，访问节点，并转向右子树
        currentNode = stackPop(stack);
        printf("%d ", currentNode->val);
        currentNode = currentNode->right;
    }

    free(stack);
}

// 栈结构体定义及操作函数
struct Stack {
    struct TreeNode** data;
    int top;
    int capacity;
};

void initStack(struct Stack* stack, int capacity) {
    stack->data = (struct TreeNode**)malloc(capacity * sizeof(struct TreeNode*));
    stack->top = -1;
    stack->capacity = capacity;
}

bool isEmpty(struct Stack* stack) {
    return stack->top == -1;
}

void stackPush(struct Stack* stack, struct TreeNode* node) {
    if (stackIsFull(stack)) {
        printf("Stack overflow\n");
        return;
    }
    stack->data[++stack->top] = node;
}

struct TreeNode* stackPop(struct Stack* stack) {
    if (isEmpty(stack)) {
        printf("Stack underflow\n");
        return NULL;
    }
    return stack->data[stack->top--];
}

bool stackIsFull(struct Stack* stack) {
    return stack->top == stack->capacity - 1;
}

int main() {
    // 创建示例二叉树
    struct TreeNode* root = newNode(1);
    root->right = newNode(2);
    root->right->left = newNode(3);

    // 执行中序遍历
    inorderTraversal(root);

    return 0;
}

这两种方法都可以实现二叉树的中序遍历。递归方法更简洁直观，但可能受到栈空间限制；迭代方法使用显式栈来避免栈溢出的问题，但代码相对复杂。

亿速云「云服务器」，即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘，价格低至29元/月。点击查看>>