Python二叉树实现与解析
学习文章要努力,但是不要急!今天的这篇文章《Python实现二叉树详解》将会介绍到等等知识点,如果你想深入学习文章,可以关注我!我会持续更新相关文章的,希望对大家都能有所帮助!
如何构建一个基本的二叉树节点?明确答案是定义一个包含值和左右子节点引用的Python类。具体做法是创建一个TreeNode类,其__init__方法接收val(节点值)、left(左子节点引用)和right(右子节点引用)三个参数,并将它们分别赋值给实例属性;2. Python中常见的二叉树遍历方式有哪些?明确答案是前序、中序和后序三种遍历方式。前序遍历先访问根节点,再递归遍历左子树和右子树;中序遍历先递归遍历左子树,再访问根节点,最后递归遍历右子树;后序遍历先递归遍历左子树和右子树,最后访问根节点;3. 如何在二叉搜索树中插入和删除节点?明确答案是插入通过递归查找合适位置实现,删除则根据节点情况分别处理。插入操作从根节点开始,若新值小于当前节点则进入左子树递归插入,否则进入右子树递归插入;删除操作分为三种情况:若为叶子节点直接删除,若只有一个子节点则用子节点替代,若有两个子节点则选择右子树中最小节点或左子树中最大节点作为替代者并递归删除该替代节点。
Python实现二叉树,说白了,核心就是定义一个节点(Node),然后通过这个节点来管理它左右子节点的引用关系。这玩意儿本质上是递归思想的体现,用Python的类和对象来模拟那种层级结构,既直观又灵活。它不像数组那样连续存储,而是靠指针(在Python里就是对象引用)把散落在内存各处的节点串起来。

解决方案
要搞定二叉树,我们通常会先定义一个节点类,然后在此基础上构建树的操作逻辑。
class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right def __repr__(self): # 只是为了方便打印和调试,实际使用中可能不需要 return f"Node({self.val})" # 构建一个简单的二叉树(非二叉搜索树) # 根节点 root = TreeNode(1) # 左子树 root.left = TreeNode(2) root.left.left = TreeNode(4) root.left.right = TreeNode(5) # 右子树 root.right = TreeNode(3) root.right.left = TreeNode(6) print("二叉树节点已构建。") # 接下来是遍历,这是理解树结构最直接的方式 def inorder_traversal(node): """中序遍历:左 -> 根 -> 右""" if node: inorder_traversal(node.left) print(node.val, end=" ") inorder_traversal(node.right) print("中序遍历结果:") inorder_traversal(root) print("\n") # 换行 def preorder_traversal(node): """前序遍历:根 -> 左 -> 右""" if node: print(node.val, end=" ") preorder_traversal(node.left) preorder_traversal(node.right) print("前序遍历结果:") preorder_traversal(root) print("\n") def postorder_traversal(node): """后序遍历:左 -> 右 -> 根""" if node: postorder_traversal(node.left) postorder_traversal(node.right) print(node.val, end=" ") print("后序遍历结果:") postorder_traversal(root) print("\n")
如何构建一个基本的二叉树节点?
构建一个二叉树节点,说白了就是定义一个Python类。我个人觉得,这玩意儿是所有树结构操作的基石,没有它,你连树的影子都摸不着。这个类通常包含三个核心属性:一个用于存储节点值(val
),另外两个则是指向其左子节点和右子节点的引用(left
和right
)。

class TreeNode: def __init__(self, val=0, left=None, right=None): """ 初始化一个二叉树节点。 :param val: 节点存储的值。可以是任何类型,数字、字符串、甚至其他对象。 :param left: 指向左子节点的引用。如果当前没有左子节点,通常设为None。 :param right: 指向右子节点的引用。如果当前没有右子节点,通常设为None。 """ self.val = val self.left = left self.right = right def __repr__(self): # 这个方法是为了方便调试,当你直接打印一个TreeNode对象时,它会显示这个格式。 # 比如 print(TreeNode(5)) 会输出 Node(5) return f"Node({self.val})" # 举个例子,看看怎么用它: node_a = TreeNode(10) # 创建一个值为10的节点,此时它没有左右子节点 node_b = TreeNode(20) node_c = TreeNode(30) node_a.left = node_b # 把node_b设为node_a的左子节点 node_a.right = node_c # 把node_c设为node_a的右子节点 # 现在,node_a 就是一个根节点,node_b是它的左孩子,node_c是它的右孩子。 # 我们可以这样访问: print(f"根节点的值: {node_a.val}") print(f"根节点的左孩子值: {node_a.left.val}") print(f"根节点的右孩子值: {node_a.right.val}") # 如果尝试访问一个不存在的子节点,比如 node_b.left,它会是None。
这里面的left
和right
属性,它们存储的不是值本身,而是指向另一个TreeNode
对象的内存地址(或者说引用)。这就跟搭积木似的,你把一块积木(节点)放在那儿,然后用线(引用)把它和另一块积木连接起来。如果没连接,那线就是空的(None
)。这种设计让树的结构变得非常灵活,可以动态地增删节点,而不用像数组那样担心内存连续性或扩容问题。
Python中常见的二叉树遍历方式有哪些?
二叉树的遍历,简单来说,就是按照某种特定的顺序访问树中的每一个节点。这事儿在数据结构里挺重要的,因为很多时候你需要把树里的所有数据都过一遍,或者按特定逻辑找出某个数据。常见的遍历方式有三种,它们都基于递归思想,但访问节点的顺序不同:前序、中序和后序。

前序遍历 (Pre-order Traversal):
- 访问根节点。
- 递归遍历左子树。
- 递归遍历右子树。
- 这种遍历方式,我觉得挺像我们平时看目录结构,先看当前文件夹的名字,再看它里面的子文件夹。
def preorder_traversal(node): if node: print(node.val, end=" ") # 先访问根节点 preorder_traversal(node.left) # 再遍历左子树 preorder_traversal(node.right) # 最后遍历右子树
中序遍历 (In-order Traversal):
- 递归遍历左子树。
- 访问根节点。
- 递归遍历右子树。
- 中序遍历在二叉搜索树(BST)里特别有用,因为它能按升序(或降序)访问所有节点。这对我来说,是它最直观的用途之一。
def inorder_traversal(node): if node: inorder_traversal(node.left) # 先遍历左子树 print(node.val, end=" ") # 再访问根节点 inorder_traversal(node.right) # 最后遍历右子树
后序遍历 (Post-order Traversal):
- 递归遍历左子树。
- 递归遍历右子树。
- 访问根节点。
- 后序遍历的一个典型应用是计算表达式树的值,或者在删除树时,先删除子节点再删除父节点,避免悬空指针。
def postorder_traversal(node): if node: postorder_traversal(node.left) # 先遍历左子树 postorder_traversal(node.right) # 再遍历右子树 print(node.val, end=" ") # 最后访问根节点
除了递归,这三种遍历方式也可以用迭代的方式实现,通常需要借助栈来模拟递归的调用栈。迭代实现虽然代码量可能多一些,但可以避免深度递归带来的栈溢出风险,尤其是在处理非常深的树时,这会是个实际的考量。
如何在二叉搜索树中插入和删除节点?
这里我们特指二叉搜索树 (Binary Search Tree, BST),因为在普通二叉树中,插入和删除通常没有固定的规则,可以任意位置插入或删除,这取决于具体的应用场景。但在BST中,每个节点的值都大于其左子树中任意节点的值,且小于其右子树中任意节点的值。这个特性让插入和删除变得有章可循,但也更复杂。
插入节点:
插入一个新节点到BST,其实就是找到它应该待的那个“坑”。这个过程是个递归的查找,从根节点开始:
- 如果新值比当前节点小,就往左子树找。
- 如果新值比当前节点大,就往右子树找。
- 直到找到一个空位置(
None
),就把新节点放进去。
def insert_bst(root, val): if root is None: return TreeNode(val) # 如果树是空的,新节点就是根节点 if val < root.val: root.left = insert_bst(root.left, val) # 往左子树递归插入 else: # 假设没有重复值,或者重复值放在右边 root.right = insert_bst(root.right, val) # 往右子树递归插入 return root # 返回当前子树的根节点
删除节点:
删除节点是BST操作里最麻烦的一个,因为它分好几种情况,得小心翼翼地处理,不然树的结构就乱了。我个人觉得,理解这块儿需要多画图,才能把逻辑搞清楚。
删除一个节点node_to_delete
,主要有三种情况:
node_to_delete
是叶子节点 (没有子节点): 直接删除它,也就是将其父节点指向它的引用设为None
。这是最简单的情况。node_to_delete
只有一个子节点: 用它的那个唯一的子节点来替代它。比如,如果它只有左子节点,就把左子节点提上来;如果只有右子节点,就把右子节点提上来。node_to_delete
有两个子节点: 这是最复杂的情况。我们需要找到一个“替代者”来填补被删除节点的位置,并且这个替代者要能维持BST的特性。通常有两种选择:- 右子树中最小的节点 (in-order successor): 找到被删除节点右子树中值最小的节点,用它的值替换被删除节点的值,然后递归地删除这个最小节点(它肯定没有左子节点,可能是叶子或只有一个右子节点)。
- 左子树中最大的节点 (in-order predecessor): 找到被删除节点左子树中值最大的节点,用它的值替换被删除节点的值,然后递归地删除这个最大节点。
下面是一个简化的删除逻辑,主要展示了处理这三种情况的思路:
def find_min_node(node): """辅助函数:找到子树中值最小的节点""" current = node while current.left is not None: current = current.left return current def delete_bst(root, val): if root is None: return root # 树为空,或者没找到要删除的节点 # 递归查找要删除的节点 if val < root.val: root.left = delete_bst(root.left, val) elif val > root.val: root.right = delete_bst(root.right, val) else: # 找到了要删除的节点 (root.val == val) # 情况 1 & 2: 节点只有一个子节点或没有子节点 if root.left is None: return root.right # 直接返回右子节点(可能是None) elif root.right is None: return root.left # 直接返回左子节点 # 情况 3: 节点有两个子节点 # 找到右子树中最小的节点 (in-order successor) temp = find_min_node(root.right) # 用这个最小节点的值替换当前节点的值 root.val = temp.val # 递归地删除右子树中的那个最小节点 root.right = delete_bst(root.right, temp.val) return root
删除操作的实现往往比较考验对递归和指针操作的理解。特别是处理有两个子节点的情况,需要先找到合适的替代者,再把那个替代者从原来的位置“挖”出来,这个过程如果逻辑不清晰,很容易出错。实际编码时,通常会写一些辅助函数来让代码更清晰,比如上面那个find_min_node
。
以上就是本文的全部内容了,是否有顺利帮助你解决问题?若是能给你带来学习上的帮助,请大家多多支持golang学习网!更多关于文章的相关知识,也可关注golang学习网公众号。

- 上一篇
- Linux系统备份配置指南

- 下一篇
- Python接入Ceph存储教程详解
-
- 文章 · python教程 | 29秒前 |
- Python爬虫实战:requests+BeautifulSoup教程
- 451浏览 收藏
-
- 文章 · python教程 | 1分钟前 | Python scikit-learn 模型性能 特征工程 特征处理
- Python特征工程技巧大揭秘
- 376浏览 收藏
-
- 文章 · python教程 | 13分钟前 |
- TensorFlowDQNcollect_policy维度问题解决方法
- 417浏览 收藏
-
- 文章 · python教程 | 22分钟前 |
- 非捕获分组作用及使用场景解析
- 249浏览 收藏
-
- 文章 · python教程 | 45分钟前 |
- Python操作MongoDB入门指南
- 406浏览 收藏
-
- 文章 · python教程 | 1小时前 |
- Python处理表单数据的实用方法
- 162浏览 收藏
-
- 文章 · python教程 | 1小时前 | 效率 异步 并发 aiohttp Python网络爬虫
- Pythonaiohttp异步爬虫实战教程
- 390浏览 收藏
-
- 文章 · python教程 | 1小时前 |
- Python操作Word文档入门指南
- 261浏览 收藏
-
- 前端进阶之JavaScript设计模式
- 设计模式是开发人员在软件开发过程中面临一般问题时的解决方案,代表了最佳的实践。本课程的主打内容包括JS常见设计模式以及具体应用场景,打造一站式知识长龙服务,适合有JS基础的同学学习。
- 542次学习
-
- GO语言核心编程课程
- 本课程采用真实案例,全面具体可落地,从理论到实践,一步一步将GO核心编程技术、编程思想、底层实现融会贯通,使学习者贴近时代脉搏,做IT互联网时代的弄潮儿。
- 511次学习
-
- 简单聊聊mysql8与网络通信
- 如有问题加微信:Le-studyg;在课程中,我们将首先介绍MySQL8的新特性,包括性能优化、安全增强、新数据类型等,帮助学生快速熟悉MySQL8的最新功能。接着,我们将深入解析MySQL的网络通信机制,包括协议、连接管理、数据传输等,让
- 498次学习
-
- JavaScript正则表达式基础与实战
- 在任何一门编程语言中,正则表达式,都是一项重要的知识,它提供了高效的字符串匹配与捕获机制,可以极大的简化程序设计。
- 487次学习
-
- 从零制作响应式网站—Grid布局
- 本系列教程将展示从零制作一个假想的网络科技公司官网,分为导航,轮播,关于我们,成功案例,服务流程,团队介绍,数据部分,公司动态,底部信息等内容区块。网站整体采用CSSGrid布局,支持响应式,有流畅过渡和展现动画。
- 484次学习
-
- CodeWhisperer
- Amazon CodeWhisperer,一款AI代码生成工具,助您高效编写代码。支持多种语言和IDE,提供智能代码建议、安全扫描,加速开发流程。
- 9次使用
-
- 畅图AI
- 探索畅图AI:领先的AI原生图表工具,告别绘图门槛。AI智能生成思维导图、流程图等多种图表,支持多模态解析、智能转换与高效团队协作。免费试用,提升效率!
- 33次使用
-
- TextIn智能文字识别平台
- TextIn智能文字识别平台,提供OCR、文档解析及NLP技术,实现文档采集、分类、信息抽取及智能审核全流程自动化。降低90%人工审核成本,提升企业效率。
- 42次使用
-
- 简篇AI排版
- SEO 简篇 AI 排版,一款强大的 AI 图文排版工具,3 秒生成专业文章。智能排版、AI 对话优化,支持工作汇报、家校通知等数百场景。会员畅享海量素材、专属客服,多格式导出,一键分享。
- 37次使用
-
- 小墨鹰AI快排
- SEO 小墨鹰 AI 快排,新媒体运营必备!30 秒自动完成公众号图文排版,更有 AI 写作助手、图片去水印等功能。海量素材模板,一键秒刷,提升运营效率!
- 36次使用
-
- Flask框架安装技巧:让你的开发更高效
- 2024-01-03 501浏览
-
- Django框架中的并发处理技巧
- 2024-01-22 501浏览
-
- 提升Python包下载速度的方法——正确配置pip的国内源
- 2024-01-17 501浏览
-
- Python与C++:哪个编程语言更适合初学者?
- 2024-03-25 501浏览
-
- 品牌建设技巧
- 2024-04-06 501浏览