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

这样做就可以了：

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)

Answer 2

其实，递归地计算有两个孩子的节点非常简单。如果每次函数调用都返回一个数字（基础情况是零），那么每当你找到一个有两个孩子的节点时，就可以简单地加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。