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返回有两个子节点的节点数。例如：

^{pr2}$

（懒洋洋地）创建的树如下所示：

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

而findDoubleNodes(x)返回{}，因为只有两个节点（5和7）有两个子节点。在

另外，向节点9（x.left.right.right.insert_left(11)）添加一个左子节点可以得到预期的结果，返回3。在