Как я могу рекурсивно вставить последовательность Фибоначчи в двоичное дерево

Question

Надеюсь, кто-то может помочь, я не программист, но мне было интересно изучить последовательность Фибоначчи и ее рекурсивное дерево ...

Я создал класс Binary Tree вместе со связанным TreeNodeкласс, и хотите сгенерировать двоичное дерево рекурсивных вызовов, созданных с помощью:

f (n) = f (n-1) + f (n-2) для заданного значения n

Я бы хотел добавить его как метод InsertFibonacci моего класса Binary Tree, заменив стандартный метод Insert:

def insertNode(self, root, inputData):
    if root == None:
        return self.addNode(inputData)
    else:
        if inputData <= root.nodeData:
            root.left = self.insertNode(root.left, inputData)
        else:
            root.right = self.insertNode(root.right, inputData)
        return root

Я бы добавил какой-нибудь декоратор в функцию Fib?

# Fib function
def f(n):

    def helper(n):
        left = f(n-1)
        right = f(n-2)
        return left,right

    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        left, right = helper(n)
        return left + right

Answer 1

Вот самое простое решение, которое я могу придумать:

class FibTree(object):
    def __init__(self, n):
        self.n = n
        if n < 2:
            self.value = n
        else:
            self.left = FibTree(n - 1)
            self.right = FibTree(n - 2)
            self.value = self.left.value + self.right.value

Answer 2

Вот один из способов:

def insertFibonacci(self, n):
    current = self.addNode(n)
    if n > 1:
        current.left = self.insertFibonacci(n-1)
        current.right = self.insertFibonacci(n-2)
        # if you want the fibonacci numbers instead of the calls:
        # current.value = current.left.value + current.right.value
    return current

Предположим, положительный n.Должен возвращать корень дерева вызовов Фибоначчи.

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