利用二叉树写一个C语言程序将算术表达式输入串（只要求1位整数）转换为后缀式，然后计算该表达式的值。要求： 1）从键盘或文件输入测试数据。 （2）输出算术表达式的后缀式和计算结果。

### 回答1：
以下是利用二叉树实现算术表达式转换为后缀式并计算的C语言程序：

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

typedef struct TreeNode {
    int val;  // 存放数字或操作符
    struct TreeNode* left;  // 左子树
    struct TreeNode* right;  // 右子树
} TreeNode;

typedef struct StackNode {
    TreeNode* p;  // 存放节点指针
    struct StackNode* next;  // 指向下一个节点的指针
} StackNode;

typedef struct Stack {
    StackNode* top;  // 栈顶指针
} Stack;

// 创建一个新的树节点
TreeNode* newTreeNode(int val) {
    TreeNode* p = (TreeNode*) malloc(sizeof(TreeNode));
    p->val = val;
    p->left = p->right = NULL;
    return p;
}

// 后序遍历删除二叉树
void deleteTree(TreeNode* root) {
    if (root) {
        deleteTree(root->left);
        deleteTree(root->right);
        free(root);
    }
}

// 创建一个新的栈节点
StackNode* newStackNode(TreeNode* p) {
    StackNode* node = (StackNode*) malloc(sizeof(StackNode));
    node->p = p;
    node->next = NULL;
    return node;
}

// 初始化栈
void initStack(Stack* stack) {
    stack->top = NULL;
}

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

// 入栈操作
void push(Stack* stack, TreeNode* p) {
    StackNode* node = newStackNode(p);
    node->next = stack->top;
    stack->top = node;
}

// 出栈操作，并返回弹出节点指针
TreeNode* pop(Stack* stack) {
    if (isStackEmpty(stack)) {
        return NULL;
    }
    StackNode* node = stack->top;
    TreeNode* p = node->p;
    stack->top = node->next;
    free(node);
    return p;
}

// 获取栈顶元素
TreeNode* getTop(Stack* stack) {
    if (isStackEmpty(stack)) {
        return NULL;
    }
    return stack->top->p;
}

// 判断是否是数字字符
int isDigit(char c) {
    return isdigit(c);
}

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

// 获取操作符优先级
int getPriority(char c) {
    if (c == '*' || c == '/') {
        return 2;
    } else if (c == '+' || c == '-') {
        return 1;
    } else {
        return 0;
    }
}

// 将中缀表达式转换为后缀表达式
TreeNode* infixToPostfix(char* infix) {
    Stack stack;
    initStack(&stack);
    TreeNode* root = NULL;
    TreeNode* prev = NULL;
    while (*infix != '\0') {
        if (isDigit(*infix)) {  // 处理数字字符
            TreeNode* p = newTreeNode(*infix - '0');
            if (!root) {
                root = p;
            } else if (!prev->right) {
                prev->right = p;
            }
            prev = p;
        } else if (isOperator(*infix)) {  // 处理操作符字符
            while (!isStackEmpty(&stack) && isOperator(getTop(&stack)->val) && getPriority(*infix) <= getPriority(getTop(&stack)->val)) {
                prev = pop(&stack);
                prev->left = pop(&stack);
                push(&stack, prev);
            }
            push(&stack, newTreeNode(*infix));
        } else if (*infix == '(') {  // 处理左括号
            push(&stack, newTreeNode(*infix));
        } else if (*infix == ')') {  // 处理右括号
            while (getTop(&stack)->val != '(') {
                prev = pop(&stack);
                prev->left = pop(&stack);
                push(&stack, prev);
            }
            pop(&stack);
        }
        infix++;
    }
    while (!isStackEmpty(&stack)) {  // 处理栈中剩余元素
        prev = pop(&stack);
        prev->left = pop(&stack);
        push(&stack, prev);
    }
    return root;
}

// 计算后缀表达式的值
int calcPostfix(TreeNode* root) {
    Stack stack;
    initStack(&stack);
    while (root) {
        if (!root->left && !root->right) {  // 处理数字节点
            push(&stack, root);
        } else {  // 处理操作符节点
            TreeNode* op2 = pop(&stack);
            TreeNode* op1 = pop(&stack);
            if (!op1 || !op2) {
                printf("Invalid expression!\n");
                exit(1);
            }
            TreeNode* res = newTreeNode(0);
            switch (root->val) {
                case '+':
                    res->val = op1->val + op2->val;
                    break;
                case '-':
                    res->val = op1->val - op2->val;
                    break;
                case '*':
                    res->val = op1->val * op2->val;
                    break;
                case '/':
                    if (op2->val == 0) {
                        printf("Divide by zero!\n");
                        exit(1);
                    }
                    res->val = op1->val / op2->val;
                    break;
            }
            push(&stack, res);
            free(op1);
            free(op2);
        }
        root = getTop(&stack)->right;
    }
    TreeNode* res = pop(&stack);
    int val = res->val;
    free(res);
    return val;
}

int main() {
    char buf[1024];
    printf("Enter an infix expression: ");
    fgets(buf, 1024, stdin);
    TreeNode* postfix = infixToPostfix(buf);
    printf("Postfix expression: ");
    TreeNode* p = postfix;
    while (p) {  // 输出后缀表达式
        printf("%c", p->val);
        p = p->right;
    }
    printf("\n");
    int result = calcPostfix(postfix);
    printf("Result: %d\n", result);
    deleteTree(postfix);
    return 0;
}

该程序实现了将中缀表达式转换为后缀表达式，并计算后缀表达式的值。其中，树节点存放数字或操作符，左子树指向左操作数，右子树指向右操作数或下一个操作符。栈节点存放节点指针，指向下一个节点的指针用于构成链表。程序中使用栈来辅助完成中缀表达式的转换和后缀表达式的计算。

### 回答2：
下面是一个使用二叉树实现的C语言程序，它可以将算术表达式输入串转换为后缀式，并计算表达式的值。程序从键盘输入测试数据，并输出算术表达式的后缀式和计算结果。

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

// 二叉树结点结构
typedef struct treeNode {
    char data;                  // 结点数据
    struct treeNode *left;      // 左子结点指针
    struct treeNode *right;     // 右子结点指针
} TreeNode;

// 创建一个新的结点
TreeNode* createNode(char data) {
    TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

// 判断字符是否为运算符
int isOperator(char c) {
    if (c == '+' || c == '-' || c == '*' || c == '/')
        return 1;
    return 0;
}

// 构建二叉树
TreeNode* buildExpressionTree(char* expression) {
    TreeNode *root = NULL;
    TreeNode *currentNode = NULL;
    TreeNode *stack[100];
    int top = -1;
    int i = 0;
    
    // 遍历输入表达式
    while (expression[i] != '\0') {
        if (!isOperator(expression[i])) {
            // 如果字符为操作数，则创建一个新的结点并入栈
            currentNode = createNode(expression[i]);
            stack[++top] = currentNode;
        } else {
            // 如果字符为运算符，则创建一个新的根节点，并将前面入栈的两个结点作为其左右子结点
            currentNode = createNode(expression[i]);
            currentNode->right = stack[top--];
            currentNode->left = stack[top--];
            stack[++top] = currentNode;
        }
        i++;
    }
    
    // 栈中最后一个结点就是构建的二叉树的根节点
    root = stack[top--];
    
    return root;
}

// 计算二叉树表示的表达式的值
int calculateExpression(TreeNode* root) {
    int leftValue, rightValue;
    
    if (root == NULL)
        return 0;
    
    // 递归遍历二叉树
    leftValue = calculateExpression(root->left);
    rightValue = calculateExpression(root->right);
    
    if (root->data == '+')
        return leftValue + rightValue;
    else if (root->data == '-')
        return leftValue - rightValue;
    else if (root->data == '*')
        return leftValue * rightValue;
    else if (root->data == '/')
        return leftValue / rightValue;
    else
        return root->data - '0';  // 当前结点为操作数，返回其值
    
}

int main() {
    char expression[100];
    
    printf("请输入算术表达式：");
    scanf("%s", expression);
    
    // 构建表达式对应的二叉树
    TreeNode* root = buildExpressionTree(expression);
    
    // 计算并输出后缀表达式
    printf("后缀式为：");
    postOrderTraversal(root);
    printf("\n");
    
    // 计算并输出结果
    int result = calculateExpression(root);
    printf("计算结果为：%d\n", result);
    
    return 0;
}

希望上述的程序可以满足您的需求。请注意，该程序只适用于包含1位整数的算术表达式，对于多位整数或其他更复杂的运算，可能需要对程序进行适当的修改。

### 回答3：
二叉树是一种适合用来处理算术表达式的数据结构，可以通过构建二叉树来将中缀表达式转换为后缀表达式，并利用后缀表达式来计算表达式的值。

首先，我们可以定义一个结构体来表示二叉树的节点，其中包括该节点的值和指向左子树和右子树的指针。然后，我们可以使用栈来辅助进行表达式的转换和计算。

1. 输入算术表达式：
可以通过从键盘或文件读取算术表达式输入串，并保存在一个字符数组中。

2. 构建二叉树：
通过遍历表达式输入串，遇到数字时创建一个具有该数字值的二叉树节点，并将其入栈；遇到运算符时，将栈中的节点出栈，并作为当前节点的子节点，然后将当前节点压入栈。最后栈顶的节点即为构建完成的二叉树的根节点。

3. 转换为后缀表达式：
通过遍历二叉树，使用后序遍历的方式输出二叉树的节点值，得到后缀表达式。

4. 计算表达式的值：
通过遍历后缀表达式，遇到数字时将其入栈；遇到运算符时，从栈中弹出两个数字进行相应的运算，并将结果压入栈。最后栈中唯一剩下的元素即为表达式的值。

需要注意的是，在将中缀表达式转换为后缀表达式时，需要考虑运算符的优先级和结合性，可以使用一个栈来记录运算符，并根据运算符的优先级来决定入栈和出栈的操作。

综上所述，可以利用二叉树来实现一个C语言程序，通过输入算术表达式输入串，将其转换为后缀表达式，并计算表达式的值。