第 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二叉搜索树的功能定义

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 == 0

2.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, parent

2.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 += 1

2.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 current

2.6.10二叉树的遍历

1)深度优先

深度优先搜索（DFS，Depth 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)层序遍历

广度优先搜索（BFS，Breadth First Search）从起始节点开始，首先访问该节点的所有子节点，然后再访问子节点的子节点，依此类推，逐层访问节点。

广度优先搜索一般使用队列实现，每访问一个节点，就将该节点的子节点添加进队列中。

3)代码实现

def for_each(self, func, order="inorder"): """遍历树，默认中序遍历""" 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, order="inorder"): """遍历树，默认中序遍历""" 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, order="preorder") # 3 # 1 6 # N 2 5 7 # 3 # 1 # 2 # 6 # 5 # 7