我如何可以遞歸插入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序列爲二叉樹

回答

相關問題