新闻网站域名360网站收录

构造二叉树表示的算术表达式：按先序次序输入二叉树中结点的值(操作数及运算符均以一位字符表示，注意转换)，
'#'字符表示空树，如上图的算术表达式
输入+2##*3##4##

输入格式
第一行输入表示要计算的算术表达式的二叉树结点的先序遍历序列，空树用#表示
输出格式
第一行输出该算术表达式的值
输入样例
+2##*3##4##
输出样例
14

部分代码如下：

#include "stdio.h"
#include "malloc.h"
#define TRUE 1
#define FALSE 0
#define OK  1
#define ERROR  0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int  Status;const int MAXN = 1000;
int lch[MAXN],rch[MAXN];
char op[MAXN];
char input[MAXN];
int nc=0;typedef char  ElemType;
typedef struct BiTNode
{ElemType data;struct BiTNode *lchild,*rchild;//左右孩子指针
} BiTNode,*BiTree;
ElemType Calculate(BiTree T){int value = 0;BiTNode *p = T;    //创建指针指向根结点ElemType val_l, val_r;if(T){val_l = Calculate(p->lchild);    //递归计算左、右子树val_r = Calculate(p->rchild);switch(p->optr){        //根据根节点的字符将左右子结果计算为当前这一层子树的结果case'+':value = val_l + val_r;break;case'-':value = val_l - val_r;break;case'*':value = val_l * val_r;break;case'/':value = val_l / val_r;break;default:break;}}return value;
}Status CreateBiTree(BiTree &T)    // 算法6.4
{// 按先序次序输入二叉树中结点的值（一个字符），’#’字符表示空树，// 构造二叉链表表示的二叉树T。char ch;scanf("%c",&ch);if (ch=='#') T = NULL;else{if (!(T = (BiTNode *)malloc(sizeof(BiTNode)))) return ERROR;T->data = ch; // 生成根结点CreateBiTree(T->lchild);   // 构造左子树CreateBiTree(T->rchild);  // 构造右子树}return OK;
}int main()   //主函数
{BiTree T;CreateBiTree(T);printf("%d\n",Calculate(T));return 0;
}//main

代码如下：

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
struct TreeNode
{char value;struct TreeNode* left;struct TreeNode* right;
};int calculate(struct TreeNode* root)
{if (root == NULL){return 0;}if (root->left == NULL && root->right == NULL){return root->value - '0';}int left = calculate(root->left);int right = calculate(root->right);switch (root->value){case '+':return left + right;case '-':return left - right;case '*':return left * right;case '/':return left / right;default:return 0;}
}struct TreeNode* createNode(char value)
{struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));node->value = value;node->left = NULL;node->right = NULL;return node;
}struct TreeNode* buildTree()
{char value = getchar();if (value == '#'){return NULL;}struct TreeNode* node = createNode(value);node->left = buildTree();node->right = buildTree();return node;
}int main()
{struct TreeNode* root = buildTree();printf("%d\n", calculate(root));return 0;
}