的Python：遞歸：查找二叉樹的葉子

Question

我想寫，通過將我的二叉樹類計算二叉樹的葉數的函數的數量：

這是我的二叉樹類：

class BinaryTree: 

def __init__(self, data): 
    self.data = data 
    self.left = None 
    self.right = None 

def insert_left(self, new_data): 
    if self.left == None: 
     self.left = BinaryTree(new_data) 
    else: 
     t = BinaryTree(new_data) 
     t.left = self.left 
     self.left = t 

def insert_right(self, new_data): 
    if self.right == None: 
     self.right = BinaryTree(new_data) 
    else: 
     t = BinaryTree(new_data) 
     t.right = self.right 
     self.right = t 

def get_left(self): 
    return self.left 

def get_right(self): 
    return self.right 

def set_data(self, data): 
    self.data = data 

def get_data(self): 
    return self.data 

而這個函數我寫道：此刻它不輸出正確的值。我覺得有什麼錯我的遞歸，但我無法弄清楚：

def num_leaves(my_tree): 
    count = 0 
    if my_tree.get_left() and my_tree.get_right() is None: 
     count += 1 
    if my_tree.get_left(): 
     num_leaves(my_tree.get_left()) 
    if my_tree.get_right(): 
     num_leaves(my_tree.get_right()) 

    return count 

輸入和輸出的一個例子是：

a = BinaryTree(1) 
a.insert_left(2) 
a.insert_right(3) 
print(num_leaves(a)) 

輸出：

0 

代替2.

我的功能背後的想法是，它重複出現，直到它找到一個節點，其中的左和右s ubtree是None，那麼它會添加一個數字。這樣它找到每一片葉子。

我在做什麼錯？

Answer 1

乍一看你對num_leaves代碼應該是這樣的：

def num_leaves(my_tree): 
    count = 0 
    if my_tree.get_left() is None and my_tree.get_right() is None: 
     count += 1 
    if my_tree.get_left(): 
     count += num_leaves(my_tree.get_left()) # added count += 
    if my_tree.get_right(): 
     count += num_leaves(my_tree.get_right()) # added count += 

    return count 

我會發布到你的樹代碼一些更多的改進。 你已經實現它的方式你的BinaryTree只是一個二叉樹而不是二叉搜索樹。所以我猜如果你對上面的代碼提出了簡單的改變，它應該可以正常工作。

測試：

這給3，符合市場預期：

a = BinaryTree(1) 
a.insert_left(2) 
a.insert_right(3) 
a.insert_right(4) 
a.get_right().insert_left(5) 
print(num_leaves(a)) 

這給2，符合市場預期：

a = BinaryTree(1) 
a.insert_left(2) 
a.insert_right(3) 
print(num_leaves(a)) 

這給2，符合市場預期：

a = BinaryTree(1) 
a.insert_left(2) 
a.insert_right(3) 
a.get_right().insert_left(5) 
print(num_leaves(a)) 

Answer 2

您誤解了遞歸調用的獨立性。 num_leaves無法返回除0或1之外的任何內容（如您所寫）。 num_leaves的每個實例都有其自己的本地副本count。而不是試圖將其作爲運行總和來執行此操作，請使用num_leaves返回此點處或之下的葉數。

此外，您已經在num_leaves的第一個if語句中誤用了布爾表達式。您沒有明確檢查左樹是否爲無。儘管你寫的東西碰巧是以同樣的方式工作的，但是在我看來，你並沒有意識到自己在做什麼。

def num_leaves(my_tree): 
    if my_tree is None: 
     return 0 
    else: 
     return num_leaves(my_tree.get_left()) + 
       num_leaves(my_tree.get_right()) 

Answer 3

我會推薦kee p在班級中所有與btree相關的功能。這是OOP。

class BinaryTree: 
    ... your code ... 

    def is_leaf(self): 
     return self.right is None and self.left is None 

    def count_leaves(self): 
     if self.is_leaf(): 
      return 1 
     count = 0 
     if self.right is not None: 
      count += self.right.count_leaves() 
     if self.left is not None: 
      count += self.left.count_leaves() 
     return count