二叉查找树平均查找长度代码实现

二叉查找树的平均查找长度可以通过递归的方式进行计算。下面是一个示例代码实现：

class Node:
    def __init__(self, key):
        self.left = None
        self.right = None
        self.key = key

def insert(root, key):
    if root is None:
        return Node(key)
    else:
        if root.key == key:
            return root
        elif root.key < key:
            root.right = insert(root.right, key)
        else:
            root.left = insert(root.left, key)
    return root

def search(root, key):
    if root is None or root.key == key:
        return root
    if root.key < key:
        return search(root.right, key)
    return search(root.left, key)

def get_tree_height(root):
    if root is None:
        return 0
    else:
        left_height = get_tree_height(root.left)
        right_height = get_tree_height(root.right)
        return max(left_height, right_height) + 1

def get_average_search_length(root):
    if root is None:
        return 0
    else:
        left_height = get_tree_height(root.left)
        right_height = get_tree_height(root.right)
        left_avg = get_average_search_length(root.left)
        right_avg = get_average_search_length(root.right)
        return (left_height + right_height + 1) / 2 + left_avg + right_avg

# 示例用法
root = None
root = insert(root, 50)
root = insert(root, 30)
root = insert(root, 20)
root = insert(root, 40)
root = insert(root, 70)
root = insert(root, 60)
root = insert(root, 80)

avg_search_length = get_average_search_length(root)
print("Average search length:", avg_search_length)

这段代码实现了二叉查找树的插入、搜索、获取树高度和计算平均查找长度的功能。你可以根据需要修改插入的节点和搜索的关键字来进行测试。