树遍历中的高阶函数

琼斯

我如何在传递函数以减少冗余的同时创建诸如插入和搜索之类的常见树操作。例如，当传入的值大于当前节点时，递归函数将在左侧分支上调用自身。如果我能够传递诸如插入和搜索之类的功能，则可以排除很多遍历。我看到的主要问题区域是这两个函数具有不同的基本情况。python中的示例解决方案将不胜感激。

def insert(n, node = root):
    if node == None:
        node.data = n
        node.left, node.right, node.middle = None
    elif node.data == n:
        insert(node.middle)
    elif node.data < n:
        insert(right)
    else:
        insert(left)


def search(n, node = root):
    if node == None:
        return false
    elif node.data == n:
        return true
    elif node.data < n:
        search(right)
    else:
        search(left)

瑞思

您的插入逻辑不正确。您正在尝试在上设置属性None。

要重用通用代码，可以使用函数装饰器。在装饰器函数中实现遍历树的通用代码，并在操作函数中实现对找到的元素的操作。您可以按以下方式更改代码：

def tree_operation(f):
    def recursive_wrapper(n, node):
       if node == None or node.data == n:
           # tree traversed to final point. do action for found element or
           # None
           return f(n, node)
       # try getting closer to interesting element
       elif node.data < n:
           return recursive_wrapper(n, node.right)
       else:
           return recursive_wrapper(n, node.left)
    return recursive_wrapper

@tree_operation
def search(n, node):
    if node == None:
        return False
    elif node.data == n:
        return True

@tree_operation
def insert(n, node):
    if node == None:
        # this obviously fail
        node.data = n
        node.left, node.right, node.middle = None
    elif node.data == n:
        insert(node.middle)

实际上，正如您所提到的，它可以传递函数，并将结果函数重命名为传递函数。上面插入函数的装饰器语法可以做到这一点：