树遍历中的高阶函数

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

来源

2014-10-19 Something Jones

你可以自己编写任何代码吗？ – Totem 2014-10-19 02:29:33

如果你编辑你的文章，并将其粘贴在那里的代码格式选项，这将是更多的可读性;） – Totem 2014-10-19 02:35:33

它不会让我编辑评论，它看起来像我已经把代码formater在，但它didn没有理由。 – 2014-10-19 02:39:37

您的插入逻辑不正确。您正尝试在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)

事实上它传递的功能，当你有问题注意加重命名为函数传递结果的功能。以上为插入功能装饰语法做到这一点：

insert = tree_operation(insert)

来源

2014-10-19 20:09:05 Reith

这段代码很漂亮。谢谢。 – 2014-10-20 00:14:03

我认为它能够更好地不是在单独的一个，因为它的代码复杂的功能迭代部分结合起来。但是，如果你认为迭代部分是复杂的，你需要编写一次，就可以重新因素它如下：

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)

最后，我不知道这是不是你简单的代码更好。

来源

2014-10-19 20:24:39

树遍历中的高阶函数

回答

相关问题