Python：递归：查找二叉树的叶子节点数量

Question

我将尝试编写一个函数，通过结合我的BinaryTree类来计算二叉树的叶子节点数：

这是我的BinaryTree类：

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。

我的函数背后的想法是，它会递归直到找到左子树和右子树均为None的节点，然后将1添加到计数器中。这样它就可以找到每个叶子节点。

我做错了什么？

- Newbie

---

你需要学习如何使用调试器。通过使用它，你可以逐步执行 num_leaves() 函数的代码，并检查 count 的值，以找出它与你期望的值不同的地方。这样做，你的问题就变得非常容易解决了。 - Ulrich Eckhardt

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

我会翻译成中文：

我将为您的树代码发布一些更多的改进。按照您的实现方式，您的二叉树只是一个二叉树而不是二叉搜索树。所以我想如果您对上面的代码进行我提出的简单更改，它应该可以正常工作。

测试：

这将得到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))

- Ankur Agarwal

Answer 2

你误解了递归调用的独立性。如你所写，num_leaves 除了返回0或1之外，不能返回任何其他值。每个 num_leaves 实例都有其自己的局部变量 count 的副本。不要试图将其作为运行总和来处理，而是让 num_leaves 返回此点及以下的叶子数。

另外，在 num_leaves 的第一个 if 语句中，你误用了布尔表达式。你没有明确检查左树是否为 None。虽然你所写的代码可能以相同的方式工作，但在我看来，你并没有意识到自己在做什么。

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())

- Prune

---

左子树和右子树中可能只有一个是存在的，另一个则为None。你的代码没有处理这种情况。 - VPfB

Answer 3

我建议将所有与B树相关的函数放在类内部。这是面向对象编程的做法。

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

- VPfB