Hello 算法用数组表示二叉树——索引映射公式与 ArrayBinaryTree 的完整 Python 实现【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo本文基于 hello-algo 仓库的codes/pythontutor/chapter_tree/array_binary_tree.mdPython Tutor 可视化数据文件及其对应的可运行源码 array_binary_tree.py系统讲解“用数组表示二叉树”的核心思想通过索引映射公式2i1 / 2i2 / (i-1)//2替代指针引用实现对节点值、父子关系的 O(1) 访问与前/中/后序及层序遍历并说明该文件在 Python Tutor 单步可视化中的使用方式。一、这个文档文件是什么Python Tutor 可视化数据codes/pythontutor/目录下的每个.md文件并非普通文章而是喂给 Python Tutor 为例它的结构非常固定!-- File: array_binary_tree.md Created Time: 2024-01-05 Author: krahets (krahets163.com) -- !-- [file]{array_binary_tree}-[class]{array_binary_tree}-[func]{} -- https://pythontutor.com/render.html#code...URL 编码后的完整 Python 源码py311modedisplay...头部注释中的[file]{array_binary_tree}-[class]{array_binary_tree}-[func]{}是与文档站代码块标记 Python多语言切换器中[file]{...}语法对应的锚点标明这段代码属于array_binary_tree文件、ArrayBinaryTree类、全部方法。紧随其后的render.html#code...链接是把完整 Python 源码做了 URL 编码后拼出来的渲染地址参数py311表示按 Python 3.11 语法高亮modedisplay表示展示模式。把该链接粘贴进浏览器就能在 Python Tutor 中获得带内存视图、可逐指令单步执行的ArrayBinaryTree运行演示——这正是该目录名为pythontutor的原因。将 URL 编码部分解码后得到的完整代码与仓库中可直接运行的 array_binary_tree.py 基本一致可视化版用更小的示例数组去掉了对modules工具的依赖保证单文件即可在 Python Tutor 中独立运行。下文以可运行版本为主体逐段讲解两者差异处会单独指出。二、表示完美二叉树索引映射公式在链表表示下二叉树的存储单元是TreeNode节点节点之间靠指针left/right引用连接仓库中的定义见 tree_node.pyclass TreeNode: 二叉树节点类 def __init__(self, val: int 0): self.val: int val # 节点值 self.height: int 0 # 节点高度 self.left: TreeNode | None None # 左子节点引用 self.right: TreeNode | None None # 右子节点引用那么能否不用指针、只用一个数组答案是肯定的。先考虑最理想的情况——完美二叉树把所有节点按层序遍历的顺序存入数组每个节点对应唯一的数组索引。根据层序遍历的特性可以推导出父/子索引之间的映射公式若某节点的索引为i则其左子节点索引为2i 1右子节点索引为2i 2父节点索引为(i - 1) // 2。这些映射公式的角色等价于链表表示中的指针给定数组中的任意一个节点通过公式即可 O(1) 定位它的左子、右子与父节点无需任何引用存储。三、表示任意二叉树显式写出 None完美二叉树只是特例。真实的二叉树中间层通常存在许多空位而普通层序遍历序列并不包含这些None因此同一条层序序列可能对应多种不同的树结构无法唯一表示。解决方法是在层序遍历序列中显式地写出所有None占位这样序列就能唯一确定二叉树。仓库使用的统一示例是# 二叉树的数组表示 # 使用 None 来表示空位 tree [1, 2, 3, 4, None, 6, 7, 8, 9, None, None, 12, None, None, 15]这个数组对应一棵非完美树索引 4、9、10、12、13 为空位。各语言对“空位”的表示不同但编码规则完全一致例如 C/C 用INT_MAX、Java 用Integer[]null、Go 用[]anynil、Rust 用Optioni32完整对照见 array_representation_of_tree.md。值得一提的是完全二叉树按定义空位只出现在最底层且靠右的位置因此所有None必然出现在数组末尾序列化时可以全部省略数组表示最为紧凑。堆heap就是最典型的“完全二叉树的数组表示”仓库中 print_util.py 的print_heap正是把堆数组用list_to_tree还原成树状图形打印。四、ArrayBinaryTree 类逐方法解析下面结合 array_binary_tree.py 的源码逐方法说明。4.1 构造与容量class ArrayBinaryTree: 数组表示下的二叉树类 def __init__(self, arr: list[int | None]): 构造方法 self._tree list(arr) def size(self): 列表容量 return len(self._tree)构造时用list(arr)做一次浅拷贝避免外部修改原数组影响树的内容size()返回数组长度即“列表容量”注意它不等于节点个数。4.2 节点访问val / left / right / parentdef val(self, i: int) - int | None: 获取索引为 i 节点的值 # 若索引越界则返回 None 代表空位 if i 0 or i self.size(): return None return self._tree[i] def left(self, i: int) - int | None: 获取索引为 i 节点的左子节点的索引 return 2 * i 1 def right(self, i: int) - int | None: 获取索引为 i 节点的右子节点的索引 return 2 * i 2 def parent(self, i: int) - int | None: 获取索引为 i 节点的父节点的索引 return (i - 1) // 2四个方法共同构成数组表示的“指针系统”方法公式说明val(i)tree[i]越界时返回None与“空位”语义统一调用方无需做边界判断left(i)2i 1返回索引而非节点越界与否交由val判定right(i)2i 2同上parent(i)(i - 1) // 2整除向下取整i0根节点会得到(0-1)//2 -1val(-1)因越界保护而返回None这种“返回索引 由val统一兜底越界”的设计使递归代码可以无边界检查地写self.dfs(self.left(i), order)逻辑非常干净。4.3 层序遍历数组的先天优势def level_order(self) - list[int]: 层序遍历 self.res [] # 直接遍历数组 for i in range(self.size()): if self.val(i) is not None: self.res.append(self.val(i)) return self.res因为数组本身就是按层序排好的层序遍历不需要队列一次线性扫描跳过None即可时间复杂度 O(n)比链表表示下需要显式维护队列的 BFS 实现简单得多。4.4 深度优先遍历用 order 参数统一前/中/后序def dfs(self, i: int, order: str): 深度优先遍历 if self.val(i) is None: return # 前序遍历 if order pre: self.res.append(self.val(i)) self.dfs(self.left(i), order) # 中序遍历 if order in: self.res.append(self.val(i)) self.dfs(self.right(i), order) # 后序遍历 if order post: self.res.append(self.val(i)) def pre_order(self) - list[int]: 前序遍历 self.res [] self.dfs(0, orderpre) return self.res # in_order / post_order 同理分别传 in 与 post实现要点有三个剪枝val(i) is None时直接返回。注意即使父节点为空left/right公式仍会算出子索引因此必须依赖空位判断终止递归而不能依赖“父为空则子必为空”。三序合一访问时机记录节点值分别放在递归左子树之前、左右之间、递归右子树之后用一个order字符串复用同一套递归骨架。结果容器self.res由三个入口方法各自初始化dfs只做累加保证每次遍历都得到独立结果。对照链表版实现可以看到数组版的dfs(i, order)与链表版dfs(root)的递归结构完全同构差别仅在于“取子节点”从node.left变成了self.left(i)的索引计算——这正是映射公式替代指针的直接体现。五、运行示例Driver Code 与可视化版的差异可运行版的驱动代码array_binary_tree.py演示了完整链路if __name__ __main__: # 初始化二叉树 # 这里借助了一个从数组直接生成二叉树的函数 arr [1, 2, 3, 4, None, 6, 7, 8, 9, None, None, 12, None, None, 15] root list_to_tree(arr) print(\n初始化二叉树\n) print(二叉树的数组表示) print(arr) print(二叉树的链表表示) print_tree(root) # 数组表示下的二叉树类 abt ArrayBinaryTree(arr) # 访问节点 i 1 l, r, p abt.left(i), abt.right(i), abt.parent(i) print(f\n当前节点的索引为 {i} 值为 {abt.val(i)}) print(f其左子节点的索引为 {l} 值为 {abt.val(l)}) print(f其右子节点的索引为 {r} 值为 {abt.val(r)}) print(f其父节点的索引为 {p} 值为 {abt.val(p)}) # 遍历树 res abt.level_order() # 层序遍历 res abt.pre_order() # 前序遍历 res abt.in_order() # 中序遍历 res abt.post_order() # 后序遍历其中list_to_tree与print_tree分别来自 tree_node.py 和 print_util.py它们同样基于同一套索引公式工作从源码结构可以印证公式的正确性def list_to_tree_dfs(arr: list[int], i: int) - TreeNode | None: 将列表反序列化为二叉树递归 # 如果索引超出数组长度或者对应的元素为 None 则返回 None if i 0 or i len(arr) or arr[i] is None: return None # 构建当前节点 root TreeNode(arr[i]) # 递归构建左右子树 root.left list_to_tree_dfs(arr, 2 * i 1) root.right list_to_tree_dfs(arr, 2 * i 2) return root数组到树list_to_tree_dfs与树到数组tree_to_list_dfs见 tree_node.py用res [None] * (i - len(res) 1)补位到目标索引互为逆操作TreeNode类注释里还直接给出了示例数组与对应树形图可作为人工验证映射公式的对照表。Python Tutor 可视化版即 array_binary_tree.md 解码后的内容为了单文件自包含做了两处简化内置了一个精简版TreeNode仅val/left/right三个属性不再 importmodules示例数组缩小为arr [1, 2, 3, 4, None, 6, None]便于在可视化器的小画布上观察内存帧变化。解码后的驱动部分如下Driver Code if __name__ __main__: # 初始化二叉树 arr [1, 2, 3, 4, None, 6, None] abt ArrayBinaryTree(arr) # 访问节点 i 1 l, r, p abt.left(i), abt.right(i), abt.parent(i) # 遍历树 res abt.level_order() res abt.pre_order() res abt.in_order() res abt.post_order()对索引i 1值为 2应用公式left 2*11 3值为 4、right 2*12 4空位val(4)返回None、parent (1-1)//2 0值为 1与树形结构完全吻合——这就是在 Python Tutor 中逐帧单步时应当核对的内存状态。六、优点与局限性综合文档 array_representation_of_tree.md 的结论与上述源码实现数组表示的取舍如下优点数组存储在连续内存中对缓存友好访问与遍历速度较快层序遍历甚至可降为简单扫描不需要存储指针比较节省空间且节点间关系通过纯算术公式 O(1) 获取允许随机访问任意节点实现紧凑完全二叉树可省略末尾空位序列化即存储天然适合堆等场景。局限性数组需要连续内存空间不适合存储数据量过大的树增删节点需要借助数组插入/删除操作实现效率较低O(n) 搬移当二叉树中存在大量None如极度不平衡的树时有效数据占比低空间利用率差。因此实践中常见“双表示”策略对外用指针链表表示方便结构操作内部堆、线段树等用数组表示追求性能——本仓库同时提供 array_binary_tree.py 与 binary_tree.py 两套实现恰好构成这一对比学习的完整闭环。七、小结数组表示二叉树的核心是三条索引映射公式左子2i1、右子2i2、父(i-1)//2它们完全替代了链表中的指针任意二叉树需要在层序序列中显式保留None占位才能被唯一表示完全二叉树则可直接省略末尾空位ArrayBinaryTree展示了四个节点访问方法与一套“order参数驱动”的三序 DFS层序遍历则退化为线性扫描codes/pythontutor/chapter_tree/array_binary_tree.md 以 URL 编码链接的形式承载上述代码可直接在 Python Tutor 中逐指令单步观察每一帧中self._tree列表与递归栈的内存变化是理解该表示法的交互式教具。【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 Hello 算法：用数组表示二叉树——索引映射公式与 ArrayBinaryTree 的完整 Python 实现
Hello 算法用数组表示二叉树——索引映射公式与 ArrayBinaryTree 的完整 Python 实现【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo本文基于 hello-algo 仓库的codes/pythontutor/chapter_tree/array_binary_tree.mdPython Tutor 可视化数据文件及其对应的可运行源码 array_binary_tree.py系统讲解“用数组表示二叉树”的核心思想通过索引映射公式2i1 / 2i2 / (i-1)//2替代指针引用实现对节点值、父子关系的 O(1) 访问与前/中/后序及层序遍历并说明该文件在 Python Tutor 单步可视化中的使用方式。一、这个文档文件是什么Python Tutor 可视化数据codes/pythontutor/目录下的每个.md文件并非普通文章而是喂给 Python Tutor 为例它的结构非常固定!-- File: array_binary_tree.md Created Time: 2024-01-05 Author: krahets (krahets163.com) -- !-- [file]{array_binary_tree}-[class]{array_binary_tree}-[func]{} -- https://pythontutor.com/render.html#code...URL 编码后的完整 Python 源码py311modedisplay...头部注释中的[file]{array_binary_tree}-[class]{array_binary_tree}-[func]{}是与文档站代码块标记 Python多语言切换器中[file]{...}语法对应的锚点标明这段代码属于array_binary_tree文件、ArrayBinaryTree类、全部方法。紧随其后的render.html#code...链接是把完整 Python 源码做了 URL 编码后拼出来的渲染地址参数py311表示按 Python 3.11 语法高亮modedisplay表示展示模式。把该链接粘贴进浏览器就能在 Python Tutor 中获得带内存视图、可逐指令单步执行的ArrayBinaryTree运行演示——这正是该目录名为pythontutor的原因。将 URL 编码部分解码后得到的完整代码与仓库中可直接运行的 array_binary_tree.py 基本一致可视化版用更小的示例数组去掉了对modules工具的依赖保证单文件即可在 Python Tutor 中独立运行。下文以可运行版本为主体逐段讲解两者差异处会单独指出。二、表示完美二叉树索引映射公式在链表表示下二叉树的存储单元是TreeNode节点节点之间靠指针left/right引用连接仓库中的定义见 tree_node.pyclass TreeNode: 二叉树节点类 def __init__(self, val: int 0): self.val: int val # 节点值 self.height: int 0 # 节点高度 self.left: TreeNode | None None # 左子节点引用 self.right: TreeNode | None None # 右子节点引用那么能否不用指针、只用一个数组答案是肯定的。先考虑最理想的情况——完美二叉树把所有节点按层序遍历的顺序存入数组每个节点对应唯一的数组索引。根据层序遍历的特性可以推导出父/子索引之间的映射公式若某节点的索引为i则其左子节点索引为2i 1右子节点索引为2i 2父节点索引为(i - 1) // 2。这些映射公式的角色等价于链表表示中的指针给定数组中的任意一个节点通过公式即可 O(1) 定位它的左子、右子与父节点无需任何引用存储。三、表示任意二叉树显式写出 None完美二叉树只是特例。真实的二叉树中间层通常存在许多空位而普通层序遍历序列并不包含这些None因此同一条层序序列可能对应多种不同的树结构无法唯一表示。解决方法是在层序遍历序列中显式地写出所有None占位这样序列就能唯一确定二叉树。仓库使用的统一示例是# 二叉树的数组表示 # 使用 None 来表示空位 tree [1, 2, 3, 4, None, 6, 7, 8, 9, None, None, 12, None, None, 15]这个数组对应一棵非完美树索引 4、9、10、12、13 为空位。各语言对“空位”的表示不同但编码规则完全一致例如 C/C 用INT_MAX、Java 用Integer[]null、Go 用[]anynil、Rust 用Optioni32完整对照见 array_representation_of_tree.md。值得一提的是完全二叉树按定义空位只出现在最底层且靠右的位置因此所有None必然出现在数组末尾序列化时可以全部省略数组表示最为紧凑。堆heap就是最典型的“完全二叉树的数组表示”仓库中 print_util.py 的print_heap正是把堆数组用list_to_tree还原成树状图形打印。四、ArrayBinaryTree 类逐方法解析下面结合 array_binary_tree.py 的源码逐方法说明。4.1 构造与容量class ArrayBinaryTree: 数组表示下的二叉树类 def __init__(self, arr: list[int | None]): 构造方法 self._tree list(arr) def size(self): 列表容量 return len(self._tree)构造时用list(arr)做一次浅拷贝避免外部修改原数组影响树的内容size()返回数组长度即“列表容量”注意它不等于节点个数。4.2 节点访问val / left / right / parentdef val(self, i: int) - int | None: 获取索引为 i 节点的值 # 若索引越界则返回 None 代表空位 if i 0 or i self.size(): return None return self._tree[i] def left(self, i: int) - int | None: 获取索引为 i 节点的左子节点的索引 return 2 * i 1 def right(self, i: int) - int | None: 获取索引为 i 节点的右子节点的索引 return 2 * i 2 def parent(self, i: int) - int | None: 获取索引为 i 节点的父节点的索引 return (i - 1) // 2四个方法共同构成数组表示的“指针系统”方法公式说明val(i)tree[i]越界时返回None与“空位”语义统一调用方无需做边界判断left(i)2i 1返回索引而非节点越界与否交由val判定right(i)2i 2同上parent(i)(i - 1) // 2整除向下取整i0根节点会得到(0-1)//2 -1val(-1)因越界保护而返回None这种“返回索引 由val统一兜底越界”的设计使递归代码可以无边界检查地写self.dfs(self.left(i), order)逻辑非常干净。4.3 层序遍历数组的先天优势def level_order(self) - list[int]: 层序遍历 self.res [] # 直接遍历数组 for i in range(self.size()): if self.val(i) is not None: self.res.append(self.val(i)) return self.res因为数组本身就是按层序排好的层序遍历不需要队列一次线性扫描跳过None即可时间复杂度 O(n)比链表表示下需要显式维护队列的 BFS 实现简单得多。4.4 深度优先遍历用 order 参数统一前/中/后序def dfs(self, i: int, order: str): 深度优先遍历 if self.val(i) is None: return # 前序遍历 if order pre: self.res.append(self.val(i)) self.dfs(self.left(i), order) # 中序遍历 if order in: self.res.append(self.val(i)) self.dfs(self.right(i), order) # 后序遍历 if order post: self.res.append(self.val(i)) def pre_order(self) - list[int]: 前序遍历 self.res [] self.dfs(0, orderpre) return self.res # in_order / post_order 同理分别传 in 与 post实现要点有三个剪枝val(i) is None时直接返回。注意即使父节点为空left/right公式仍会算出子索引因此必须依赖空位判断终止递归而不能依赖“父为空则子必为空”。三序合一访问时机记录节点值分别放在递归左子树之前、左右之间、递归右子树之后用一个order字符串复用同一套递归骨架。结果容器self.res由三个入口方法各自初始化dfs只做累加保证每次遍历都得到独立结果。对照链表版实现可以看到数组版的dfs(i, order)与链表版dfs(root)的递归结构完全同构差别仅在于“取子节点”从node.left变成了self.left(i)的索引计算——这正是映射公式替代指针的直接体现。五、运行示例Driver Code 与可视化版的差异可运行版的驱动代码array_binary_tree.py演示了完整链路if __name__ __main__: # 初始化二叉树 # 这里借助了一个从数组直接生成二叉树的函数 arr [1, 2, 3, 4, None, 6, 7, 8, 9, None, None, 12, None, None, 15] root list_to_tree(arr) print(\n初始化二叉树\n) print(二叉树的数组表示) print(arr) print(二叉树的链表表示) print_tree(root) # 数组表示下的二叉树类 abt ArrayBinaryTree(arr) # 访问节点 i 1 l, r, p abt.left(i), abt.right(i), abt.parent(i) print(f\n当前节点的索引为 {i} 值为 {abt.val(i)}) print(f其左子节点的索引为 {l} 值为 {abt.val(l)}) print(f其右子节点的索引为 {r} 值为 {abt.val(r)}) print(f其父节点的索引为 {p} 值为 {abt.val(p)}) # 遍历树 res abt.level_order() # 层序遍历 res abt.pre_order() # 前序遍历 res abt.in_order() # 中序遍历 res abt.post_order() # 后序遍历其中list_to_tree与print_tree分别来自 tree_node.py 和 print_util.py它们同样基于同一套索引公式工作从源码结构可以印证公式的正确性def list_to_tree_dfs(arr: list[int], i: int) - TreeNode | None: 将列表反序列化为二叉树递归 # 如果索引超出数组长度或者对应的元素为 None 则返回 None if i 0 or i len(arr) or arr[i] is None: return None # 构建当前节点 root TreeNode(arr[i]) # 递归构建左右子树 root.left list_to_tree_dfs(arr, 2 * i 1) root.right list_to_tree_dfs(arr, 2 * i 2) return root数组到树list_to_tree_dfs与树到数组tree_to_list_dfs见 tree_node.py用res [None] * (i - len(res) 1)补位到目标索引互为逆操作TreeNode类注释里还直接给出了示例数组与对应树形图可作为人工验证映射公式的对照表。Python Tutor 可视化版即 array_binary_tree.md 解码后的内容为了单文件自包含做了两处简化内置了一个精简版TreeNode仅val/left/right三个属性不再 importmodules示例数组缩小为arr [1, 2, 3, 4, None, 6, None]便于在可视化器的小画布上观察内存帧变化。解码后的驱动部分如下Driver Code if __name__ __main__: # 初始化二叉树 arr [1, 2, 3, 4, None, 6, None] abt ArrayBinaryTree(arr) # 访问节点 i 1 l, r, p abt.left(i), abt.right(i), abt.parent(i) # 遍历树 res abt.level_order() res abt.pre_order() res abt.in_order() res abt.post_order()对索引i 1值为 2应用公式left 2*11 3值为 4、right 2*12 4空位val(4)返回None、parent (1-1)//2 0值为 1与树形结构完全吻合——这就是在 Python Tutor 中逐帧单步时应当核对的内存状态。六、优点与局限性综合文档 array_representation_of_tree.md 的结论与上述源码实现数组表示的取舍如下优点数组存储在连续内存中对缓存友好访问与遍历速度较快层序遍历甚至可降为简单扫描不需要存储指针比较节省空间且节点间关系通过纯算术公式 O(1) 获取允许随机访问任意节点实现紧凑完全二叉树可省略末尾空位序列化即存储天然适合堆等场景。局限性数组需要连续内存空间不适合存储数据量过大的树增删节点需要借助数组插入/删除操作实现效率较低O(n) 搬移当二叉树中存在大量None如极度不平衡的树时有效数据占比低空间利用率差。因此实践中常见“双表示”策略对外用指针链表表示方便结构操作内部堆、线段树等用数组表示追求性能——本仓库同时提供 array_binary_tree.py 与 binary_tree.py 两套实现恰好构成这一对比学习的完整闭环。七、小结数组表示二叉树的核心是三条索引映射公式左子2i1、右子2i2、父(i-1)//2它们完全替代了链表中的指针任意二叉树需要在层序序列中显式保留None占位才能被唯一表示完全二叉树则可直接省略末尾空位ArrayBinaryTree展示了四个节点访问方法与一套“order参数驱动”的三序 DFS层序遍历则退化为线性扫描codes/pythontutor/chapter_tree/array_binary_tree.md 以 URL 编码链接的形式承载上述代码可直接在 Python Tutor 中逐指令单步观察每一帧中self._tree列表与递归栈的内存变化是理解该表示法的交互式教具。【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考