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

Question

我正在尝试编写一个函数，通过合并我的 BinaryTree class:

来计算二叉树的叶子数

这是我的二叉树class:

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

输出：

而不是 2。

我这个函数的思路是一直循环，直到找到左右子树为None的节点，然后加一计数。这样它就找到了每一片叶子。

我做错了什么？

Answer 1

你误解了递归调用的独立性。 num_leaves 不能 return 除 0 或 1（如您所写）之外的任何值。 num_leaves 的每个实例都有其自己的 count 的本地副本。不要尝试将此作为运行总和，而是让 num_leaves return 位于或低于该点的叶子数。

此外，您在 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())

Answer 2

乍一看，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

我将 post 对您的 Tree 代码进行更多改进。你实现它的方式你的 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 3

我建议将所有与 btree 相关的函数保留在 class 中。这就是 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

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

Python: Recursion: Find number of leaves of binary tree

python

recursion

binary-tree