折半查找和二叉排序树 折半查找（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/46300.html
