二叉树的介绍
二叉树的节点代码
class TreeNode: def __init__(self, value) -> None: self.val = value self.left = None self.right = None
- 节点的「深度 depth」：从根节点到该节点所经过的边的数量。
- 节点的「高度 height」：从最远叶节点到该节点所经过的边的数量。
二叉树的类型
- 「完美二叉树 perfect binary tree」除了最底层外，其余所有层的节点都被完全填满。在完美二叉树中，叶节点的度为 0 ，其余所有节点的度都为 2 ；若树高度为 ℎ ，则节点总数为 2n+1−1 ，呈现标准的指数级关系，反映了自然界中常见的细胞分裂现象。
- 「完全二叉树 complete binary tree」只有最底层的节点未被填满，且最底层节点尽量靠左填充。
- 「完满二叉树 full binary tree」除了叶节点之外，其余所有节点都有两个子节点。
- 「平衡二叉树 balanced binary tree」中任意节点的左子树和右子树的高度之差的绝对值不超过 1 。
链表二叉树的遍历
层序遍历(广度优先遍历breadth‑first traversal) BFT/BFS
从顶部到底部逐层遍历二叉树，并在每一层按照从左到右的顺序访问节点。
from collections import deque def level_order(root): queue = deque() queue.append(root) res = [] while queue: node = queue.popleft() res.append(node.val) if node.left is not None: queue.append(node.left) if node.right is not None: queue.append(node.right) return res
前序、中序、后序遍历（深度优先遍历）DFT/DFS
- 前序:访问优先级：根节点 -> 左子树 -> 右子树
- 中序:访问优先级：左子树 -> 根节点 -> 右子树
- 后序:访问优先级：左子树 -> 右子树 -> 根节点
class TreeOrder: def __init__(self) -> None: self.res = [] def pre_order_need(self, root): if root is None: return None self.res.append(root.val) self.pre_order_need(root.left) self.pre_order_need(root.right) def pre_order(self, root): self.res = [] self.pre_order_need(root) def in_order_need(self, root): if root is None: return None self.in_order_need(root.left) self.res.append(root.val) self.in_order_need(root.right) def in_order(self, root): self.res = [] self.in_order_need(root) def post_order_need(self, root): if root is None: return None self.post_order_need(root.left) self.post_order_need(root.right) self.res.append(root.val) def post_order(self, root): self.res = [] self.post_order_need(root)
复杂度分析
- 时间复杂度 𝑂(𝑛) ：所有节点被访问一次，使用 𝑂(𝑛) 时间。
- 空间复杂度 𝑂(𝑛) ：在最差情况下，即树退化为链表时，递归深度达到 𝑛 ，系统占用 𝑂(𝑛) 栈帧空间。
数组二叉树的构造
class ArrayTree: def __init__(self, arr) -> None: self.__tree = list(arr) self.res = [] def size(self): return len(self.__tree) def val(self, ix): if ix < 0 or ix >= self.size(): return None else: return self.__tree[ix] def left(self, ix): return 2*ix + 1 def right(self, ix): return 2*ix + 2 def parent(self, ix): return (ix -1)//2 def level_order(self): self.res = [] for i in range(self.size()): if self.val(i) is not None: self.res.append(self.val(i)) return self.res def __dfs(self, ix, order): if self.val(ix) is None: return None if order == 'pre': self.res.append(self.val(ix)) self.__dfs(self.left(ix), order) if order == 'in': self.res.append(self.val(ix)) self.__dfs(self.right(ix), order) if order == 'post': self.res.append(self.val(ix)) def pre_order(self): self.res = [] self.__dfs(0, order='pre') return self.res def in_order(self): self.res = [] self.__dfs(0, order='in') return self.res def post_order(self): self.res = [] self.__dfs(0, order='post') return self.res lst = [1,2,3,4,None,6,7,8,9,None,None,12,None,None,15] tree = ArrayTree(lst) tree.level_order() tree.pre_order() tree.in_order() tree.post_order()
数组二叉树的优缺点
二叉树的数组表示主要有以下优点。
- 数组存储在连续的内存空间中，对缓存友好，访问与遍历速度较快。
- 不需要存储指针，比较节省空间。
- 允许随机访问节点。
然而，数组表示也存在一些局限性。 - 数组存储需要连续内存空间，因此不适合存储数据量过大的树。
- 增删节点需要通过数组插入与删除操作实现，效率较低。
- 当二叉树中存在大量 None 时，数组中包含的节点数据比重较低，空间利用率较低。
二叉搜索树
「二叉搜索树 binary search tree」满足以下条件：
- 对于根节点，左子树中所有节点的值 < 根节点的值 < 右子树中所有节点的值。
- 任意节点的左、右子树也是二叉搜索树，即同样满足条件 1. 。
二叉搜索树的构造
二叉搜索树的中序遍历序列是升序的。在二叉搜索树中获取有序数据仅需 𝑂(𝑛)时间
class binary_search_tree: def __init__(self, root) -> None: self.__root = root self.res = [] def search(self, num): cur = self.__root while cur is not None: if cur.val == num: return cur elif cur.val < num: cur = cur.right elif cur.val > num: cur = cur.left else: return None def insert(self, num): node = TreeNode(num) if self.__root is None: self.__root = node pre = None cur = self.__root while cur is not None: if cur.val == num: return ValueError('值重复') elif cur.val < num: pre = cur cur = cur.right elif cur.val > num: pre = cur cur = cur.left if pre.val < num: pre.right = node else: pre.left = node def remove(self, num): cur = self.__root pre = None while cur is not None: if cur.val == num: break elif cur.val < num: pre = cur cur = cur.right elif cur.val > num: pre = cur cur = cur.left else: raise ValueError('没有这个值') if cur.left is None or cur.right is None: child = cur.left or cur.right if pre is None: self.__root = None if pre.left == cur: pre.left = child elif pre.right == cur: pre.right = child else: tem = cur.left while tem.right is not None: tem = tem.right self.remove(tem.val) cur.val = tem.val def __dfs(self, node, order): if node is None: return None if order == 'pre': self.res.append(node.val) self.__dfs(node.left, order) if order == 'in': self.res.append(node.val) self.__dfs(node.right, order) if order == 'post': self.res.append(node.val) def pre_order(self): self.res = [] self.__dfs(self.__root, 'pre') return self.res def in_order(self): self.res = [] self.__dfs(self.__root, 'in') return self.res def post_order(self): self.res = [] self.__dfs(self.__root, 'post') return self.res node_1 = TreeNode(8) node_2 = TreeNode(4) node_3 = TreeNode(12) node_4 = TreeNode(3) node_5 = TreeNode(6) node_6 = TreeNode(10) node_7 = TreeNode(14) node_1.left = node_2 node_1.right = node_3 node_2.left = node_4 node_2.right = node_5 node_3.left = node_6 node_3.right = node_7
二叉搜索树的效率
给定一组数据，我们考虑使用数组或二叉搜索树存储。观察表 7‑2 ，二叉搜索树的各项操作的时间复杂度都是对数阶，具有稳定且高效的性能表现。只有在高频添加、低频查找删除的数据适用场景下，数组比二叉搜索树的效率更高。在理想情况下，二叉搜索树是“平衡”的，这样就可以在 log 𝑛 轮循环内查找任意节点。然而，如果我们在二叉搜索树中不断地插入和删除节点，可能导致二叉树退化为图 7‑23 所示的链表，这时各种操作的时间复杂度也会退化为 𝑂(𝑛) 。
AVL树
class AVL: def __init__(self, root) -> None: self.root = root self.res = [] def height(self, node): if node is not None: return node.height else: return -1 def __update_height(self, node): node.height = max(node.left.height, node.right.height) + 1 def balance_factor(self, node): if node is None: return 0 else: return self.height(node.left) - self.height(node.right) def __right_rotate(self, node): child = node.left grand_child = child.right child.right = node node.left = grand_child self.__update_height(node) self.__update_height(child) return child def __left_rotate(self, node): child = node.right grand_child = child.left child.left = node node.right = grand_child self.__update_height(node) self.__update_height(child) return child def __rotate(self, node): balance_factor = self.balance_factor(node) if balance_factor > 1: if self.balance_factor(node.left) >= 0: return self.__right_rotate(node) else: node.left = self.__left_rotate(node.left) return self.__right_rotate(node) elif balance_factor < -1: if self.balance_factor(node.right) <= 0: return self.__left_rotate(node) else: node.right = self.__right_rotate(node.right) return self.__left_rotate(node) return node def __insert_helper(self, node, val): if node is None: return TreeNode(val) if val < node.val: node.left = self.__insert_helper(node.left, val) elif val > node.val: node.right = self.__insert_helper(node.right, val) else: return node self.__update_height(node) return self.__rotate(node) def insert(self, val): self.root = self.__insert_helper(self.root, val) def __remove_helper(self, node, val): if node is None: return None if val < node.val: node.left = self.__remove_helper(node.left, val) elif val > node.val: node.right = self.__remove_helper(node.right, val) else: if node.left is None or node.right is None: child = node.left or node.right if child is None: return None else: node = child else: temp = node.left while temp.right: temp = temp.right node.left = self.__remove_helper(node.left, temp.val) node.val = temp.val self.__update_height(node) return self.__rotate(node) def remove(self, val): self.root = self.__remove_helper(self.root, val) def __dfs(self, node, order): if node is None: return None if order == 'pre': self.res.append(node.val) self.__dfs(node.left, order) if order == 'in': self.res.append(node.val) self.__dfs(node.right, order) if order == 'post': self.res.append(node.val) def pre_order(self): self.res = [] self.__dfs(self.root, 'pre') return self.res def in_order(self): self.res = [] self.__dfs(self.root, 'in') return self.res def post_order(self): self.res = [] self.__dfs(self.root, 'post') return self.res def search(self, value): cur = self.root while cur: if cur.val == value: break elif cur.val < value: cur = cur.right elif cur.val > value: cur = cur.left else: raise ValueError('这个值不存在') return cur
重点回顾
- 二叉树是一种非线性数据结构，体现“一分为二”的分治逻辑。每个二叉树节点包含一个值以及两个指针，分别指向其左子节点和右子节点。
- 对于二叉树中的某个节点，其左（右）子节点及其以下形成的树被称为该节点的左（右）子树。
- 二叉树的相关术语包括根节点、叶节点、层、度、边、高度和深度等。
- 二叉树的初始化、节点插入和节点删除操作与链表操作方法类似。
- 常见的二叉树类型有完美二叉树、完全二叉树、满二叉树和平衡二叉树。完美二叉树是最理想的状态，而链表是退化后的最差状态。
- 二叉树可以用数组表示，方法是将节点值和空位按层序遍历顺序排列，并根据父节点与子节点之间的索引映射关系来实现指针。
- 二叉树的层序遍历是一种广度优先搜索方法，它体现了“一圈一圈向外”的分层遍历方式，通常通过队列来实现。
- 前序、中序、后序遍历皆属于深度优先搜索，它们体现了“走到尽头，再回头继续”的回溯遍历方式，通常使用递归来实现。
- 二叉搜索树是一种高效的元素查找数据结构，其查找、插入和删除操作的时间复杂度均为 𝑂(log 𝑛) 。
- 当二叉搜索树退化为链表时，各项时间复杂度会劣化至 𝑂(𝑛) 。
- AVL 树，也称为平衡二叉搜索树，它通过旋转操作，确保在不断插入和删除节点后，树仍然保持平衡。
- AVL 树的旋转操作包括右旋、左旋、先右旋再左旋、先左旋再右旋。在插入或删除节点后，AVL 树会从底向顶执行旋转操作，使树重新恢复平衡。
