二叉查找算法python

二叉查找算法是一种用于在二叉搜索树中查找特定值的算法。在Python中，可以使用递归来实现二叉查找算法。下面是一个简单的二叉查找算法的Python代码实现：

class Solution:
    def searchBST(self, root: TreeNode, val: int) -> TreeNode:
        if not root:
            return None
        if val == root.val:
            return root
        elif val < root.val:
            return self.searchBST(root.left, val)
        else:
            return self.searchBST(root.right, val)

在这个代码中，我们首先检查根节点是否为空。如果根节点为空，则返回None表示未找到。如果根节点的值等于目标值val，则返回根节点。如果目标值小于根节点的值，则递归地在左子树中查找。如果目标值大于根节点的值，则递归地在右子树中查找。

相关问题

最优二叉查找树 python

最优二叉查找树，也称为哈夫曼树或者权重平衡树，是一种二叉树，它的叶子节点存储着数据元素，而其他节点则存储着权重值。在最优二叉查找树中，每个节点的权重值等于其本身的权重值加上其子树中所有节点的权重值之和。因此，最优二叉查找树的根节点具有最小的权重值。

在 Python 中实现最优二叉查找树需要使用动态规划算法。具体来说，我们可以使用一个二维数组来存储每个子树的最小权重值，然后通过填充数组中的值来逐步构建最优二叉查找树。

以下是一个简单的 Python 实现：

def optimal_bst(keys, freq):
    n = len(keys)
    cost = [[0 for _ in range(n)] for _ in range(n)]
    for i in range(n):
        cost[i][i] = freq[i]
    for L in range(2, n+1):
        for i in range(n-L+2):
            j = i+L-1
            cost[i][j] = float('inf')
            for k in range(i, j+1):
                c = 0 if k == i else cost[i][k-1]
                c += 0 if k == j else cost[k+1][j]
                c += sum(freq[i:j+1])
                if c < cost[i][j]:
                    cost[i][j] = c
    return cost[n-1]

keys = [10, 12, 20]
freq = [34, 8, 50]
print(optimal_bst(keys, freq)) # 输出结果为 142

一、 实验内容： 二叉查找算法 二、 程序清单

一、 实验内容：二叉查找算法，也称为二分搜索法，是一种在有序数组中快速查找特定元素的有效算法。其基本思想是从数组中间位置开始比较，如果目标值大于中间元素，则在右侧半部分继续查找；如果小于，则在左侧半部分查找，直到找到目标值或者搜索范围为空。这种搜索方式每次都能将搜索区间减半，效率较高。

二、 程序清单（以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  # 如果未找到目标值，返回-1表示不存在

# 示例数组
sorted_array = [1, 3, 5, 7, 9]
target_value = 5

# 调用函数并打印结果
result_index = binary_search(sorted_array, target_value)
if result_index != -1:
    print(f"目标值 {target_value} 的索引是：{result_index}")
else:
    print(f"{target_value} 不在数组中.")