Python中的二叉樹大小函數

我已經寫了幾個函數來計算二叉樹的大小。第一個（函數1）工作得很好，在類之外聲明，它不是類的成員函數。然而，第二個是班級的成員功能是給我奇怪的結果。我很困惑！任何幫助，將不勝感激。Python中的二叉樹大小函數

Function 1 
    def size(root): 
     if root is None: 
      return 0 
     else: 
      return size(root.left)+ 1+ size(root.right) 


Function 2 
    def size(self): 
     if self.left is None or self.right is None: 
       return 0 
     else: 
       return self.left.size()+1+self.right.size()

來源

2015-04-25 avinash shah

您的if語句條件在函數之間是不等價的。具體來說，如果左邊或右邊的子項不存在，第二個函數返回0。這可能不是你想要的。 – Shashank

if self.left is None or self.right is None:

如果其中一人是無，返回0

，你需要至少得到正確的大小+ 1，如果剩下的就是無

我認爲你需要像：

leftSize = self.left.size() if self.left else 0 
rightSize = self.right.size() if self.right else 0 
return leftSize + 1 + rightSize

我還沒試過。

來源

2015-04-25 21:01:22 Saloparenator

謝謝！您的幫助。 –

它工作得很好.... –

第二個功能是不準確的，例如

x = Tree() 
x.left = Tree() 
x.right = None

在上述例子中，x.size()將評估爲零，因爲你正在考慮要麼left is None或right is None返回0（這是上述平凡真例）。你需要調整你的邏輯。

def size(self): 
    total = 1 #any instantiated object has a size of at least 1. 
    if self.left is not None: #feel free to add additional validity checks, i.e. instanceof(Tree...) 
     total += self.left.size() 
    if self.right is not None: 
     total += self.right.size() 
    return total

來源

2015-04-25 21:02:34

謝謝！ +1，感謝您的幫助。 –

Python中的二叉樹大小函數

回答

相關問題