未排序的二叉搜索树、遍历、大小

Question

创建一个函数traverse需要4个args第一个是树，第二个是empty_fn()，leaf_fn(arg)，第三个是node_fn(arg0,arg1,arg2) 如果树为空，则应调用采用 0 个参数的函数 empty_fn()。因此，如果我们遇到一个叶子，leaf_fn(arg) 应该是运行，如果我们有一个子树，函数 node_fn(arg0,arg1,arg2) 应该是运行.
创建函数 contains_key 调用 traverse() 并检查给定的二叉树中是否存在键。此函数本质上是为了创建 traverse 用作参数的三个函数。
创建一个新函数 tree_size()，它调用 traverse() 函数和 returns 一棵树的大小。

注意： 树不一定必须以正确的方式排序，例如 [[3,5,4],1,0] 是一棵有效的树

例子

def empty_fn():
    return 0


def leaf_fn(key):
    return key**2


def node_fn(key, left_value, right_value): 
    return key + left_value
>>> traverse([6, 7, 8], inner_node_fn, leaf_fn, empty_tree_fn)
43

这里是我解决问题的尝试，给定规范给出的程序示例运行ning：

def traverse(tree,empty_tree_fn,leaf_fn, inner_node_fn ):
    if is_empty_tree(tree):
        return empty_tree_fn()
    else:
        if is_leaf(tree[0]):
            tree[0]=leaf_fn(tree[0])

        elif is_leaf(tree[2]):
            tree[2]=leaf_fn(tree[2])
        return inner_node_fn(tree[1],tree[0],tree[2])

如果我运行它针对示例给出的输入我得到相同的输出这意味着这是正确的方法吗？然而，一旦我们进入问题的第二部分，它就会变得更加复杂，因为我必须创建一个新版本的 traverse() namley traverse2_0 来满足问题 1 的要求。这是我的代码：

def traverse2_0(tree,empty_tree_fn,leaf_fn, inner_node_fn ):
    if is_empty_tree(tree):
        return empty_tree_fn()
    else:
        """if is_leaf(tree[0]) and is_leaf(tree[2]):
            return leaf_fn(tree[0]) or leaf_fn(tree[2])""" #lazy mechanism
        if is_leaf(tree[0]):
            if leaf_fn(tree[0]):
                return True
        if is_leaf(tree[2]):
            if leaf_fn(tree[2]):
                return True
        else:
            return inner_node_fn(tree[1],tree[0],tree[2])
    return False
def contains_key(key, tree):
    #print (tree)
    def empty_fn(tree):
        return not is_empty_tree(tree)
    def leaf_fn(side):
        return side==key
    def inner_node_fn(k,left,right):
        if  isinstance(left,list) and isinstance(right,list):
            return contains_key(key, left) or contains_key(key, right)
        elif  isinstance(left,list):
            return contains_key(key,left)
        elif isinstance(right,list):
            return contains_key(key, right)
    if key==tree[1]:
        return True
    else:
        return traverse2_0(tree,empty_fn,leaf_fn,inner_node_fn)

一旦我们到达第三个，如果我想使用 traverse() 就更复杂了，所以我不得不递归地解决它。但是，除了第一个解决方案外，我的解决方案都不符合根据我的 L.I 提出的问题的要求。我觉得没有办法满足示例中的所有三个要求。

def tree_size(tree):
    if not tree: #corresponds to empty_tree_fn
        return 0
    if isinstance(tree[0],list): #corresponds to inner_node_fn
        return tree_size(tree[0])+tree_size(tree[1:])
    else:
        return 1+tree_size(tree[1:]) #corresponds to leaf_fn
print (tree_size( [[0,1,2],2,[1,3,2]]))

这是一个很长的问题，我知道这一点并感谢任何相关的回答。

Answer 1

from tree import *
def traverse(bst,empty_fn,leaf_fn,inner_node_fn):
    if is_empty_tree(bst):
        return empty_fn()
    else:
        left,root,right= bst[0],bst[1],bst[2]
        if is_leaf(left):
            left= leaf_fn(left)
        if is_leaf(right):
            right=leaf_fn(right)
        return inner_node_fn(root,left, right)
def contains_key(key, tree):
    def empty_fn():
        return not is_empty_tree(tree)
    def leaf_fn(side):
        return side==key
    def inner_node_fn(k,left,right):
        if k==key:
            return True
        if isinstance(left,list) and isinstance(right,list):
            return contains_key(key,left) or contains_key(key,right)
        elif isinstance(right,list):
            return contains_key(key,right)
        elif isinstance (left,list):

            return contains_key(key,left)
        else:
            return right or left

    return traverse(tree,empty_fn,leaf_fn,inner_node_fn)

print(contains_key("m", [["m",6,4], 7, [[2, 3, 4], 0, []]]))

尽管该解决方案不适用于嵌套子树，但仍希望收到任何反馈。我将问题悬而未决，希望能收到更多答案

未排序的二叉搜索树、遍历、大小

Unsorted Binary Search Trees, Traversal, Size

python

algorithm

functional-programming

tree-traversal

binary-search-tree