'NoneType'對象沒有屬性'height'

Question

我試圖找到BST的高度，但它給出的錯誤如'NoneType' object has no attribute 'height'。我無法弄清楚錯誤。

class BST: 
    def __init__(self,val): 
     self.left = None 
     self.right = None 
     self.root = val 
    def insert(self,data): 
     if self.root == None: 
      self.root = BST(data) 
     elif data > self.root: 
      if self.right == None: 
       self.right = BST(data) 
      else: 
       self.right.insert(data) 
     elif data < self.root: 
      if self.left == None: 
       self.left = BST(data) 
      else: 
       self.left.insert(data) 
    def inorder(self): 
     if self.left != None: 
      self.left.inorder() 
     print(self.root) 
     if self.right != None: 
      self.right.inorder() 
    def height(self): 
     if self.root == None: 
      return 0 
     else: 
      return 1 + max(self.left.height(), self.right.height()) 

t = BST(4) 
t.insert(1) 
t.insert(7) 
t.insert(3) 
t.insert(6) 
t.insert(2) 
t.insert(5) 
t.inorder() 
print(t.height()) 

Answer 1

你需要改變你的init方法是這樣的：

def __init__(self,val): 
    self.left = None 
    self.right = None 
    self.root = val 
    self.rheight = 0 
    self.lheight = 0 

而且你的身高的方法是這樣的：

def height(self): 
    if self.root == None: 
     return 0 
    else: 
     if hasattr(self.left, 'height'): 
      self.lheight = self.left.height() 
     if hasattr(self.right, 'height'): 
      self.rheight = self.right.height() 
     return 1 + max(self.lheight, self.rheight) 

這需要改變的原因是，你一直在樹下調用高度，因此一直到樹的底部一直到左右兩側None。那麼這是做什麼檢查是否self.right和self.left有高度的屬性。如果類型爲None，那麼它們不會，所以當兩者都是None時，我們會一路返回。

Answer 2

當你在某個時候到達這條線

return 1 + max(self.left.height(), self.right.height()) 

然後，self.left變得沒有定義（雖然不是在一開始）。您可以通過在該語句前添加print(self.left)來檢查該錯誤，並且您會在錯誤消息之前輸出None。

這意味着，雖然定義了self.root，但您的基本情況需要包括self.left（可能還有self.right），因此在任何時候都不會有這些無。

Answer 3

替換此行：

return 1 + max(self.left.height(), self.right.height()) 

與

if hasattr(self.left, 'height'): 
    left_height = self.left.height() 
if hasattr(self.right, 'height'): 
    right_height = self.right.height() 
return 1 + max(left_height, right_height)