我想定义一个返回树节点值列表的函数。该列表按级别顺序排列(从上到下,从左到右)。
例如,从上面显示的树生成的列表将是:[2, 29, 4, 26, None, None, 2, None, None, None, None, None, None, 9, None , 结束].
这是二叉树的实现
class BinaryTree:
def __init__(self, data, left = None, right = None):
self.key = data
self.left = left
self.right = right
def insert(self, data):
node = self
while node is not None:
parent = node
if node.left is None:
parent.insert_left(data)
break
if node.right is None:
parent.insert_right(data)
break
node = node.left
def insert_left(self, data):
self.left = BinaryTree(data, left=self.left)
def insert_right(self, data):
self.right = BinaryTree(data, right=self.right)
def get_left_subtree(self):
return self.left
def set_left(self, tree):
self.left = tree
def set_right(self, tree):
self.right = tree
def get_right_subtree(self):
return self.right
def set_value(self, val):
self.key = val
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(' ')
最佳答案
对于层序遍历,迭代算法是最自然的,例如:
def create_list(tree, templist=[]):
"""
>>> tree = BinaryTree(2, BinaryTree(29, BinaryTree(26)), BinaryTree(4, None, BinaryTree(2, BinaryTree(9))))
>>> create_list(tree)
[2, 29, 4, 26, None, None, 2, None, None, None, None, None, None, 9, None]
"""
items = []
queue = [tree]
while queue:
copy = queue[:]
queue = []
for item in copy:
if item is None:
items.append(None)
queue.append(None)
queue.append(None)
else:
items.append(item.key)
queue.append(item.left)
queue.append(item.right)
if all((x is None for x in queue)):
break
return items
如果你真的真的真的想要递归实现:
def create_list_rec(tree, items=[], queue=[]):
"""
>>> tree = BinaryTree(2, BinaryTree(29, BinaryTree(26)), BinaryTree(4, None, BinaryTree(2, BinaryTree(9))))
>>> create_list_rec(tree)
[2, 29, 4, 26, None, None, 2, None, None, None, None, None, None, 9, None]
"""
if not items and not queue:
return create_list_rec(None, [], [tree])
copy = queue[:]
queue = []
for item in copy:
if item is None:
items.append(None)
queue.append(None)
queue.append(None)
else:
items.append(item.key)
queue.append(item.left)
queue.append(item.right)
if all((x is None for x in queue)):
return items
return create_list_rec(items, queue)
关于python-3.x - 来自 python 二叉树的 python 列表,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/37495634/