二叉排序树怎么构造_折半查找和二叉排序树的时间性能

二叉排序树怎么构造_折半查找和二叉排序树的时间性能折半查找和二叉排序树折半查找(Binary Search)和二叉排序树(Binary Search Tree)是两种常用的查找算法。1. 折半查找算法实现:折半查找是一种在有序数组中查找指定素的算法。它的基本思想是将数组分成两部分,然后判断目标素与中间素的大小关系,进而确定

折半查找和二叉排序树   折半查找(Binary Search)和二叉排序树(Binary Search Tree)是两种常用的查找算法。   1. 折半查找算法实现:   折半查找是一种在有序数组中查找指定素的算法。它的基本思想是将数组分成两部分,然后判断目标素与中间素的大小关系,进而确定目标素在哪一部分中,然后再在该部分中进行查找,如此循环直到找到目标素或者确定目标素不存在。   以下是折半查找的算法实现示例:   “`python   def binary_search(arr, target):   low = 0   high = len(arr) – 1   while low <= high:   mid = (low + high) // 2   if arr[mid] == target:   return mid   elif arr[mid] < target:   low = mid + 1   else:   high = mid – 1   return -1 # 目标素不存在   arr = [5, 14, 18, 21, 23, 29, 31, 35]   target = 29   result = binary_search(arr, target)   print(“小于29的最大关键字值是:”, arr[result-1]) # 输出:23   “`   2. 二叉排序树算法实现:   二叉排序树是一种特殊的二叉树,它的每个节点的左子树的所有节点的值都小于该节点的值,右子树的所有节点的值都大于该节点的值。通过这种特性,可以实现高效的插入和删除操作。   以下是二叉排序树的算法实现示例:   “`python   class TreeNode:   def __init__(self, val):   self.val = val   self.left = None   self.right = None   def insert(root, val):   if root is None:   return TreeNode(val)   if val < root.val:   root.left = insert(root.left, val)   else:   root.right = insert(root.right, val)   return root   def delete(root, val):   if root is None:   return root   if val < root.val:   root.left = delete(root.left, val)   elif val > root.val:   root.right = delete(root.right, val)   else:   if root.left is None:   return root.right   elif root.right is None:   return root.left   else:   min_node = find_min(root.right)   root.val = min_node.val   root.right = delete(root.right, min_node.val)   return root   def find_min(root):   while root.left:   root = root.left   return root   def inorder_traversal(root):   if root:   inorder_traversal(root.left)   print(root.val, end=” “)   inorder_traversal(root.right)   # 构造二叉排序树   keys = [45, 24, 53, 12, 37, 93, 13]   root = None   for key in keys:   root = insert(root, key)   # 删除关键字53和24   root = delete(root, 53)   root = delete(root, 24)   # 中序遍历二叉排序树   inorder_traversal(root) # 输出:12 13 37 45 93   “`

2024最新激活全家桶教程,稳定运行到2099年,请移步至置顶文章:https://sigusoft.com/99576.html

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请联系我们举报,一经查实,本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处:https://sigusoft.com/39369.html

(0)
上一篇 2024年 9月 8日 上午10:47
下一篇 2024年 9月 8日

相关推荐

关注微信