class BTNode(object):
"""A node in a binary tree."""
def __init__(self, item, left=None, right=None):
"""(BTNode, object, BTNode, BTNode) -> NoneType
Initialize this node to store item and have children left and right,
as well as depth 0.
"""
self.item = item
self.left = left
self.right = right
self.depth = 0 # the depth of this node in a tree
def __str__(self):
"""(BTNode) -> str
Return a "sideways" representation of the subtree rooted at this node,
with right subtrees above parents above left subtrees and each node on
its own line, preceded by as many TAB characters as the node's depth.
"""
# If there is a right subtree, add an extra TAB character in front of
# every node in its string representation, with an extra newline at the
# end (ready to be concatenated with self.item).
if self.right:
str_right = "\t" + str(self.right).replace("\n", "\n\t") + "\n"
else:
str_right = ""
# The string representation of self.item: if item is a string, use
# repr(item) so that quotes are included and special characters are
# treated correctly -- just like in a list; else use str(item).
if isinstance(self.item, str):
str_item = repr(self.item)
else:
str_item = str(self.item)
# If there is a left subtree, add an extra TAB character in front of
# every node in its string representation, with an extra newline at the
# beginning (ready to be concatenated with self.item).
if self.left:
str_left = "\n\t" + str(self.left).replace("\n", "\n\t")
else:
str_left = ""
# Put the right subtree above the root above the left subtree.
return str_right + str_item + str_left
def leaves_and_internals(self):
"""(BTNode) -> ([object], [object])
Return a pair of lists: (list of all the items stored in the leaves of
the subtree rooted at this node, list of all the items stored in the
internal nodes of the subtree rooted at this node).
"""
#Leaf: Doesn't have children
#Internal Node: Has children
leaf = []
internal = []
if not self.left and not self.right:
leaf.append(self.item)
if self.left is not None:
internal.append(self.item)
if self.right is not None:
self.right.leaves_and_internals()
self.left.leaves_and_internals()
elif self.right is not None:
internal.append(self.item)
self.right.leaves_and_internals()
print(leaf, internal)
return leaf, internal
BTNode クラスは、編集できない場所で提供されるスターター コードです。私の責任は、指定されたドキュメント文字列に従って、leaves_and_intervals のコードを記述することです。現在の私の唯一の問題は、extend を使用してリストを再帰的に適切に結合する方法がわからないことです。
私のテストブロックは次のようになります:
if __name__ == "__main__":
root = BTNode(2, BTNode(4, BTNode(6, BTNode(8, None, None), None), None), None)
root.leaves_and_internals()
そして、私の出力は次のようになります。
[8] []
[] [6]
[] [4]
[] [2]
正しい出力は次のようになります (順序は重要ではありません)。
[8] [6, 4, 2]
再帰するたびにリーフと内部が空のリストにリセットされないように、extend を正しく使用するにはどうすればよいですか? 拡張用に 2 番目のリストのセットが必要なのはわかっていますが、それを実装する方法がわかりません。