数据结构与算法_二叉树与二叉堆的Python实现
数据结构和算法是计算机技术的基本功之一，北京大学的课程深入浅出，使用Python作为载体简化了编程难度。最近浏览了59-67，主要内容是树结构的介绍，二叉树结构及其实现（含完全二叉树定义与实现问题），二叉堆结构及其实现。并且以语法解析树为例探讨了树结构的应用。
非线性数据结构-树
树在计算机科学的各个领域中被广泛应用-操作系统，图形学，数据库系统，计算机网络。生物分类树：层次化-越接近顶层越普遍，越接近底层越独特。一个节点的子节点与另一个节点的子节点相互之间是隔离、独立的，如不同对象共同的属性。HTML文档的嵌套标记就是树结构的应用，域名体系也是树结构的应用。
树结构相关术语
节点Node:使用键值作为节点的名称，Node还保存额外数据项
边Edge:另一个基础部分，每条边恰好连接两个节点，表示节点之间具有关联，边具有出入方向
每个节点（除根节点）恰有一条来自另一节点的入边
每个节点可以有多条连到其他节点的出边
根Root：
路径Path：
子节点和父节点：入边均来自于同一个节点的若干节点，成为这个节点的子节点。
兄弟节点Sibling:同一个父节点的节点之间
子树Subtree：一个节点和其所有子孙节点，以及相关边的集合
层级：从根节点到某节点边的数量
树中所有节点最大层级成为树的高度
定义1：树由若干节点以及两两连接的边组成
定义2：树是-空集；或者根节点及0或多个子树构成，每个子数的根到根节点具有边相连
树的嵌套列表实现
首先使用列表类型实现二叉树类型
用递归的嵌套列表实现二叉树，由具有3个元素的列表实现：第1个元素为根节点的值，第2个元素是左子树，第三个元素是右子树-形如【root,left,right】
嵌套列表法：
myTree=['a',['b'],['c',['d'],['e']]]
子树的结构与树相同，是一种递归数据结构
很容易扩展成多叉树，只需要增加列表元素即可
"""
定义一系列函数来辅助操作嵌套列表
BinaryTree-创建仅有根节点的二叉树
inserLeft-将新节点插入树中作为直接的左右节点
get/setRootVal-取得返回根节点
getLeft/RightChild-返回左右子树
"""
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,[],[]])
return root
def insertRight(root,newBranch):
t=root.pop(2)
if len(t)>1:
root.insert(2,[newBranch,[],t])
else:
root.insert(2,[newBranch,[],[]])
return root
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]
r=BinaryTree(3)
insertLeft(r,4)
insertLeft(r,5)
insertRight(r,6)
insertRight(r,7)
l=getLeftChild(r)
print(l)
节点链接法实现二叉树
每个节点保存根节点的数据项，以及指向左右子树的链接
定义一个binaryTree类-成员key保存根节点数据项，成员left/right保存指向左右子树的引用
class BinaryTree:
def __init__(self,rootObj):
self.key=rootObj
self.rightChild=None#BinaryTree对象的引用
self.leftChild=None
def insertLeft(self,newNode):
if self.leftChild==None:
self.leftChild=BinaryTree(newNode)
else:
t=BinaryTree(newNode)
t.leftChild=sekf.leftChild
self.leftChild=t
def insertRight(self,newNode):
if self.rightChild==None:
self.rightChild=BinaryTree(newNode)
else:
t=BinaryTree(newNode)
t.rightChild=self.rightChild
self.rightChild=t
def getRootVal(self):
return self.key
def setRootVal(self,Obj):
self.key=Obj
def getLeftChild(self):
return self.leftChild
def getRightChild(self):
return self.rightChild
r=BinaryTree('a')
r.insertLeft('b')
r.getLeftChild().setRootVal('c')
树结构的应用-语法树
将树用于表示语言中句子，可以分析句子的各种语法成分，对句子的各种成分进行处理
程序设计语言的编译-从语法树生成目标代码的编译过程
表达式表示为树结构，操作数叶节点，操作符内部节点，越底层的表达谁计算优先级越高
用全括号表达式构建表达式解析树
利用表达式解析树对表达式求职
从表达式解析树恢复原表达式的字符串形式
首先，全括号表达式要分解为单词Token列表，其单词分为括号”()“，操作符”+-/*“和操作数”0-9“这几类
创建流程，当前节点的移动-遇到左括号，创建左子节点，当前节点下降，右括号，上升到父节点
操作符-当前节点值设为操作符，创建右子节点并移动当前节点至右节点
"""
创建左右子树-insetLeft/Right
设置当前节点值-setRootVal
下降到左右子树-getLeft/RightChild
上升到父节点-没有方法支持？使用栈来记录父节点位置-每当下降，下降前的位置push入栈，反之pop
"""
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)#stack中的tree类值会随之改变
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
对此二叉树求值，使用递归算法，定义求值递归函数evaluate
调用自身，左右子树求值，父节点操作符
"""
Python operator库,将操作符引入为函数对象，增加代码可读性
"""
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()
对此二叉树遍历
以递归的方式访问树。1 前序遍历 preorder：先访问根节点，再递归地前序访问左子树
最后前序访问右子树
2中序遍历,递归地访问左子树-根节点-右子树
后续遍历-递归访问左子树-右子树-根节点 postorder
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.leftChild.predorder()
if self.rightChild:
self.rightChild.preorder()
中序遍历递归算法生成全括号中缀表达式
def printexp(tree):
sVal=""
if tree:
sVal='('+printexp(tree.getLeftChild())
sVal=sVal+str(tree.getRootVal())
sVal=sVal+printexp(tree.getRightChild())+')'
return sVal
队列的变体-优先队列Priority Queue
VIP客户插队，操作系统中关键任务优先等
优先队列的出队和队列一样从队首出队，但在优先队列内部，数据项的次序由优先级决定
因此，优先队列的重点在于入队的时候确定正确的顺序，O(n)?
使用二叉堆数据结构是一种经典方案-将入队出队都保持在O(log n)
二叉堆逻辑上像二叉树，但却是用非嵌套的列表来实现的
"""
定义二叉堆对象的操作
BinaryHeap()空对象创建
insert(k)新key插入堆中
findMin()返回堆中最小项，最小项仍保留在堆中
delMin()返回堆中最小项并删除之
isEmpty()
size()
buildHeap(list)从一个key列表创建新堆
为了使堆操作能保持在对数水平上，就必须采用二叉树结构，且二叉树最好是平衡的-左右子树拥有相同数量的节点
定义【完全二叉树】：叶节点最多出现在最底层和次底层，而且最底层的叶节点都连续集中在最左边，每个内部节点都有两个子节点，最多可有1个节点例外
使用非嵌套列表实现，节点下标p，左子节点2p，右子节点2p+1，父节点p//2[1开始的下标]。
因此，任何一个节点，父节点的key值小于其key值，路径皆为已排序数列。这就是堆次序。
"""
二叉堆操作的实现
class BinHeap:
def __init__(self):
self.heapList=[0]
self.currentSize=0
#新key加入列表末尾，会影响路径上节点-上浮直到正确位置
def percUp(self,i):
while i//2 >0:#依次与父节点比较直到根节点
if self.heapList[i]<self.heapList[i//2]:#值小于父节点则交换值
tmp=self.heapList[i//2]
self.heapList[i//2]=self.heapList[i]
self.heapList[i]=-tmp
i=i//2
def insert(self,k):
self.heapList.append(k)
self.currentSize=self.currentSize+1
self.percUp(self.currentSize)
#delMin()将最后一个节点移动到根节点-再调整顺序，保持完全二叉树的性质-下沉方法
#左还是右？找更小的。
def delMin(self):
retval=self.heapList[1]
self.heapList[1]=self.heapList[self.currentSize]
self.currentSize-=1
self.heapList.pop()
self.percDown(1)
return retval
#buildHeap(list)逐个insert的话O(nlogn),用下沉法可以O(n)
def buildHeap(self,alist):
i=len(alist)//2#因为叶节点不需要下沉
self.currentSize=len(alist)
self.heapList=[0]+alist[:]
print(len(self.heapList),i)
while (i>0):
print(self.heapList,i)
self.percDown(i)
i=i-1
print(self.heapList,i)
