尝试从树中按顺序打印字符串时遇到问题

Question

我想将一棵树变成一个字符串并获取 prestr 顺序（从根开始，然后沿着所有左侧节点向下移动，然后向右移动）示例：tree (root (left (a) (b)) (右 (c) (d))) 将是 "root left a b right c d".

class TreeNode:
def __init__(self, data = None):
    self.data = data
    self.children = []

class Tree:
def __init__(self, string = None):
    self.root = None

def prestr(self):
    string1 = ""
    value = self.root
    string1 += value.data
    string1 += " "
    while len(value.children) > 0:
        for i in value.children:
            string1 += i.data
            string1 += " "
            value = i
    print(string1)

当运行将此代码与

结合使用时

tree (root (left (a) (b)) (right (c) (d)))

我得到："root left right c d"。我怀疑这是因为它没有运行 for i in value.children on value.children[0] 当它被设置为值时但我不知道为什么。这里有什么问题？

Answer 1

您的代码存在问题，因为您在 for 循环中设置了 value = i。当您执行此操作时，您希望您的代码返回到 while ...: 但它不会，而是转到 for 循环的下一次迭代。这样做的结果是，在实际继续该值之前，您将值设置为 for 循环中节点的最后一个子节点。这将跳过每个节点的最后一个子节点以外的所有节点，这就是为什么您看到了您的行为。为了在正确的同时尽可能接近您的原始解决方案，我建议您对此代码使用递归，因为在这种情况下更容易推理：

def prestr_helper(value): if len(value.children) > 0: return value.data + ' ' + \ ' '.join(prestr_helper(child) for child in value.children) else: return value.data def prestr(self): print(prestr_helper(self.root))

然而，这确实存在 Python 的递归限制问题，因此在深度为 1000 或更多（大约）的树时会失败。为了规避此限制，您必须实施迭代解决方案，例如 here.
中描述的解决方案

尝试从树中按顺序打印字符串时遇到问题

Trouble trying to print string in order from a tree

python

tree

python-3.x