gpt4 book ai didi

python - BST广度优先遍历(包括已删除节点)

转载 作者:太空宇宙 更新时间:2023-11-03 21:10:48 24 4
gpt4 key购买 nike

给定这棵树:

         7
5 9
_ 6 8 _
_ _ _ _

我希望输出是:

[[Node(7)], [Node(5), Node(9)], [None, Node(6), Node(8), None], [None, None, None, None]]

因此,包含“无”并且输出在列表中列出非常重要。

我尝试了很多事情,但这就是我现在的处境:

class Node(object):
def __init__(self, key, value=None):
self.key = key
self.value = value
self.parent = None
self.left_child = None
self.right_child = None
self.height = 0

def breadth_first_traversal(self):
self.height = 1
to_do = [self.root]
if (self.root == None):
return to_do
output = []
current_height = self.height
output.append([str(node) for node in to_do])

while (to_do):
done = []
current = to_do.pop(0)
if (current.height > current_height):
current_height += 1
if (current.left_child):
current.left_child.height = current_height + 1
to_do.append(current.left_child)
done.append(current.left_child)
elif (not current.left_child):
done.append(None)
if (current.right_child):
current.right_child.height = current_height + 1
to_do.append(current.right_child)
done.append(current.right_child)
elif (not current.right_child):
done.append(None)
output.append([str(node) for node in done])

print(output)
return output

现在的输出是:

[['7'], ['5', '9'], ['None', '6'], ['8', 'None'], ['None', 'None'], ['None', 'None']]

我理解为什么它要创建包含 2 个元素的列表,因为这就是我所说的它现在应该做的事情。我只是不知道如何考虑级别。

最佳答案

一种可能是找到所有节点,包括存储 None 的叶子,以及每个节点的深度,然后按深度分组:

为了简单起见,我创建了一个可以使用 kwargs 轻松初始化的二叉树,以及遍历树并提供运行深度值的方法:

from itertools import groupby

class Node:
def __init__(self, **kwargs):
self.__dict__ = {i:kwargs.get(i, None) for i in ['left', 'right', 'value']}
def get_depths(self, _count = 0):
yield [_count, self.value]
if self.left is not None:
yield from self.left.get_depths(_count+1)
else:
yield [_count+1, None]
if self.right is not None:
yield from self.right.get_depths(_count+1)
else:
yield [_count+1, None]

tree = Node(value=7, left=Node(value=5, right=Node(value=6)), right=Node(value=9, left=Node(value=8)))
flattened = [[c for _, c in b] for _, b in groupby(sorted(list(tree.get_depths()), key=lambda x:x[0]), key=lambda x:x[0])]

输出:

[[7], [5, 9], [None, 6, 8, None], [None, None, None, None]]

关于python - BST广度优先遍历(包括已删除节点),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/55078705/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com