python数据结构实现（五）
1. 二叉树1.1 实现一个二叉查找树，并且支持插入、删除、查找操作1.2 实现查找二叉查找树中某个结点的后继、前驱结点1.2.1 python实现查找二叉查找树中某个结点的前驱结点1.2.2 python实现查找二叉查找树中某个结点的后继结点
1.3 实现二叉树前、中、后序以及按层遍历1.3.1 二叉树前序遍历1.3.2 二叉树中序遍历1.3.3 二叉树后序遍历1.3.4 二叉树层次遍历
1.4 LeetCode相关习题1.4.1 Invert Binary Tree（翻转二叉树）1.4.2 Maximum Depth of Binary Tree（二叉树的最大深度）1.4.3 Validate Binary Search Tree（验证二叉查找树）1.4.4 python实现二叉树层次遍历(102,107)1.4.5 python实现二叉树层次遍历(107)
2. 堆2.1 实现小顶堆，大顶堆2.2 实现堆排序2.3 求一组动态数据集合的最大 Top K2.4 LeetCode相关习题2.4.1 路径总和
1. 二叉树
1.1 实现一个二叉查找树，并且支持插入、删除、查找操作
class Node:
def __init__(self, value, lchild=None, rchild=None):
self.data = value
self.lchild = lchild
self.rchild = rchild
class BSTree:
def __init__(self, value):
self.root = Node(value)
def insert(self, value):
'''
插入值为value的结点
二叉排序树插入的结点一定为叶子结点
'''
node = Node(value)
p = self.root; pre = None
while p:
pre = p
if p.data > value:
p = p.lchild
elif p.data < value:
p = p.rchild
else:
break
if p == None: # 当该结点不存在于当前的二叉排序树中，插入结点
if pre.data > value:
pre.lchild = node
else:
pre.rchild = node
def find(self, value):
p = self.root
while p:
if p.data > value:
p = p.lchild
elif p.data < value:
p = p.rchild
else:
print('已找到该结点')
break
if p == None:
raise Exception('value error: %d do not exist in BSTree ' % value)
return p
def findParent(self, target):
'''
查找二叉排序树中目标结点的父结点
:param bstree: 二叉排序树的根结点
:param target: 目标结点
'''
p = self.root; pre = None
while p:
if target.data < p.data:
pre = p
p = p.lchild
elif target.data > p.data:
pre = p
p = p.rchild
else:
if p is target:
break
else:
pre = p
# 目标结点为中序序列的后一个相邻结点，故在右子树中
p = p.rchild
if p == None:
raise Exception('value error: %d do not exist in bstree' % value)
else:
return pre
def remove(self, node, value):
'''
删除二叉排序树中值为value的结点
目标结点p的位置可能有以下三种情况：
1) p为叶子结点：直接删除即可
2) p有左子树或右子树其中之一：删除p，p的父结点连接到p的子树
3) p同时有左右子树：选中序序列中与p相邻的两个结点之一覆盖p结点，
再依据1)或2)删除该结点
'''
p = node; pre = None
while p:
if p.data > value:
pre = p
p = p.lchild
elif p.data < value:
pre = p
p = p.rchild
else: # 找到待删结点之后进行的操作
if p.lchild and p.rchild: # 情况3)要删除的结点
temp = p.rchild
while temp.lchild:
temp = temp.lchild
p.data = temp.data # 找到中序序列后一个结点temp覆盖待删结点p
'''
以下在二叉排序树中找到temp结点并删除（由于此时有两个相同值的结点，
故在查找时还需用地址进行比较（findParent（target）中））
temp结点只有两种可能：
1)叶子结点
2)只有右子树
'''
if temp.lchild == None and temp.rchild == None: # 情况1)待删结点为叶子结点
self._removeLeaf(temp)
break
else: # 情况2)待删结点只有右子树
parentTemp = self.findParent(temp)
self._changeChild(parentTemp, temp, temp.rchild)
elif p.lchild: # 情况2)待删结点只有左子树
self._changeChild(pre, p, p.lchild)
break
elif p.rchild: # 情况2)待删结点只有右子树
self._changeChild(pre, p, p.rchild)
break
else: # 情况1)待删结点为叶子结点
self._removeLeaf(p)
break
def _changeChild(self, parent, preChild, afterChild):
if parent.lchild == preChild:
parent.lchild = afterChild
print('remove success')
else:
parent.rchild = afterChild
print('remove success')
def _removeLeaf(self, leaf):
parent = self.findParent(leaf)
if parent == None: # 待删结点为二叉排序树的唯一结点
self.root = None
else:
if parent.lchild and parent.lchild.data == leaf.data:
parent.lchild = None
else:
parent.rchild = None
1.2 实现查找二叉查找树中某个结点的后继、前驱结点
1.2.1 python实现查找二叉查找树中某个结点的前驱结点
def findParent(bstree, value):
'''
查找二叉排序树中值为value的结点的前驱结点
:param bstree: 二叉排序树的根结点
:param value: 目标结点的值
'''
p = bstree; pre = None
while p:
if value < p.data:
pre = p
p = p.lchild
elif value > p.data:
pre = p
p = p.rchild
else:
break
if p == None:
raise Exception('value error: %d do not exist in bstree' % value)
else:
return pre.data
1.2.2 python实现查找二叉查找树中某个结点的后继结点
def findPost(bstree, value):
'''
查找二叉排序树中值为value的结点的后继结点
:param bstree: 二叉排序树的根结点
:param value: 目标结点的值
'''
p = bstree
while p:
if value < p.data:
p = p.lchild
elif value > p.data:
p = p.rchild
else:
break
if p == None:
raise Exception('value error: %d do not exist in bstree' % value)
elif p.lchild and p.rchild:
return p.lchild.data, p.rchild.data
else:
re = p.lchild if p.lchild else p.rchild
return re.data
1.3 实现二叉树前、中、后序以及按层遍历
1.3.1 二叉树前序遍历
def preOrder(bt):
if bt:
print(bt.data)
preOrder(bt.lchild)
preOrder(bt.rchild)
1.3.2 二叉树中序遍历
def inOrder(bt):
# 中序遍历
if bt:
inOrder(bt.lchild)
print(bt.data)
inOrder(bt.rchild)
1.3.3 二叉树后序遍历
def postOrder(bt):
# 后序遍历
if bt:
postOrder(bt.lchild)
postOrder(bt.rchild)
print(bt.data)
1.3.4 二叉树层次遍历
class Queue:
# 定义一个循环队列
def __init__(self, capacity=10):
self.front = 0
self.rear = 0
self.data = [None] * capacity
self.size = 0
self.maxsize = capacity
def enQueue(self, node):
self.rear = (self.rear + 1) % self.maxsize
self.data[self.rear] = node
self.size += 1
def deQueue(self):
self.front = (self.front + 1) % self.maxsize
self.size -= 1
return self.data[self.front]
def levelOrder(bt):
queue = Queue()
queue.enQueue(bt)
while queue.size != 0:
q = queue.deQueue()
print(q.data,end=' ')
if q.lchild:
queue.enQueue(q.lchild)
if q.rchild:
queue.enQueue(q.rchild)
1.4 LeetCode相关习题
1.4.1 Invert Binary Tree（翻转二叉树）
class Solution:
def invertTree(self, root: TreeNode) -> TreeNode:
if root:
root.left, root.right = root.right, root.left
self.invertTree(root.left)
self.invertTree(root.right)
return root
1.4.2 Maximum Depth of Binary Tree（二叉树的最大深度）
class Solution:
def maxDepth(self, root: TreeNode) -> int:
if root == None:
return 0
else:
leftdepth = self.maxDepth(root.left)
rightdepth = self.maxDepth(root.right)
depth = leftdepth if leftdepth > rightdepth else rightdepth
return depth + 1
1.4.3 Validate Binary Search Tree（验证二叉查找树）
递归遍历每个结点，每个结点都有它应该符合的上下限： 左子树的结点：大于负无穷小于父结点 右子树的结点：小于正无穷大于父结点
import sys
from functools import lru_cache
class Solution:
lru_cache(10**8)
def isValidBST(self, root: TreeNode) -> bool:
def helper(node, lower, upper):
if node == None:
return True
if node.val > lower and node.val < upper:
return helper(node.left, lower, node.val) and helper(node.right, node.val, upper)
else:
return False
return helper(root, float('-inf'), float('inf'))
1.4.4 python实现二叉树层次遍历(102,107)
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
if root:
res = []
level = [root]
while level:
temp1 = []
for _ in level:
temp1.append(_.val)
res.append(temp1)
temp2 = []
for n in level:
if n.left:
temp2.append(n.left)
if n.right:
temp2.append(n.right)
level = temp2
return res
else:
return []
1.4.5 python实现二叉树层次遍历(107)
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def levelOrderBottom(self, root: TreeNode) -> List[List[int]]:
if root:
res = []
level = [root]
while level:
temp1 = []
for _ in level:
temp1.append(_.val)
res.append(temp1)
temp2 = []
for n in level:
if n.left:
temp2.append(n.left)
if n.right:
temp2.append(n.right)
level = temp2
res.reverse()
return res
else:
return []
2. 堆
2.1 实现小顶堆，大顶堆
# 小顶堆
def smallerAdjust(arr, low, high):
# 向下调整arr数组low位置上的元素
temp = arr[low]
i = low; j = 2 * i
while i < j and j < high:
if arr[j] > arr[j+1]:
j += 1
if temp > arr[j]:
arr[i] = arr[j]
i = j; j = 2 * i
else:
break
arr[i] = temp
def smallerHeap(arr):
length = len(arr)
for i in range(length//2 : -1 : -1):
smallerAdjust(arr, i, length-1)
# 大顶堆
def biggerAdjust(arr, low, high):
# 向下调整arr数组low位置上的元素
temp = arr[low]
i = low; j = 2 * i
while i < j and j < high:
if arr[j] < arr[j+1]:
j += 1
if temp < arr[j]:
arr[i] = arr[j]
i = j; j = 2 * i
else:
break
arr[i] = temp
def biggerHeap(arr):
length = len(arr)
for i in range(length//2 : -1 : -1):
biggerAdjust(arr, i, length-1)
2.2 实现堆排序
'''
堆可以看做是一棵完全二叉树，这里使用大顶堆，则该完全二叉树的根结点即为最大值。
堆排序的基本思想：
将初始序列按照顺序写出其完全二叉树形式，对所有的非叶子节点从下往上，从右往左依次做调整（要求以其为根结点的二叉树也是大顶堆），建堆完毕；
此时根结点为最大值，将其与最后一个结点交换，则最大值到达其最终位置，之后继续对二叉树剩下的结点做同样的调整（此时只有刚换上去的根结点需要调整）
'''
def adjust(arr, low, high):
# 向下调整k位置上的结点
i = low; j = 2*i;
temp = arr[low]
while i <= j and j < high:
if arr[j] < arr[j+1]: # 将左右结点中最大的结点当做arr[j]
j += 1
if arr[j] > temp:
arr[i] = arr[j]
i = j; j = 2*i # 循环做对下一个根结点的调整
else:
break
arr[i] = temp # 存于最终位置
def heapSort(arr):
length = len(arr)
for i in range(length//2,-1,-1): # 建堆
adjust(arr, i ,length-1)
for index in range(length-1, -1, -1): # 将根结点与每一趟的最后一个结点交换,再调整
arr[index], arr[0] = arr[0], arr[index] # 该趟最大值已到最终位置
adjust(arr, 0, index-1) # 新一轮的调整
2.3 求一组动态数据集合的最大 Top K
# 利用大顶堆结构求出数组中的top K个值
# 大顶堆
def biggerAdjust(arr, low, high):
# 向下调整arr数组low位置上的元素
temp = arr[low]
i = low; j = 2 * i
while i <= j and j < high:
if arr[j] < arr[j+1]:
j += 1
if temp < arr[j]:
arr[i] = arr[j]
i = j; j = 2 * i
else:
break
arr[i] = temp
def topK(arr, k):
length = len(arr)
for i in range(length//2,-1,-1): # 初始堆
biggerAdjust(arr, i, length-1)
re, end = [], length-1
for i in range(k):
re.append(arr[0])
arr[0] = arr[end]
end -= 1
biggerAdjust(arr, 0, end)
return re
2.4 LeetCode相关习题
2.4.1 路径总和
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def hasPathSum(self, root: TreeNode, sum: int) -> bool:
if not root:
return False
if sum == root.val and (not root.left and not root.right):
return True
else:
return self.hasPathSum(root.left, sum-root.val) or \
self.hasPathSum(root.right, sum-root.val)
