二叉排序树(BST)又称二叉查找树、二叉搜索树
二叉排序树(Binary Sort Tree)又称二叉查找树。它或者是一棵空树;或者是具有下列性质的二叉树:
1.若左子树不空,则左子树上所有结点的值均小于根结点的值;
2.若右子树不空,则右子树上所有结点的值均大于根节点的值;
3.左、右子树也分别为二叉排序树。
- 求树深度
- 按序输出节点值(使用中序遍历)
- 查询二叉搜索树中一个具有给点关键字的结点,返回该节点的位置。时间复杂度是O(h),h是树的高度。
- 递归/迭代求最大关键字元素
- 递归/迭代求最小关键字元素
# -*- coding:utf-8 -*- ''' 用Python实现二叉搜索树。 ''' class Node(): def __init__(self, x): self.val = x self.left = None self.right = None #求树的深度 def depth(root): if root is None: return 0 else: return 1 + max(depth(root.left), depth(root.right)) #按序输出结点值(中序遍历) def input_in_order(root): if root is None: return input_in_order(root.left) print(root.val) input_in_order(root.right) #(递归实现 、迭代实现)查询二叉搜索树中一个具有给点关键字的结点,返回该节点的位置。时间复杂度是O(h),h是树的高度。 #递归实现 def search1(root, value): if root is None or root.val == value: return root if root.val > value: return search1(root.left, value) if root.val < value: return search1(root.right, value) #迭代实现 def search2(root, value): while root != None and root.val != value: if root.val > value: root = root.left elif root.val < value: root = root.right return root #求最大关键字元素 #迭代实现 def max_value1(root): while root != None and root.left != None: root = root.right if root is None: return root else: return root.val #递归实现 def max_value2(root): if root == None: return root elif root.right == None: return root.val else: return max_value2(root.right) #求最小关键字元素 #递归实现 def min_value1(root): if root is None: return root elif root.left is None: return root.val else: return min_value1(root.left) #迭代实现 def min_value2(root): if root is None: return root while root.left !=None: root = root.left return root.val if __name__ == '__main__': a = Node(15) b = Node(6) c = Node(18) d = Node(4) e = Node(8) f = Node(17) g = Node(20) h = Node(13) i = Node(9) a.left = b a.right = c b.left = d b.right = e c.left = f c.right = g e.right = h h.left = i print(search1(a, 13)) print(search2(a,13)) print(max_value1(a)) print(max_value2(a)) print(min_value1(a)) print(min_value2(a))
ps:从二叉查找树BST中查找元素X,返回其所在结点的地址,查找的次数取决于树的高度。
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持。
免责声明:本站文章均来自网站采集或用户投稿,网站不提供任何软件下载或自行开发的软件!
如有用户或公司发现本站内容信息存在侵权行为,请邮件告知! 858582#qq.com
暂无“Python实现二叉搜索树BST的方法示例”评论...
《魔兽世界》大逃杀!60人新游玩模式《强袭风暴》3月21日上线
暴雪近日发布了《魔兽世界》10.2.6 更新内容,新游玩模式《强袭风暴》即将于3月21 日在亚服上线,届时玩家将前往阿拉希高地展开一场 60 人大逃杀对战。
艾泽拉斯的冒险者已经征服了艾泽拉斯的大地及遥远的彼岸。他们在对抗世界上最致命的敌人时展现出过人的手腕,并且成功阻止终结宇宙等级的威胁。当他们在为即将于《魔兽世界》资料片《地心之战》中来袭的萨拉塔斯势力做战斗准备时,他们还需要在熟悉的阿拉希高地面对一个全新的敌人──那就是彼此。在《巨龙崛起》10.2.6 更新的《强袭风暴》中,玩家将会进入一个全新的海盗主题大逃杀式限时活动,其中包含极高的风险和史诗级的奖励。
《强袭风暴》不是普通的战场,作为一个独立于主游戏之外的活动,玩家可以用大逃杀的风格来体验《魔兽世界》,不分职业、不分装备(除了你在赛局中捡到的),光是技巧和战略的强弱之分就能决定出谁才是能坚持到最后的赢家。本次活动将会开放单人和双人模式,玩家在加入海盗主题的预赛大厅区域前,可以从强袭风暴角色画面新增好友。游玩游戏将可以累计名望轨迹,《巨龙崛起》和《魔兽世界:巫妖王之怒 经典版》的玩家都可以获得奖励。
更新动态
2025年03月16日
2025年03月16日
- 小骆驼-《草原狼2(蓝光CD)》[原抓WAV+CUE]
- 群星《欢迎来到我身边 电影原声专辑》[320K/MP3][105.02MB]
- 群星《欢迎来到我身边 电影原声专辑》[FLAC/分轨][480.9MB]
- 雷婷《梦里蓝天HQⅡ》 2023头版限量编号低速原抓[WAV+CUE][463M]
- 群星《2024好听新歌42》AI调整音效【WAV分轨】
- 王思雨-《思念陪着鸿雁飞》WAV
- 王思雨《喜马拉雅HQ》头版限量编号[WAV+CUE]
- 李健《无时无刻》[WAV+CUE][590M]
- 陈奕迅《酝酿》[WAV分轨][502M]
- 卓依婷《化蝶》2CD[WAV+CUE][1.1G]
- 群星《吉他王(黑胶CD)》[WAV+CUE]
- 齐秦《穿乐(穿越)》[WAV+CUE]
- 发烧珍品《数位CD音响测试-动向效果(九)》【WAV+CUE】
- 邝美云《邝美云精装歌集》[DSF][1.6G]
- 吕方《爱一回伤一回》[WAV+CUE][454M]