Unsorted Двоичное деревья, Traversal, размер

Question

1. Создайте функцию traverse, которая занимает первое из которых является дерево, второй empty_fn(), leaf_fn(arg), третий является node_fn(arg0,arg1,arg2) если дерево пусто функция empty_fn() которая принимает 0 аргументы должны были вызвать. Поэтому, если мы сталкиваемся с листом, нужно запустить leaf_fn(arg), и если у нас есть поддерево, то должна быть запущена функция node_fn(arg0,arg1,arg2).

2. Создайте функцию contains_key, которая вызывает traverse() и проверяет, существует ли ключ в данном двоичном дереве. Эта функция по существу предназначена для создания трех функций, используемых в качестве аргументов в traverse.

3. Создайте новую функцию tree_size(), которая вызывает функцию traverse() и возвращает размер дерева.

Примечание: дерево не обязательно должны быть отсортированы в правильном пути, например [[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 

---

Здесь - мои попытки решить проблему, учитывая t он образец программы работает с учетом спецификациями:

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(), поэтому мне пришлось рекурсивно решать его. ОДНАКО ни одно из моих решений, кроме первого, не отвечает требованиям, заданным в соответствии с моими вопросами. Я чувствую, что нет способа удовлетворить все три требования, приведенные в примере.

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, []]])) 

Решение не будет работать для вложенных поддеревьев, хотя, было бы полезно получить любую обратную связь. Я оставляю вопрос открытым, чтобы надеяться получить больше ответов.