我如何将Fibonacci数列递归插入二叉树中

Question

希望有人能帮忙，我不是程序员，但对斐波那契数列和它的递归树很感兴趣...

我创建了一个二叉树类，还有一个相关的树节点类，想要生成一个由以下递归调用构成的二叉树：

f(n) = f(n-1) + f(n-2)，这是给定n值的公式

我想把这个作为我的二叉树类中的一个InsertFibonacci方法，替代标准的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

这里有一种方法：

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 是一个正数。这个方法应该返回斐波那契调用树的根节点。

需要注意的是，这个树和普通的二叉树不完全一样；它不会像二叉搜索树那样遵循特定的顺序规则。我假设你只是想利用你现有的结构，方便一些。

Answer 2

这是我能想到的最简单的解决办法：

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