树遍历中的高阶函数

Question

如何在传递函数以减少冗余的同时创建常见的树操作，如插入和搜索。例如，当传入的值大于当前节点时，递归函数在左分支上调用自己。若我能够传递插入和搜索之类的函数，我就能够排除很多遍历。我看到的主要问题是，两个函数都有不同的基本情况。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)

Answer 1

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

为了重用公共代码，可以使用函数装饰器。实现遍历decorator函数中的树和操作函数中找到的元素的操作的通用代码。您可以按如下方式更改代码：

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)

事实上，它传递函数，正如您在问题中所指出的，并将结果函数重命名为传入函数。上面插入函数的decorator语法是这样做的：

insert = tree_operation(insert)

Answer 2

我认为最好不要将函数的迭代部分组合在一个函数中，因为这会使代码复杂化。但是，如果你认为迭代部分很复杂，并且你需要写一次，你可以重新考虑如下：

def do_iterate(base_function, n, node=root):
    if node == None or node.data == n:
        base_function(n, node)
    elif node.data < n:
        do_iterate(base_function, n, node.right)
    else:
        do_iterate(base_function, n, node.left)

然后，您可以编写自己的base_function，当满足基本条件时将调用该函数。例如，您可以使用base_insert（）和base_search（）函数来代替insert（）和search（）。

def base_insert(n, node):
    if node == None:
        node.data = n
        node.left, node.right, node.middle = None
    else:
        do_iterate(base_insert, n, node.middle)
def base_search(n, node):
    if node == None:
        return false
    else:
        return true

因此，您可以使用以下算法：

do_iterate(base_insert, 7)
do_iterate(base_search, 4)

最后，我不确定它是否比您的简单代码更好。