目录Python全系列 教程
3567个小节阅读：5929.1k
目录
鸿蒙应用开发
C语言快速入门
JAVA全系列 教程
面向对象的程序设计语言
Python全系列 教程
Python3.x版本，未来主流的版本
人工智能 教程
顺势而为，AI创新未来
大厂算法 教程
算法，程序员自我提升必经之路
C++ 教程
一门通用计算机编程语言
微服务 教程
目前业界流行的框架组合
web前端全系列 教程
通向WEB技术世界的钥匙
大数据全系列 教程
站在云端操控万千数据
AIGC全能工具班
A A
White Night
将所有节点按照层序遍历的顺序存储在一个数组中，则每个节点都对应唯一的数组索引
可以推导出父节点索引与子节点索引之间的"映射公式"：
如果不是规则的二叉树，就会出问题！
解决方案
xxxxxxxxxxclass ArrayBinaryTree: """数组表示下的二叉树类"""
def __init__(self, arr: list[int | None]): """构造方法""" self._tree = list(arr)
def size(self): """节点数量""" return len(self._tree)
def val(self, i: int) -> int: """获取索引为 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
def level_order(self) -> list[int]: """层序遍历""" self.res = [] # 直接遍历数组 for i in self.: if self.val(i) is not None: self.res.append(self.val(i)) return self.res
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, order="pre") return self.res
def in_order(self) -> list[int]: """中序遍历""" self.res = [] self.dfs(0, order="in") return self.res
def post_order(self) -> list[int]: """后序遍历""" self.res = [] self.dfs(0, order="post") return self.res实时效果反馈
1. 二叉树通过数组的方式实现，若节点索引为10，右子节点的索引是多少？
A 18
B 20
C 21
D 22
答案
1=>D