利用折叠器实现二叉树映射

from functools import reduce

# 定义二叉树节点
class Node:
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.left = None
        self.right = None

# 定义二叉树映射类
class BinaryTreeMap:
    def __init__(self):
        self.root = None

    def insert(self, key, value):
        # 递归插入节点
        def insert_node(node, key, value):
            if node is None:
                return Node(key, value)
            elif key < node.key:
                node.left = insert_node(node.left, key, value)
            elif key > node.key:
                node.right = insert_node(node.right, key, value)
            else:
                node.value = value
            return node

        self.root = insert_node(self.root, key, value)

    def search(self, key):
        # 递归查找节点
        def search_node(node, key):
            if node is None or node.key == key:
                return node
            elif key < node.key:
                return search_node(node.left, key)
            else:
                return search_node(node.right, key)

        node = search_node(self.root, key)
        if node is not None:
            return node.value
        else:
            return None

    def fold(self, func, initial):
        # 利用折叠器将二叉树映射折叠为单个值
        def fold_node(node, func, initial):
            if node is None:
                return initial
            else:
                left_result = fold_node(node.left, func, initial)
                accumulator = func(left_result, node.key, node.value)
                return fold_node(node.right, func, accumulator)

        return fold_node(self.root, func, initial)

# 创建二叉树映射对象
tree_map = BinaryTreeMap()

# 插入键值对
tree_map.insert(1, 'Value 1')
tree_map.insert(2, 'Value 2')
tree_map.insert(3, 'Value 3')
tree_map.insert(4, 'Value 4')

# 查找键对应的值
value = tree_map.search(2)
print(value)  # Output: Value 2

# 使用折叠器将二叉树映射折叠为单个值
result = tree_map.fold(lambda acc, key, value: acc + value, '')
print(result)  # Output: Value 1Value 2Value 3Value 4