我如何可以递归插入Fibonacci序列为二叉树

希望有人能帮助，我不是一个程序员，但在探索Fibonacci序列中一直有兴趣，它的递归树...我如何可以递归插入Fibonacci序列为二叉树

我创建二叉树类以及相关的TreeNode类，并且想要生成由以下创建的递归调用的二叉树：

f（n）= f（n-1）+ f（n-2）对于给定的值n

我想将其添加为InsertFibonacci me我的二叉树类的方法，取代标准的插入方法：

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

来源

2012-02-11 Alex2134

你的意思是你想要的数据结构来表示递归斐波那契函数调用关系图？那么你不应该使用二进制*搜索*树。 – 2012-02-11 00:14:55

嗨Larsmans，是的，一个数据结构来表示调用图。调用图不表示接近完全严格的二叉树结构吗？ – Alex2134 2012-02-11 00:20:36

是的，但调用图不是一个二进制*搜索*树，这是'insertNode'好像要实现的。 BST是带有排序约束的标记二叉树，斐波那契调用图不显示。 – 2012-02-11 00:24:35

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

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

来源

2012-02-11 00:22:14

非常感谢Tzaman和Larsmans为您的快速解答！我会尝试这些解决方案。 – Alex2134 2012-02-11 00:27:45

非常感谢@larsmans我已经使用了你的FibTree类，它运行良好。我已经修正它，因此，每个节点包括一个参考到它的父：类FibTree（对象）： \t DEF __init __（个体中，n，母体）： \t \t self.n =正 \t \t self.parent =父 \t \t如果n <2： \t \t \t self.value =正 \t \t \t self.left =无 \t \t \t self.right =无 \t \t其他： \t \t \t自我。左= FibTree（N - 1，自） \t \t \t self.right = FibTree（N - 2，自） \t \t \t self.value = self.left.value + self.right.value 我想就像能够确定给定节点是父母的左右兄弟姐妹一样。这是可能的，通过父节点链接？谢谢亚历克斯 – Alex2134 2012-02-11 17:30:01

当然：'self is self.parent.left'和类似的'right'。 – 2012-02-11 17:41:51

这里有一种方法：

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。应该返回斐波那契呼叫树的根。

请注意，这不会完全是同一种二叉树;它不会满足二叉搜索树所做的排序不变量。我假设你只是想使用你现有的结构，以方便。

来源

2012-02-11 00:20:31 tzaman

非常感谢@larsmans我已经使用了你的FibTree类，它运行良好。我修改了它，因此每个节点都包含对其父项的引用： – Alex2134 2012-02-11 17:26:35

我如何可以递归插入Fibonacci序列为二叉树

回答

相关问题