中缀表达式构建二叉树c语言

中缀表达式是一种常见的数学表达式，但它不方便计算机处理。我们可以使用二叉树来构建中缀表达式，使其更容易进行计算机处理。

首先，我们需要定义一个二叉树的结构，可以使用C语言中的结构体来定义。结构体包括节点的值和左右子节点指针。

接下来，我们需要编写一个函数来将中缀表达式转换成二叉树。这个函数可以使用栈来辅助实现。我们从左到右遍历中缀表达式，遇到操作数时就创建一个节点，遇到运算符时就将其压入栈中。当遇到右括号时，就从栈中弹出运算符和操作数，构建子树，并将子树的根节点压入栈中。最终，栈中只会剩下一个根节点，就是整个二叉树的根节点。

最后，我们可以编写一个计算二叉树表达式的函数。这个函数可以使用递归的方法来遍历二叉树，计算出表达式的值。

通过以上步骤，我们就可以使用C语言来构建中缀表达式的二叉树，并进行计算。这样就可以更方便地处理中缀表达式，使其适用于计算机处理。

相关问题

把中缀表达式转换为二叉树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` 函数实现了中缀表达式转换为二叉树的具体操作，最后通过中序遍历输出二叉树。

二叉树中的表达式按中缀表达式输出，并加上括号，给出c语言代码

下面是一个示例的 C 代码，用于将二叉树中的表达式按中缀表达式输出，并加上括号：

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

struct Node {
    char data;
    struct Node* left;
    struct Node* right;
};

struct Node* createNode(char data) {
    struct Node* node = (struct Node*)malloc(sizeof(struct Node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}

void inorderTraversal(struct Node* root) {
    if (root == NULL) {
        return;
    }
    
    if (root->left != NULL || root->right != NULL) {
        printf("(");
    }
    
    inorderTraversal(root->left);
    printf("%c", root->data);
    inorderTraversal(root->right);
    
    if (root->left != NULL || root->right != NULL) {
        printf(")");
    }
}

int main() {
    // 构建示例二叉树
    struct Node* root = createNode('+');
    root->left = createNode('*');
    root->right = createNode('-');
    root->left->left = createNode('a');
    root->left->right = createNode('b');
    root->right->left = createNode('c');
    root->right->right = createNode('d');
    
    // 按中缀表达式输出并加上括号
    inorderTraversal(root);
    
    return 0;
}

此代码中，我们首先定义了一个 `Node` 结构体，表示二叉树的节点。然后，我们实现了一个 `createNode` 函数，用于创建节点。接下来，我们实现了一个 `inorderTraversal` 函数，使用中序遍历的方式输出二叉树的中缀表达式，并在需要的地方加上括号。最后，在 `main` 函数中构建了一个示例二叉树，并调用 `inorderTraversal` 函数进行输出。注意，此处示例二叉树为了方便起见，直接在代码中进行构建，实际情况下可能需要根据具体需求进行修改。