二叉树-链表存储，用二叉树构造表达式（Python实现）

既然用到二叉树了，直观上链表的方式比较容易接受，下面用python实现简单的二叉树。二叉树是递归结构，Python的list也是递归结构，基于list类型很容易实现二叉树：
下面是函数

def bintree(data,left=None,right=None):
    return [data,left,right]
def is_empty_bintree(btree):
    return btree is None
def root(btree):
    return btree[0]
def left(btree):
    return btree[1]
def right(btree):
    return btree[2]
def set_root(btree,data):
    btree[0] = data
def set_left(btree,left):
    btree[1]=left
def set_right(btree,right):
     btree[2]=right
t1 = bintree(2,bintree(4),bintree(8))
print t1
# t1 = [2,[4,None,None],[8,None,None]]
set_left(left(t1),bintree(5))
print t1

执行结果：
[2, [4, None, None], [8, None, None]]
[2, [4, [5, None, None], None], [8, None, None]]

上面用二叉树构造了表达式，下面采用tuple计算结果，计算公式：

def is_basic_exp(a):
    return not isinstance(a,tuple)
def is_number(x):
    return (isinstance(x,int) or isinstance(x,float) or isinstance(x,complex))
def eval_sum(a,b):
        if is_number(a) and is_number(b):
            return a+b
        if is_number(a) and a ==0:
            return b
        if is_number(b) and b==0:
            return a
        return make_sum(a,b)
def eval_div(a,b):
        if is_number(a) and is_number(b):
            return a/b
        if is_number(a) and a ==0:
            return 0
        if is_number(b) and b==1:
            return a
        if is_number(b) and b ==0:
            raise ZeroDivisionError
        return make_div(a,b)
def eval_prod(a,b):
        if is_number(a) and is_number(b):
            return a*b
        return make_prod(a,b)
def eval_exp(e):
    if is_basic_exp(e):
        return e
    op, a, b = e[0],eval_exp(e[1]),eval_exp(e[2])
    #**
    if op =='+':
        return eval_sum(a,b)
    if op=='-':
        return eval_diff(a,b)
    if op =='*':
        return eval_prod(a,b)
    elif op == '/':
        return eval_div(a,b)
    else:
        raise ValueError("Unknown operator:", op)

a = 3
b = 2
e2 = make_sum(make_prod(a,2),make_prod(b,7))
print e2

e3 =  eval_exp(e2)
print e3

计算结果：
('', 3, ('+', 2, 5))
('+', ('', 3, 2), ('*', 2, 7))
20