把中缀表达式转换为二叉树c语言实现

以下是将中缀表达式转换为二叉树的 C 语言实现：

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

// 定义二叉树节点结构体
typedef struct node {
    char data;
    struct node *left;
    struct node *right;
} Node;

// 定义栈结构体
typedef struct stack {
    int top;
    int capacity;
    Node **array;
} Stack;

// 初始化栈
Stack *initStack(int capacity) {
    Stack *stack = (Stack *)malloc(sizeof(Stack));
    stack->top = -1;
    stack->capacity = capacity;
    stack->array = (Node **)malloc(stack->capacity * sizeof(Node *));
    return stack;
}

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

// 判断栈是否已满
int isStackFull(Stack *stack) {
    return stack->top == stack->capacity - 1;
}

// 入栈
void push(Stack *stack, Node *node) {
    if (isStackFull(stack)) {
        printf("Stack is full!\n");
        return;
    }
    stack->array[++stack->top] = node;
}

// 出栈
Node *pop(Stack *stack) {
    if (isStackEmpty(stack)) {
        printf("Stack is empty!\n");
        return NULL;
    }
    return stack->array[stack->top--];
}

// 获取栈顶元素
Node *peek(Stack *stack) {
    if (isStackEmpty(stack)) {
        printf("Stack is empty!\n");
        return NULL;
    }
    return stack->array[stack->top];
}

// 判断是否为操作符
int isOperator(char c) {
    return c == '+' || c == '-' || c == '*' || c == '/';
}

// 创建节点
Node *createNode(char data) {
    Node *newNode = (Node *)malloc(sizeof(Node));
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

// 中缀表达式转换为二叉树
Node *infixToBinaryTree(char expression[]) {
    Stack *stack = initStack(strlen(expression));
    Node *root = NULL;

    for (int i = 0; i < strlen(expression); i++) {
        if (expression[i] == '(') {
            Node *newNode = createNode(expression[++i]);
            push(stack, newNode);
        } else if (isOperator(expression[i])) {
            Node *newNode = createNode(expression[i]);
            newNode->left = pop(stack);
            newNode->right = createNode(expression[++i]);
            push(stack, newNode);
        } else if (expression[i] == ')') {
            root = pop(stack);
        } else {
            Node *newNode = createNode(expression[i]);
            push(stack, newNode);
        }
    }

    return root;
}

// 中序遍历输出二叉树
void inOrderTraversal(Node *root) {
    if (root) {
        inOrderTraversal(root->left);
        printf("%c ", root->data);
        inOrderTraversal(root->right);
    }
}

// 测试函数
int main() {
    char expression[] = "((a+b)*(c-d))/e";
    Node *root = infixToBinaryTree(expression);
    inOrderTraversal(root);
    printf("\n");

    return 0;
}

以上代码基于栈实现，首先定义了 `Node` 结构体作为二叉树节点，然后定义了 `Stack` 结构体作为栈，包括初始化、入栈、出栈等基本操作。`isOperator` 函数用于判断是否为操作符，`createNode` 函数用于创建节点。`infixToBinaryTree` 函数实现了中缀表达式转换为二叉树的具体操作，最后通过中序遍历输出二叉树。