我将尝试编写一个函数,通过结合我的BinaryTree类来计算二叉树的叶子节点数:
这是我的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添加到计数器中。这样它就可以找到每个叶子节点。
我做错了什么?
num_leaves()
函数的代码,并检查count
的值,以找出它与你期望的值不同的地方。这样做,你的问题就变得非常容易解决了。 - Ulrich Eckhardt