Python二進制樹打印節點與兩個恰好兩個孩子

Question

如何製作一個函數，返回有兩個孩子的樹中的節點數量？

我的類代碼如下：

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

    def insert_left(self, value): 
     self.left = RefBinaryTree(value, left=self.left) 

    def insert_right(self, value): 
     self.right = RefBinaryTree(value, right=self.right) 

    def get_left_subtree(self): 
     return self.left 

    def get_right_subtree(self): 
     return self.right 

    def set_value(self, new_value): 
     self.key = new_value 

    def get_value(self): 
     return self.key 

    def create_string(self, indent): 
     string = str(self.key) + '---+' 
     if self.left: 
      string += '\n(l)' + indent + self.left.create_string(indent + ' ') 
     if self.right: 
      string += '\n(r)' + indent + self.right.create_string(indent + ' ') 
     return string 

    def __str__(self): 
     return self.create_string(' ') 

我猜這將是最好使用遞歸。任何提示或有用的鏈接都會很棒。謝謝。

Answer 1

遞歸計算兩個子節點真的很簡單。如果你返回一個數字，每個函數調用（零爲基數的情況下），你可以簡單地添加1每次找到兩個子節點：

def findDoubleNodes(tree): 
    if tree == None or (tree.left == None and tree.right == None): 
     # base case 
     return 0 
    elif tree.left <> None and tree.right <> None: 
     # both have children, so add one to our total and go down one level 
     return findDoubleNodes(tree.left)+findDoubleNodes(tree.right) + 1 
    else: 
     # only one child, so only go down one level 
     return findDoubleNodes(tree.left)+findDoubleNodes(tree.right) 

輸入一個RefBinaryTree返回節點的數量，有兩個孩子。舉個例子：

x = RefBinaryTree(1) 
x.insert_left(5) 
x.left.insert_left(6) 
x.left.insert_right(7) 
x.left.right.insert_left(8) 
x.left.right.insert_right(9) 
x.left.right.right.insert_right(10) 

的（懶洋洋）創建樹是這個樣子：

1 
/
    5 
/\ 
6 7 
/\ 
    8 9 
     \ 
     10 

而且findDoubleNodes(x)回報2，因爲只有兩個節點（5,7），有兩個孩子。

此外，向節點9（x.left.right.right.insert_left(11)）添加左側子項具有預期結果，返回3。

Answer 2

這應該這樣做：

def countNodes(tree): 
    if tree is None: 
     return 0 
    left = tree.get_left_subtree() 
    rght = tree.get_right_subtree() 
    return (0 if left is None or rght is None else 1) \ 
      + countNodes(left) + countNodes(rght)