为了充分披露,这是硬件,但分配已经到期。
如果我们定义一个简单的树如下:
class Tree (object):
__slots__ = "node","children"
def __init__(self,node,children=[]):
self.node = node
self.children = children
我们如何从字符串构建一棵树?在字符串模型中,“NIL”表示树的结束。因此,字符串 1 2 5 NIL 3 4 NIL NIL NIL NIL
将返回一棵类似于 t = Tree(1, [Tree(2, [Tree(5, [])),树(3,[树(4)])])])
。该解决方案可以使用递归和/或堆栈。我以为我理解了堆栈和递归,但我无法弄清楚这个问题。有什么想法吗?
编辑
要添加更多信息,我们可以打印树,如下所示:
def __str__(self):
return "(%s)" % " ".join(map(str,[self.node]+self.children))
我无法接近创建一棵树并打印它。我所能想到的就是创建一个看起来像创建树的字符串的字符串。我有:
def delinearize(self, linear_string):
@staticmethod
tree_data = linear_string.split()
tree_str = ""
if tree_data[0] == "NIL":
print "Tree needs initial root node"
return
for entry in tree_data:
if entry != "NIL":
tree_str += "Tree("+entry+", ["
elif entry == "NIL":
tree_str += "]),"
最佳答案
在您的示例中,对于此输入:
1 2 5 NIL 3 4 NIL NIL NIL NIL
你说这应该是结果(注意我只是格式化你的版本以便于理解):
Tree(1, [
Tree(2, [
Tree(5, []),
Tree(3, [
Tree(4)
])
])
])
这“看起来像”:
1
|
2
/ \
5 3
|
4
从此(以及 nneonneo 的有用评论)我们可以确定这些树是如何从字符串构建的。它似乎是这样工作的:
- 从理论上的根节点开始,被视为“当前”节点。
- 对于每个非 NIL 值,将其添加为当前节点的子节点,并将其标记为新的当前节点。即下降。
- 对于每个 NIL 值,将当前节点的父节点标记为新的当前节点。即上升。
- 当再次到达理论上的根节点时,我们就完成了(并且字符串应该被完全消耗)。
请注意,如果您想节省空间,可以省略返回根的尾随 NIL。另一方面,包括它们支持最后的健全性检查。
根据我上面给出的概述,它可以以迭代方式实现,无需递归。有些人更喜欢递归解决方案,但无论哪种方式都同样强大,因此后者留作练习!
关于python - 使用堆栈将字符串解析为树,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/14793972/