【正确答案】正确答案：以后序遍历方式遍历算术表达式的二叉树可以得到后缀表达式，后缀表达式求值已在前面讲过。这里给出另一种算法。重新定义二叉树结点结构为(1eft，data，val，fight)，其中left和fight是左右子女的指针，data是算法表达式中的字符，val是子表达式的值。采用后序遍历，先分别求出左子树和右子树表示的子表达式的值，最后计算出表达式的最后结果。算法如下： int PostEval(BiTree bt) ／／以后序遍历算法求以二叉树表示的算术表达式的值 {BiTree p=bt；int Iv，rv； if(p) (1v=PostEval(p一>lef))； ／／求左子树表示的子表达式的值 rv=PostEval(p一>right)； ／／求右子树表示的子表达式的值 if(!P一>left&&!P一>right) ／／叶子结点将数据值存到val域中 P一>val：P一>data一‘0’； ／／数字字符转成整数存储 else switch(p一>data) ／／求子表达式的值 {case‘+’：P一>val=p一>left一>val+p一>right一>val；break； case ‘一’：p一>Val=p一>left一>val—P一>right一>val；break； case ‘*’：p->val=p->left一>vai。P一>right一>val；break； case ‘／’：p一>Val=p一>1ef七一>val／p一>right一>val； }return(p->val)； } } 本算法中数值是以字符表示的，因此是一位数的算术运算。若是多位数(包括实数)，要做如下修改：在建立二叉树时进行拼数，一个数输入完毕再存入二叉树结点中；本算法中的p一>val=p一>data一0，要改为p一>Val=p一>data；lv和rv的类型做相应改变。拼数算法的核心语句段如下： case 0<=x<9一： ／／设读入字符x while((x>=0&&X<=‘9’)lI X==．) ／／拼数 if(x!=‘.’) ／／处理整数 { num=num*10+(ord(x)-ord(‘0’))；cin>>x；} ／／num初始值为0．0 else ／／处理小数部分 {scale=10．0；cin>>x； while(x>=’0‘&&x<=。9’) {num=num+(ord(x)-ord(。0’)／scale； scale=scale*10；cin>>x； } }