Как искать узлы двоичного дерева, чтобы получить самое длинное дерево в python, используя ADT - PullRequest
Новая
       15

Как искать узлы двоичного дерева, чтобы получить самое длинное дерево в python, используя ADT

0 голосов
/ 08 ноября 2018 
T = [[[[], [3, []]], [5, [[[[], [6, []]], [2, [[], [1, []]]]], [4, [[], [3, [[], [7, []]]]]]]]], [2, [[], [8, []]]]]

является представлением двоичного дерева.

ВЫШЕ КОД ДЛЯ T ДЛИННО, ПРОКРУТКА ПО ПОЛНОМУ КОДУ

Я ищу самое длинное дерево, у которого сумма узлов кратна данному числу.

Пример, приведенный 7 дерево T выше как searchMax(T, 7), [[2,5], [4,3], [7]] возвращает, поскольку оно самое длинное, а также сумма которого кратна 7

Pictorial representation

Я определил следующий код 

def cons(x, y):
    return [x, y]

def car(p):
    return p[0]

def cdr(p):
    return p[1]

nil = []

def makeBinTree(root, left, right):
    return cons(left, cons(root, right))

emptyTree = nil


def isEmpty(tree):
    if len(tree) < 1:
        return True
    else:
        return False

def root(tree):
    return tree[1][0]

def left(tree):
    return tree[0][1]

def right(tree):
    return [1][1]

def searchMax(tree, number):

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

1 Ответ

0 голосов
/ 08 ноября 2018

Я бы написал функцию, которая перебирает все возможные пути в дереве. Затем я перебрал бы эти пути и выбрал бы те, которые складываются в кратные семь, а затем из числа тех, кто выбрал самый длинный. 

def isEmpty(tree):
    if len(tree) < 1:
        return True
    else:
        return False

def root(tree):
    return tree[1][0]

def left(tree):
    return tree[0]

def right(tree):
    return tree[1][1]

def iter_all_paths(t):
    if isEmpty(t):
        return
    yield [root(t)]
    for child in (left(t), right(t)):
        for path in iter_all_paths(child):
            yield [root(t)] + path

def searchMax(t, x):
    #find all paths that add up to a multiple of x
    candidates = []
    for path in iter_all_paths(t):
        if sum(path) % x == 0:
            candidates.append(path)
    if not candidates: 
        return None
    return max(candidates, key=len)

T = [[[[], [3, []]], [5, [[[[], [6, []]], [2, [[], [1, []]]]], [4, [[], [3, [[], [7, []]]]]]]]], [2, [[], [8, []]]]]
print(searchMax(T, 7))

Результат: 

[2, 5, 4, 2, 1]

Это отличается от вашего ожидаемого результата, [2, 5, 4, 3, 7]. Два решения имеют одинаковую длину, поэтому я предполагаю, что можно возвращать одно или другое. Мое решение возвращает крайний левый путь, если есть связь в длину.

Возможно, вы думаете "на самом деле я не хочу самую длинную длину пути, а скорее самую большую сумму узлов". Тогда [2, 5, 4, 3, 7] побьет [2, 5, 4, 2, 1] на семь. Если это то, что вы хотите, вы можете изменить последнюю строку с searchMax на return max(candidates, key=sum).

Вы также можете подумать: «Я бы предпочел, чтобы результатом был список списков, а не список целых чисел. Я хочу, чтобы каждый подсписок суммировался с числом, кратным числу. Вместо [2, 5, 4, 3, 7], я хочу [[2, 5], [4, 3], [7]].

Вы можете написать функцию, которая упорядочивает список по частям, которые складываются в число, и вызывать эту функцию перед возвратом из searchMax. 

def chunk(seq, x):
    result = [[]]
    for item in seq:
        result[-1].append(item)
        if sum(result[-1]) % x == 0:
            result.append([])
    if not result[-1]:
        del result[-1]
    return result

#later, in searchMax...
    return chunk(max(candidates, key=len), x)

Результат: 

[[2, 5], [4, 2, 1]]
...