树
定义
- 节点Node：key
- 边Edge：链接两个节点
- 根节点Root：没有入边
- 路径Path：由边依次相连
- 子节点children：入边来自同一个节点（父节点Parent），他们之间称作兄弟节点
- 子树subtree：一个节点及其所有子孙节点和相关的边
- 叶节点leaf：没有子节点
- 层级level：从根节点开始到达一个节点的路劲所包含的边的数量
- 高度=最大层级
二叉树
每个节点最多有两个子节点
数的定义
普通 or 递归
嵌套实现一个二叉树
def BinaryTree(r):
return [r,[],[]] # 创建二叉树，仅有跟节点
def insertLeft(root,newbranch):
t = root.pop(1) # 把原先的左子树pop出来
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
# 建立一个实例
mytree = BinaryTree(3)
insertLeft(mytree,5)
insertRight(mytree,1)
insertRight(mytree,6)
print(mytree)
[3, [5, [], []], []]
[3, [5, [], []], [1, [], []]]
[3, [5, [], []], [6, [], [1, [], []]]]
[3, [5, [], []], [6, [], [1, [], []]]]
用链实现一个二叉树
每一个方块，有一个数据项
class BinaryTree:
def __init__(self, rootObj):
self.key=rootObj
self.leftchild = None
self.rightchild = None
def insertleft(self,newnode):
if self.leftchild == None:
self.leftchild = BinaryTree(newnode)
else:
t = BinaryTree(newnode)
t.leftchild = self.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 getRightchild(self):
return self.rightchild
def getLeftchild(self):
return self.leftchild
def setRoot(self,obj):
self.key = obj
def getRoot(self):
return self.key
r = BinaryTree('a')
r.insertleft('b')
r.insertright('c')
r.getRightchild().insertright('d')
r.getRightchild().getRoot()
r.getRightchild().getRightchild().getRoot()
'c'
'd'
树的应用——表达式解析
-
每个子树都表示一个子表达式
-
下面：1.构建表达式解析树，2.并求值，3.从表达式解析树恢复表达式的字符串形式
构建表达式解析树
首先，全括号表达式分解为括号、操作符和 数
- 如果是（：为当前添加一个新的左子节点，当前节点下降
- 如果是操作符：为当前添加一个新右子节点，当前节点下降
- 如果是数字：设置当前节点，并且当前节点上升到父节点
- 如果是）：当前节点上升到父节点
但是： 上升到父节点没有方法支持，如何做到？
- 用一个栈来记录跟踪父节点
- 下降时，把下降前的节点push入栈，需要上升时候pop出来
def build_parsetree(fpexp):
fplist = list(fpexp) # 把字符串切割
eTree = BinaryTree(' ') # 初始化tree
pStack =[] # 初始化一个栈
pStack.append(eTree) # 入栈
currentTree = eTree # 定义当前tree
for i in fplist:
if i=="(":
currentTree.insertleft(' ') # 添加一个新的左子节点
pStack.append(currentTree) # 下降前的节点push进栈
currentTree = currentTree.getLeftchild() # 下降到左子节点
elif i not in ['+',"-","*","/",")"] : # 如果是数字
currentTree.setRoot(int(i)) # 设置为节点值
currentTree = pStack.pop(0) # 上升为父节点
elif i in ['+','-','*',"/"]:
currentTree.setRoot(i)
currentTree.insertright(' ')
pStack.append(currentTree)
currrentTree = currentTree.getRightchild()
elif i ==")":
currentTree = pStack.pop(0)
else:
raise ValueError
return eTree
求值——递归
- 结束条件：叶节点
- 缩小：分为左子树右子树
- 调用自身：根据根节点计算
import operator
def evaluate(parseTree):
opers = {'+':operator.add, '-':operator.sub, '/':operator.truediv,'*':operator.mul} # 操作符
leftT = parseTree.getLeftchild()
rightT = parseTree.getRightchild()
if leftT and rightT: # 空的说明是叶节点
fn = opers[parseTree.getRoot()]
return fn(evaluate(leftT), evaluate(rightT)) # 递归
else:
return parseTree.getRoot()
树的遍历——递归
def preorder(tree): # 前序
if tree:
print (tree.getRoot())
preorder(tree.getLeftchild())
preorder(tree.getRightchild())
优先队列——二叉堆实现
优先队列入队时候：根据其优先级尽可能挤到前方
- 二叉堆：优先队列出入队复杂度保持在o(logn)
堆次序
- 任何一个节点x，父节点p中的key均小于x中的key（任何一条路劲都是排序好的数列）
from IPython.display import Image
from IPython.core.interactiveshell import InteractiveShell
InteractiveShell.ast_node_interactivity = "all"
Image(filename = 'Desktop/快乐研一/python/ercha2.jpg', width=300, height=300)
Image(filename = 'Desktop/快乐研一/python/erchadui1.jpg', width=300, height=300)
Image(filename = 'Desktop/快乐研一/python/erchadui2.jpg', width=300, height=300)
class BinHeap:
def __init__(self):
self.heapList=[0] # 把下表为0的填起来，无用，方便后面下标整数乘除法
self.currentSize = 0
def percUp(self,i): # 上浮
while i//2>0:
if self.heapList[i]<self.heapList[i//2]: # 如果比父节点大——交换
self.heapList[i], self.heapList[i//2]= self.heapList[i//2], self.heapList[i]
i = i//2
def insert(self,k):
self.heapList.append(k)
self.currentSize +=1
self.percUp(self.currentSize) # 对这个新增节点进行“上浮”操作
def minchild(self,i):
if i*2+1>self.currentSize: return i*2 # 如果只有左子节点，直接输出
else:
if self.heapList[i*2]<self.heapList[i*2+1]: # 否则对比输出较大的
return i*2
else: return i*2+1
def percDown(self,i):
while i*2<=self.currentSize:
minc = self.minchild(i) # 最小的子节点的位置
if self.heapList[i]>self.heapList[minc]:
self.heapList[i],self.heapList[minc] = self.heaplist[minc],self.heapList[i]
i = minc # 下沉后继续判断
def delMin(self): # 删除根节点后，把最后一位移到根节点，然后做下沉
self.heapList[1] = self.heapList[self.currentSize]
self.currentSize -=1
self.heapList.pop()
self.percDown(1)
### heapq库是专门处理最小堆的库
import heapq
nums = [7, 2, 11, 5, 1, 54, 23]
heapq.heapify(nums)
nums
heapq.heappush(nums, 3)
nums
print([heapq.heappop(nums) for _ in range(len(nums))])
[1, 2, 11, 5, 7, 54, 23]
[1, 2, 11, 3, 7, 54, 23, 5]
[1, 2, 3, 5, 7, 11, 23, 54]
有一堆石头，每块石头的重量都是正整数。
每一回合，从中选出两块 最重的 石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：
如果 x == y，那么两块石头都会被完全粉碎；
如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。
最后，最多只会剩下一块石头。返回此石头的重量。如果没有石头剩下，就返回 0。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/last-stone-weight
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
def lastStone(stones) -> int:
if len(stones)==1:
return stones[0]
stones=[-i for i in stones] # 变成负数，方便pop出最大值
import heapq
heapq.heapify((stones)) # 引入二叉堆
while len(stones)>1:
max1 = -heapq.heappop(stones)
max2 = -heapq.heappop(stones)
if max1>max2: # 如果大小不等，还有剩， 否则没有剩
heapq.heappush(stones,max2-max1)
print([-i for i in stones])
if len(stones)==0:
return 0
else:
return -stones[0]
stones = [2,7,2,3,7,4,6,8]
lastStone(stones)
[7, 3, 6, 2, 2, 4, 1]
[4, 3, 1, 2, 2, 1]
[2, 2, 1, 1, 1]
[1, 1, 1]
[1]
1