王道书 P150 T20 + 拓展（表达式树的计算）

/**
 * 用二叉树链式存储实现 王道 P150 T20 + 拓展（表达式树的计算）
 *
 *
 * ①算法思想
 * ①将给定的表达式树转换为等价的中缀表达式：其实就是中缀表达式树加括号。
 * 记住中缀表达式加括号的逻辑。
 * 表达式树的中序序列加上必要的括号即为等价的中缀表达式。
 * 除根结点和叶子节点外，遍历到其他节点时在遍历其左子树之前加上左括号，遍历完右子树后加上右 
 * 括号。 
 * ②表达式树的计算:只要知道左子树的值和右子树的值，然后结合根节点的符号就可以计算出来了。
 *  
 * ②算法设计
 */
 
#include <stdio.h>
#include <iostream>
#define MaxSize 100
 
typedef struct BiTreeNodeC{
    char data;
    struct BiTreeNodeC *lchild,*rchild;
}BiTreeNodeC,*BiTreeC;
 
 
 
 
//P150 T20 （记住）
//①中缀表达式树加括号
void BiTreeToExp(BiTreeC T,int deep){//deep初值得是1
    if(!T)
        return;
    if(!T -> lchild && !T -> rchild)//叶子节点是操作数
        printf("%c",T -> data);
    else{
        if(deep > 1)
            printf("(");
        BiTreeToExp(T -> lchild,deep +1);
        printf("%c",T -> data);
        BiTreeToExp(T -> rchild,deep +1);
        if(deep > 1)
            printf(")");
    }
}
//②表达式树的计算（默认树的分叉都是两个）
int CalTreeExp(BiTreeC T){
    if(!T)
        return 0;
    if(!T -> lchild && !T -> rchild)
        return T -> data;
    else if(T -> lchild && T -> rchild){
        int leftValue = CalTreeExp(T -> lchild);
        int rightValue = CalTreeExp(T -> rchild);
        if(T -> data == '+')
            return leftValue + rightValue;
        if(T -> data == '-')
            return leftValue - rightValue;
        if(T -> data == '*')
            return leftValue * rightValue;
        if(T -> data == '/')
            return leftValue / rightValue;
    }
}