图文详解Python解析树及树的遍历

本篇是给大家介绍的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 

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()) 

def preorder(self):
  print(self.key)
  if self.leftChild:
    self.leftChild.preorder()
  if self.rightChild:
    self.rightChild.preorder() 

def postorder(tree):
  if tree != None:
    postorder(tree.getLeftChild())
    postorder(tree.getRightChild())
    print(tree.getRootVal()) 

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() 

def inorder(tree):
 if tree != None:
   inorder(tree.getLeftChild())
   print(tree.getRootVal())
   inorder(tree.getRightChild()) 

def printexp(tree):
 sVal = ""
 if tree:
   sVal = '(' + printexp(tree.getLeftChild())
   sVal = sVal + str(tree.getRootVal())
   sVal = sVal + printexp(tree.getRightChild())+')'
 return sVal 

我们发现 printexp 函数对每个数字也加了括号，这些括号显然没必要加。

以上就是图文详解Python解析树及树的遍历的详细内容，更多请关注Gxl网其它相关文章！

查看更多关于图文详解Python解析树及树的遍历的详细内容...