# 图文详解python解析树及树的遍历

from pythonds.basic.stack import stack
from pythonds.trees.binarytree import binarytree
def buildparsetree(fpexp):
fplist = fpexp.split()
pstack = stack()
etree = binarytree(”)
pstack.push(etree)
currenttree = etree
for i in fplist:
if i == ‘(‘:
currenttree.insertleft(”)
pstack.push(currenttree)
currenttree = currenttree.getleftchild()
elif i not in [‘+’, ‘-‘, ‘*’, ‘/’, ‘)’]:
currenttree.setrootval(int(i))
parent = pstack.pop()
currenttree = parent
elif i in [‘+’, ‘-‘, ‘*’, ‘/’]:
currenttree.setrootval(i)
currenttree.insertright(”)
pstack.push(currenttree)
currenttree = currenttree.getrightchild()
elif i == ‘)’:
currenttree = pstack.pop()
else:
raise valueerror
return etree
pt = buildparsetree(“( ( 10 + 5 ) * 3 )”)
pt.postorder() #defined and explained in the next section

listing 1

def evaluate(parsetree):
opers = {‘+’:operator.add, ‘-‘:operator.sub, ‘*’:operator.mul, ‘/’:operator.truep}
leftc = parsetree.getleftchild()
rightc = parsetree.getrightchild()
if leftc and rightc:
fn = opers[parsetree.getrootval()]
return fn(evaluate(leftc),evaluate(rightc))
else:
return parsetree.getrootval()

def preorder(tree):
if tree:
print(tree.getrootval())
preorder(tree.getleftchild())
preorder(tree.getrightchild())

listing 3

def preorder(self):
print(self.key)
if self.leftchild:
self.leftchild.preorder()
if self.rightchild:
self.rightchild.preorder()

listing 4

def postorder(tree):
if tree != none:
postorder(tree.getleftchild())
postorder(tree.getrightchild())
print(tree.getrootval())

listing 5

def postordereval(tree):
opers = {‘+’:operator.add, ‘-‘:operator.sub, ‘*’:operator.mul, ‘/’:operator.truep}
res1 = none
res2 = none
if tree:
res1 = postordereval(tree.getleftchild())
res2 = postordereval(tree.getrightchild())
if res1 and res2:
return opers[tree.getrootval()](res1,res2)
else:
return tree.getrootval()

listing 6

def inorder(tree):
if tree != none:
inorder(tree.getleftchild())
print(tree.getrootval())
inorder(tree.getrightchild())

listing 7

def printexp(tree):
sval = “”
if tree:
sval = ‘(‘ + printexp(tree.getleftchild())
sval = sval + str(tree.getrootval())
sval = sval + printexp(tree.getrightchild())+’)’
return sval

Posted in 未分类