本文研究的主要是python实现二叉查找树的相关内容,具体介绍及实现如下。
1. 二叉查找树的定义:
左子树不为空的时候,左子树的结点值小于根节点,右子树不为空时,右子树的结点值大于根节点,左右子树分别为二叉查找树
2. 二叉查找树的最左边的结点即为最小值,要查找最小值,只需遍历左子树的结点直到为空为止,同理,最右边的结点结尾最大值,要查找最大值,只需遍历右子树的结点直到为空为止。二叉查找树的插入查找和删除都是通过递归的方式来实现的,删除一个结点的时候,先找到这个结点S,如果这个结点左右孩子都不为空,这时并不是真正的删除这个结点S,而是在其右子树找到后继结点,将后继结点的值付给S,然后删除这个后继结点即可。如果结点S的左孩子或者右孩子为空,可以直接删除这个结点S。
3. 二叉查找树的python实现:
class TreeNode: def __init__(self,val): self.val=val; self.left=None; self.right=None; def insert(root,val): if root is None: root=TreeNode(val); else: if val<root.val: root.left=insert(root.left,val); #递归地插入元素 elif val>root.val: root.right=insert(root.right,val); return root; def query(root,val): if root is None: return ; if root.val is val: return 1; if root.val <val: return query(root.right,val); #递归地查询 else: return query(root.left,val); def findmin(root): if root.left: return findmin(root.left); else: return root; def delnum(root,val): if root is None: return ; if val<root.val: return delnum(root.left,val); elif val>root.val: return delnum(root.right,val); else: # 删除要区分左右孩子是否为空的情况 if(root.left and root.right): tmp=finmin(root.right); #找到后继结点 root.val=tmp.val; root.right=delnum(root.right,val); #实际删除的是这个后继结点 else: if root.left is None: root=root.right; elif root.right is None: root=root.left; return root; #测试代码 root=TreeNode(3); root=insert(root,2); root=insert(root,1); root=insert(root,4); #print query(root,3); print query(root,1); root=delnum(root,1); print query(root,1);
结果:
1
None
>
总结
以上就是本文关于python实现二叉查找树实例代码的全部内容,希望对大家有所帮助。感兴趣的朋友可以继续参阅本站其他相关专题,如有不足之处,欢迎留言指出。感谢朋友们对本站的支持!
风云阁资源网 Design By www.bgabc.com
广告合作:本站广告合作请联系QQ:858582 申请时备注:广告合作(否则不回)
免责声明:本站资源来自互联网收集,仅供用于学习和交流,请遵循相关法律法规,本站一切资源不代表本站立场,如有侵权、后门、不妥请联系本站删除!
免责声明:本站资源来自互联网收集,仅供用于学习和交流,请遵循相关法律法规,本站一切资源不代表本站立场,如有侵权、后门、不妥请联系本站删除!
风云阁资源网 Design By www.bgabc.com
暂无评论...
更新日志
2024年09月23日
2024年09月23日
- Merryland《Merryland》[320K/MP3][69.48MB]
- 苏芮.1991-停在我心里的温柔【福茂】【WAV+CUE】
- 苏慧伦.2020-面面Every.Side.of.Me【相信音乐】【WAV+CUE】
- 群星.1991-不一样的感觉REMIX【宝丽金】【WAV+CUE】
- 银霞.1983-《你那好冷的小手》珍藏纪念版[WAV分轨]
- 银霞.2002-《国语巨星专辑VOL.3》2CD台湾版[WAV+CUE]
- 金池刘罡《昨日情歌HQ》头版限量编号[低速原抓WAV+CUE]
- 段奥娟.2024-23·岁碎念【白米范】【FLAC分轨】
- 顺子.2001-昨日·唯一·更多·顺子自选辑【魔岩】【WAV+CUE】
- 无印良品.1999-私藏三首·原创相对论(EP)【滚石】【WAV+CUE】
- Merryland《Merryland》[FLAC/分轨][170.22MB]
- 庄锭欣 ELKIE《没有你的未来》[320K/MP3][15.78MB]
- 庄锭欣 ELKIE《没有你的未来》[FLAC/分轨][36MB]
- TchaikovskySwanLake,Op.20柴可夫斯基天鹅湖(2013)SACD[Hi-Res]
- 24bit达人艺典《琴歌终极版》整轨WAV+CUE