第 2 章 常用数据结构2.6 树用链表/数组解决2.6.1 树的概述树Tree由一系列具有层次关系的节点Node组成。树的常见术语父节点节点的上层节点。子节点节点的下层节点。根节点位于树的顶端没有父节点的节点。叶节点位于树的底端没有子节点的节点。边连接两个节点的线段。节点的度节点的子节点数量。节点的层从根开始定义起根为第1层根的子节点为第2层以此类推。节点的深度从根节点到该节点所经过的边的数量根的深度为0。节点的高度从距离该节点最远的叶节点到该节点所经过的边的数量所有叶节点的高度为0。树的深度高度从根节点到最远叶节点所经过的边的数量。2.6.2二叉树简介树形结构中最具代表性的一种就是二叉树Binary Tree。二叉树规定每个节点最多只能有两个子节点两个子节点分别被称为左子节点和右子节点。以左子节点为根节点的子树被称为左子树以右子节点为根节点的子树被称为右子树。2.6.3二叉树存储结构1) 二叉树的数组存储采用数组结构存储二叉树访问与遍历速度较快。但不适合存储数据量过大的树且增删效率较低而且树中存在大量None的情况下空间利用率较低因此不是主流方式。2)二叉树的链表存储2.6.4 常见的二叉树1)完全二叉树完全二叉树只有最下面一层的节点未被填满且靠左填充。2)满二叉树满二叉树所有层的节点都被完全填满满二叉树也是一种完全二叉树。3)平衡二叉树平衡二叉树中任意节点的左右子树高度之差不超过1。4)二叉搜索树二叉搜索树中的每个节点的值大于其左子树中的所有节点的值并且小于右子树中的所有节点的值。5)AVL树AVL 树是一种自平衡的二叉搜索树插入和删除时会进行旋转操作来保证树的平衡性。6)红黑树红黑树是一种特殊的二叉搜索树除了二叉搜索树的要求外它还具有以下特性每个节点或者是黑色或者是红色。根节点是黑色。每个叶节点都是黑色。这里叶节点是指为空None的节点。红色节点的两个子节点必须是黑色的。即从每个叶到根的所有路径上不能有两个连续的红色节点。从任一个节点到其每个叶的所有路径上包含相同数目的黑色节点。7)堆堆Heap是一种满足特定条件的完全二叉树主要可分为两种类型大顶堆每个父节点的值都大于等于其子节点的值。根节点为树中的最大值。小顶堆每个父节点的值都小于等于其子节点的值。根节点为树中的最小值。8)霍夫曼树霍夫曼树又称最优二叉树是一种带权路径长度最短的二叉树通常用于数据压缩它的构建基于字符出现频率的概率。9)B树B树是一种自平衡的多路查找树。虽然它不是严格意义上的二叉树但与二叉树的结构类似。经常用于数据库、文件系统等需要磁盘访问的应用。10)B树B树是B树的优化版本。它通过将数据集中存储在叶子节点并通过链表连接来实现高效的范围查询并且非叶子节点仅存储索引提高了磁盘利用率。2.6.5二叉搜索树的功能定义方法说明size()返回树中节点个数is_empty()判断树是否为空search(item)查找节点是否存在add(item)向二叉搜索树中插入节点remove(item)从二叉搜索树中删除节点for_each(func, order)按指定方式遍历二叉树2.6.6二叉树的创建from collections import deque #队列 class Node: 二叉树节点 def __init__(self, data): self.data data self.left None self.right None class BinarySearchTree: 二叉搜索树 def __init__(self): 初始化二叉树 self.__root None self.__size 0 def print_tree(self): 打印树的结构 # 先得到树的层数 def get_layer(node): 递归计算树的层数 if node is None: return 0 else: left_depth get_layer(node.left) #递归 right_depth get_layer(node.right) return max(left_depth, right_depth) 1 layer get_layer(self.__root) #总层级 # 层序遍历并打印 queue deque([(self.__root, 1)]) current_level 1 while queue: node, level queue.popleft() if level current_level: print() current_level 1 if node: print(f{node.data:^{20*layer//2**(level-1)}}, end) else: print(f{N:^{20*layer//2**(level-1)}}, end) if level layer: if node: queue.append((node.left, level 1)) queue.append((node.right, level 1)) else: queue.append((None, level 1)) queue.append((None, level 1)) print() property def size(self): 返回树中节点的个数 return self.__size def is_empty(self): 判断树是否为空 return self.__size 02.6.7二叉搜索树的查找操作查找时先与当前节点比较大小等于则找到了目标节点小于则向左子节点查找大于则向右子节点查找。如果查找到None仍未找到则说明该节点不在树中。后续插入与删除操作也会用到查找所以此处提供一个__search_pos()方法返回查找到的节点和其父节点供后续使用。def search(self, item): 查找节点是否存在 return self.__search_pos(item)[0] is not None def __search_pos(self, item): 查找节点返回(节点,父节点)。如果节点不存在则为None此时父节点为一个叶节点 parent None current self.__root while current: if item current.data: break parent current current current.left if item current.data else current.right return current, parent2.6.8二叉搜索树的插入操作插入时先执行查找操作查找时保存当前节点的父节点。如果找到了节点则说明树中已有此元素退出。如果找到了None应将该元素插入到对应的节点下。def add(self, item): 插入节点 node Node(item) if self.is_empty(): self.__root node else: current, parent self.__search_pos(item) # 如果节点之前已存在则返回 if current: return # 如果节点之前不存在则插入父节点的左节点或右节点 if parent.data item: parent.left node else: parent.right node self.__size 12.6.9二叉搜索树的删除操作需要保证删除节点后仍然保证二叉搜索树的性质。删除操作需要根据目标节点的子节点数量为0、1、2分三种情况。1) 目标节点的子节点数量为0直接删除目标节点。2)目标节点的子节点数量为1将目标节点替换为其子节点。3)目标节点的子节点数量为2使用目标节点的右子树最小节点、或左子树最大节点替换目标节点。4)代码实现def remove(self, item): 删除节点 current, parent self.__search_pos(item) if not current: return # 如果删除的是叶节点没有子节点 if not current.left and not current.right: if parent: if parent.left current: parent.left None else: parent.right None else: # 如果没有父节点说明是根节点 self.__root None # 如果删除的节点只有一个子节点 elif not current.left or not current.right: child current.left if current.left else current.right if parent: if parent.left current: parent.left child else: parent.right child else: # 如果没有父节点说明是根节点 self.__root child # 如果删除的节点有两个子节点 else: # 找到中序后继右子树中最小的节点 successor self.__get_min(current.right) successor_data successor.data # 删除中序后继节点 self.remove(successor_data) #删除原本17位置的节点,调用自身,size已减1,所以这里还要1 # 因为current知识把值替换没有删除 self.__size 1 # 用中序后继的值替代当前节点 current.data successor_data self.__size - 1 #找到17 def __get_min(self, node): 找到当前子树的最小节点 current node while current.left: current current.left return current2.6.10二叉树的遍历1)深度优先深度优先搜索DFSDepth First Search尽可能地深入每一个分支直到不能再深入为止然后回溯到上一个节点继续尝试其他的分支。(1)前序遍历先访问当前节点再访问节点的左子树再访问节点的右子树。def dfs(node): 前序遍历 if node is None: return print(node) # 访问当前节点 dfs(node.left) # 访问节点的左子树 dfs(node.right) # 访问节点的右子树(2)中序遍历先访问节点的左子树再访问当前节点再访问节点的右子树。二叉搜索树中序遍历的结果是有序的。def dfs(node): 中序遍历 if node is None: return dfs(node.left) # 访问节点的左子树 print(node) # 访问当前节点 dfs(node.right) # 访问节点的右子树(3)后续遍历先访问节点的左子树再访问节点的右子树再访问当前节点。def dfs(node): 后序遍历 if node is None: return dfs(node.left) # 访问节点的左子树 dfs(node.right) # 访问节点的右子树 print(node) # 访问当前节点2)广度优先(1)层序遍历广度优先搜索BFSBreadth First Search从起始节点开始首先访问该节点的所有子节点然后再访问子节点的子节点依此类推逐层访问节点。广度优先搜索一般使用队列实现每访问一个节点就将该节点的子节点添加进队列中。3)代码实现def for_each(self, func, orderinorder): 遍历树默认中序遍历 match order: case inorder: self.__inorder_traversal(func) case preorder: self.__preorder_traversal(func) case postorder: self.__postorder_traversal(func) case levelorder: self.__levelorder_traversal(func) def __inorder_traversal(self, func): 深度优先搜索中序遍历 def inorder(node): if node: inorder(node.left) func(node.data) inorder(node.right) inorder(self.__root) def __preorder_traversal(self, func): 深度优先搜索前序遍历 def preorder(node): if node: func(node.data) preorder(node.left) preorder(node.right) preorder(self.__root) def __postorder_traversal(self, func): 深度优先搜索后序遍历 def postorder(node): if node: postorder(node.left) postorder(node.right) func(node.data) postorder(self.__root) def __levelorder_traversal(self, func): 广度优先搜索层序遍历 queue deque() queue.append(self.__root) while queue: node queue.popleft() func(node.data) if node.left: queue.append(node.left) if node.right: queue.append(node.right)2.6.11完整代码from collections import deque #队列 class Node: 二叉树节点 def __init__(self, data): self.data data self.left None self.right None class BinarySearchTree: 二叉搜索树 def __init__(self): 初始化二叉树 self.__root None self.__size 0 def print_tree(self): 打印树的结构 # 先得到树的层数 def get_layer(node): 递归计算树的层数 if node is None: return 0 else: left_depth get_layer(node.left) right_depth get_layer(node.right) return max(left_depth, right_depth) 1 layer get_layer(self.__root) # 层序遍历并打印 queue deque([(self.__root, 1)]) current_level 1 while queue: node, level queue.popleft() if level current_level: print() current_level 1 if node: print(f{node.data:^{20*layer//2**(level-1)}}, end) else: print(f{N:^{20*layer//2**(level-1)}}, end) if level layer: if node: queue.append((node.left, level 1)) queue.append((node.right, level 1)) else: queue.append((None, level 1)) queue.append((None, level 1)) print() property def size(self): 返回树中节点的个数 return self.__size def is_empty(self): 判断树是否为空 return self.__size 0 def search(self, item): 查找节点是否存在 return self.__search_pos(item)[0] is not None def __search_pos(self, item): 查找节点返回(节点,父节点)。如果节点不存在则为None此时父节点为一个叶节点 parent None current self.__root while current: if item current.data: break parent current current current.left if item current.data else current.right return current, parent def add(self, item): 插入节点 node Node(item) if self.is_empty(): self.__root node else: current, parent self.__search_pos(item) # 如果节点之前已存在则返回 if current: return # 如果节点之前不存在则插入父节点的左节点或右节点 if parent.data item: parent.left node else: parent.right node self.__size 1 def remove(self, item): 删除节点 current, parent self.__search_pos(item) if not current: return # 如果删除的是叶节点没有子节点 if not current.left and not current.right: if parent: if parent.left current: parent.left None else: parent.right None else: # 如果没有父节点说明是根节点 self.__root None # 如果删除的节点只有一个子节点 elif not current.left or not current.right: child current.left if current.left else current.right if parent: if parent.left current: parent.left child else: parent.right child else: # 如果没有父节点说明是根节点 self.__root child # 如果删除的节点有两个子节点 else: # 找到中序后继右子树中最小的节点 successor self.__get_min(current.right) successor_data successor.data # 删除中序后继节点 self.remove(successor_data) # 因为current知识把值替换没有删除 self.__size 1 # 用中序后继的值替代当前节点 current.data successor_data self.__size - 1 def __get_min(self, node): 找到当前子树的最小节点 current node while current.left: current current.left return current def for_each(self, func, orderinorder): 遍历树默认中序遍历 match order: case inorder: self.__inorder_traversal(func) case preorder: self.__preorder_traversal(func) case postorder: self.__postorder_traversal(func) case levelorder: self.__levelorder_traversal(func) def __inorder_traversal(self, func): 深度优先搜索中序遍历 def inorder(node): if node: inorder(node.left) func(node.data) inorder(node.right) inorder(self.__root) def __preorder_traversal(self, func): 深度优先搜索前序遍历 def preorder(node): if node: func(node.data) preorder(node.left) preorder(node.right) preorder(self.__root) def __postorder_traversal(self, func): 深度优先搜索后序遍历 def postorder(node): if node: postorder(node.left) postorder(node.right) func(node.data) postorder(self.__root) def __levelorder_traversal(self, func): 广度优先搜索层序遍历 queue deque() queue.append(self.__root) while queue: node queue.popleft() func(node.data) if node.left: queue.append(node.left) if node.right: queue.append(node.right)if __name__ __main__: tree BinarySearchTree() tree.add(3) tree.add(1) tree.add(6) tree.add(2) tree.add(5) tree.add(7) tree.print_tree() tree.for_each(print, orderpreorder) # 3 # 1 6 # N 2 5 7 # 3 # 1 # 2 # 6 # 5 # 7