如何递归地将Fibonacci序列插入到二进制文件中

Question

希望有人能帮忙，我不是程序员，但有兴趣探索斐波那契序列和它的递归树。。。在

我已经创建了一个二叉树类和一个相关的TreeNode类，并希望生成一个由以下对象创建的递归调用的二叉树：

f(n) = f(n-1) + f(n-2) for a given value of 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函数中添加某种装饰器吗？在

^{pr2}$

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。 应该返回fibonacci调用树的根。在

注意，这并不是完全相同的二叉树；它不能满足二叉搜索树那样的排序不变量。我假设你只是为了方便而使用现有的结构。在

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