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

Question

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

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

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

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

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 

ли я добавить somekind из декоратора функции Фибо?

# 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. Должен возвращать корень дерева вызовов фибоначчи.

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