好资源导航 » 文章资讯 » Python实现二叉搜索树BST的方法示例

Python实现二叉搜索树BST的方法示例

2023-08-18 10:00:05 67

二叉排序树（BST）又称二叉查找树、二叉搜索树

二叉排序树(BinarySortTree)又称二叉查找树。它或者是一棵空树；或者是具有下列性质的二叉树：

1.若左子树不空，则左子树上所有结点的值均小于根结点的值；
2.若右子树不空，则右子树上所有结点的值均大于根节点的值；
3.左、右子树也分别为二叉排序树。

求树深度
按序输出节点值（使用中序遍历）
查询二叉搜索树中一个具有给点关键字的结点，返回该节点的位置。时间复杂度是O(h),h是树的高度。
递归/迭代求最大关键字元素
递归/迭代求最小关键字元素

#-*-coding:utf-8-*-
'''
用Python实现二叉搜索树。
'''


classNode():
def__init__(self,x):
self.val=x
self.left=None
self.right=None

#求树的深度
defdepth(root):
ifrootisNone:
return0
else:
return1+max(depth(root.left),depth(root.right))


#按序输出结点值（中序遍历）
definput_in_order(root):
ifrootisNone:
return
input_in_order(root.left)
print(root.val)
input_in_order(root.right)



#（递归实现、迭代实现）查询二叉搜索树中一个具有给点关键字的结点，返回该节点的位置。时间复杂度是O(h),h是树的高度。
#递归实现
defsearch1(root,value):
ifrootisNoneorroot.val==value:
returnroot
ifroot.val>value:
returnsearch1(root.left,value)
ifroot.valvalue:
root=root.left
elifroot.val
ps:从二叉查找树BST中查找元素X，返回其所在结点的地址，查找的次数取决于树的高度。


以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持毛票票。

返回顶部
514930285
czq8825@qq.com

Python实现二叉搜索树BST的方法示例

热门推荐

随机推荐