Python二叉树的构建、解析与遍历

一、二叉树的构建有两种方法： 1.列表之列表 2.节点与引用（使用递归） ①列表之列表：使用Python特有的列表结构，用嵌套的形式进而实现，每个父节点默认有两个子节点，可以为空

def BinaryTree(r): return [r,[],[]] def insertLeft(root,newBranch): t=root.pop(1) if len(t)>1: root.insert(1,[newBranch,t,[]]) else: root.insert(1,[newBranch,[],[]]) def insertRight(root,newBranch): t=root.pop(2) if len(t)>1: root.insert(2,[newBranch,t,[]]) else: root.insert(2,[newBranch,[],[]]) def getRootVal(root): return root[0] def getRootVal(root): return root[0] def setRootVal(root,newVal): root[0]=newVal def getLeftChild(root): return root[1] def getRightChild(root): return root[2] a=BinaryTree(3) insertLeft(a,5) insertLeft(a,4) insertRight(a,9) l=getLeftChild(a) setRootVal(l,'a') print(a)

②节点与引用：运用递归的思想，所有二叉树的子树也是二叉树

class BinaryTree(): def __init__(self,rootObj): self.key=rootObj self.leftChild=None self.rightChild=None def InsertLeft(self,newObj): if self.leftChild: t=BinaryTree(newObj) t.leftChild=self.leftChild #注意和后面一行的顺序 self.leftChild=t else: self.leftChild=BinaryTree(newObj) def InsertRight(self,newObj): if self.rightChild: t=BinaryTree(newObj) t.rightChild=self.rightChild #注意和后面一行的顺序 self.rightChild=t else: self.rightChild=BinaryTree(newObj) def getLeftChild(self): return self.leftChild def getRightChild(self): return self.rightChild def setRootVal(self,obj): self.key=obj def getRootVal(self): return self.key r=BinaryTree('a') print(r.getRootVal()) r.InsertLeft('a') print(r.getLeftChild()) print(r.getLeftChild().getRootVal()) r.getLeftChild().setRootVal('b') print(r.getLeftChild().getRootVal())

二、二叉树的解析和计算 ①解析 原理：使用完全括号法构建二叉树 1.遇到(，就为当前节点添加一个左节点，并下沉到该子节点； 2.遇到符号，就将当前节点的值设为当前标记的运算符，并添加一个右节点，并下沉； 3.遇到数字，就将当前节点的值设为这个数，然后返回至父节点； 4.遇到)，就返回父节点

from pythonds.trees import BinaryTree from pythonds.basic import Stack 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 in ['+','-','*','/']: currentTree.setRootVal(i) currentTree.insertRight('') pStack.push(currentTree) currentTree=currentTree.getRightChild() elif i not in ['+','-','*','/',')']: currentTree.setRootVal(int(i)) parent=pStack.pop() currentTree=parent else: currentTree=pStack.pop() return eTree pt = buildParseTree("( ( 10 + 5 ) * 3 )") print(pt.getLeftChild().getRootVal())

②计算（一般单独作为外部函数，也可以放到类里面）

import operator def evaluate(parseTree): opers={'+':operator.add,'-':operator.sub,'*':operator.mul, '/':operator.truediv} leftC=parseTree.getLeftChild() rightC=parseTree.getRightChild() if leftC and rightC: #带节点的子树 fn=opers[parseTree.getRootVal()] return fn(evaluate(leftC),evaluate(rightC)) #递归调用 else: #没有子节点的节点 return parseTree.getRootVal() pt = buildParseTree("( ( 10 + 5 ) * 3 )") print(evaluate(pt))

三、二叉树的遍历 ①前序遍历：

def preorder(Tree): if Tree: print(Tree.getRootVal()) preorder(Tree.getLeftChild()) preorder(Tree.getRightChild()) pt = buildParseTree("( ( 10 + 5 ) * 3 )") preorder(pt)

②后序遍历：（不知道书中为什么给的是左-右-根）

def postorder(Tree): if Tree: postorder(Tree.getLeftChild()) postorder(Tree.getRightChild()) print(Tree.getRootVal()) pt = buildParseTree("( ( 10 + 5 ) * 3 )") postorder(pt)

③中序遍历

def inorder(Tree): if Tree: inorder(Tree.getLeftChild()) print(Tree.getRootVal()) inorder(Tree.getRightChild()) pt = buildParseTree("( ( 10 + 5 ) * 3 )") print(inorder(pt))

④用括号展示二叉树

def printexp(Tree): sVal='' if Tree: sVal='('+printexp(Tree.getLeftChild()) sVal=sVal+str(Tree.getRootVal()) sVal=sVal+printexp(Tree.getRightChild())+')' return sVal pt = buildParseTree("( ( 10 + 5 ) * 3 )") print(printexp(pt))

前序

中序 后序（但书中的仿佛是左-右-根）