建设物流网站,校园网站建设策划书,仪征建设银行官方网站,做电影网站的工具目录
一、解析树
二、树的遍历 一、解析树
我们可以用解析树来表示现实世界中像句子或数学表达式这样的构造。
我们可以将((73)*(5-2))这样的数学表达式表示成解析树。这是完全括号表达式#xff0c;乘法的优先级高于加法和减法#xff0c;但因为有括号#xff0c;所以在…目录
一、解析树
二、树的遍历 一、解析树
我们可以用解析树来表示现实世界中像句子或数学表达式这样的构造。
我们可以将((73)*(5-2))这样的数学表达式表示成解析树。这是完全括号表达式乘法的优先级高于加法和减法但因为有括号所以在做乘法前必须先做括号内的加法和减法。树的层次性有助于理解整个表达式的计算次序。在计算顶层的乘法前必须先计算子树中的加法和减法。 构建解析树的第一步是将表达式字符串拆分成标记列表。需要考虑4种标记左括号、右括号、运算符和操作数。我们知道左括号代表新表达式的起点所以应该创建一颗对应该表达式的新树。反之遇到右括号则意味着到达该表达式的终点。我们也知道操作数既是叶子节点也是其运算符的子节点。此外每个运算符都有左右子节点。
有了上述信息便可以定义以下4条规则
1如果当前标记是就为当前节点添加一个左子节点并下沉至该子节点
2如果当前标记在列表[,-,/,*]种就将当前节点的值设为当前标记对应的运算符为当前节点添加一个右子节点并下沉至该子节点
3如果当前标记是数字就将当前节点的值设为这个数并返回至父节点
4如果当前标记是就跳到当前节点的父节点。
追踪父节点的方法在遍历这棵树时使用栈记录父节点。每当要下沉至当前节点的子节点时先将当前节点压到栈中。当要返回当前节点的父节点时就将父节点从栈中弹出来。
解析树构建器代码如下
from pythonds.basic import Stack
from pythonds.trees import BinaryTreedef bulidParseTree(fpexp):fplistfpexp.split()pStackStack()eTreeBinaryTree()pStack.push(eTree)currentTreeeTreefor i in fplist:if i(:currentTree.insertLeft()pStack.push(currentTree)currentTreecurrentTree.getLeftChild()elif i not in -*/):currentTree.setRootVal(eval(i))parentpStack.pop()currentTreeparentelif i in -*/:currentTree.setRootVal(i)currentTree.insertRight()pStack.push(currentTree)currentTreecurrentTree.getRightChild()elif i ):currentTreepStack.pop()else:raise ValueError(Unknown Operator: i)return eTree
计算二叉解析树的递归函数
def evaluate(parseTree):opers{:operator.add,-:operator.sub,*:operator.mul,/:operator.truediv}leftCparseTree.getLeftChild()rightCparseTree.getRightChild()if leftC and rightC:fnopers[parseTree.getRootVal()]return fn(evaluate(leftC),evaluate(rightC))else:return parseTree.getRootVal()
二、树的遍历
我们将对所有节点的的访问称为“遍历”共有3种遍历方式分别为前序遍历、中序遍历和后序遍历。
前序遍历
在前序遍历中先访问根节点然后递归地前序遍历左子树最后递归地前序遍历右子树。
中序遍历
在中序遍历中先递归地中序遍历左子树然后访问根节点最后递归地中序遍历右子树。
后序遍历
在后序遍历中先递归地后序遍历左子树然后递归地后序遍历右子树最后访问根节点。
遍历树的代码格外简洁这主要是因为遍历是递归的。
将前序遍历算法实现为外部函数
def preorder(tree):if tree:print(tree.getRootVal())preorder(tree.getLeftChild())preorder(tree.getRightChild())
将前序遍历算法实现为BinaryTree类的方法
def preorder(self):print(self.key)if self.leftChild:self.left.preorder()if self.rightChild:self.right.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.truediv}res1Noneres2Noneif tree:res1postordereval(tree.getLeftChild())res2postordereval(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):sValif tree:sVal(printexp(tree.getLeftChild())sValsValstr(tree.getRootVal())sValsValprintexp(tree.getRightChild()))return sVal
