Блог

Я пытаюсь реализовать функцию, которая проверяет, является ли вложенный список двоичным деревом
поиска, например [50, [44, 30, 48], [80, [66, 60, 67], 88]] , у меня есть этот список, который представляет дерево
дерево представлено с использованием этой логики

 # Tree in nested list
tree1 = ['a', ['b', ['d',[],[]], ['e',[],[]] ], ['c', ['f',[],[]], []] ]
#
tree2 = ['a',         #root
      ['b',             #left subtree
       ['d', [], []],   #left child of b - empty lists show that there are no children
       ['e', [], []] ], #right child of b
      ['c',             #right subtree
       ['f', [], []],
       [] ]
     ]
 

Есть ли какой-нибудь простой и очевидный способ сделать это. Я довольно новичок в python и структурах данных

Я попытался написать его с помощью функции is_bst

 def is_bsp(list)     
    root = lists[0]
        cur_value = 0
        level = 0
        for i in lists:
            print(i)
            if isinstance(i, list):
                is_bsp(i)
 

Но я не знаю, как продолжать использовать это

пример ввода / вывода

 is_bsp([50, [44, 30, 48], [80, [66, 60, 67], 88]])
=> True

is_bsp([50, [44, 30, 48], [49, [66, 60, 67], 88]])
=> False
 

Я бы сгладил дерево до последовательности, а затем проверил, отсортирован ли результат.

 def flatten_tree(lst):
    if not isinstance(lst, (list, tuple)):
        return [lst]
    if not lst:
        return []
    if len(lst) != 3:
        raise ValueError(f"expected is [root, left, right], got {lst}")
    return [*flatten_tree(lst[1]), lst[0], *flatten_tree(lst[2])]

def is_bsp(tree):
    # TODO: if empty: return True
    try:
        lst = flatten_tree(tree)
        return all(a <= b for a, b in zip(lst, lst[1:]))    # is sorted?
    except (ValueError, TypeError):
        return False
    
 

Приведенный выше код не обрабатывает пустое дерево (не знаю, как оно представлено) и не проверяет циклические ссылки (вредоносный ввод может вызвать бесконечную рекурсию).