使用栈解析字符串为树

1 投票

3 回答

3715 浏览

提问于 2025-04-17 15:23

为了让大家都明白，这个曾经是作业，但作业已经到期了。

我们可以这样定义一个简单的树：

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, []), Tree(3, [Tree(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 += "]),"

数据结构递归编程问题树结构字符串解析算法树遍历栈

3 个回答

假设我们知道以下两件事：

如果你从输入字符串中读取到 NIL，那就意味着你读取到了一个空树。
如果你读取到一个数字，那么你就有了一棵非空的树，树的根节点包含这个数字，并且你还需要从输入字符串中读取两个树（一个是左子树，一个是右子树）。

现在我们准备开始读取这棵树了 :）。假设有一个类似 C 语言的结构（我会让你自己在 Python 中做这个练习，Python 写起来会更简洁）：

struct tree {
   int value;
   tree *left;
   tree *right;
}

还有一些简单的解释，基本上是一个方法，它接受一个字符指针（char*），返回第一个标记，并且把输入字符串指向下一个标记）在输入流中可以这样做：

tree *readTree(char *&inputString) {
   char *token = read_next_token(inputString); 
   if (strcmp(token, "NIL") {
      // empty tree .. we return
      return NULL;
   }

   struct tree* node = malloc(sizeof(struct tree));
   node->value = token_as_int(token);

   // note that after the readTree is called the inputString will be modified
   // that's why i defined it to take a reference to a pointer of chars.
   node->left = readTree(inputString);
   node->right = readTree(inputString);
   return node; 
}

而 read_next_token 的定义是：

char *read_next_token(char*&inputString) {
  char *token = inputString;

  while ( *inputString != ' ' )
    inputString++;

  *inputString = 0; // make the token a null terminated string.

  while ( *inputString == ' ' ) inputString++;

  return token;
}

回答于 2025-04-17 由 Python大师

分享举报

也许可以这样做：

#! /usr/bin/python3.2

class Tree:
    def __init__ (self, value):
        self.value = value
        self.parent = None
        self.children = []

    def __iadd__ (self, child):
        child.parent = self
        self.children.append (child)
        return self

    def fromString (string):
        return Tree.fromList (string.split () ) [0]

    def fromList (list):
        node = Tree (list [0] )
        list = list [1:]
        while list [0] != 'NIL':
            child, list = Tree.fromList (list)
            node += child
        return node, list [1:]

    def __repr__ (self):
        return '{}{}'.format (self.value, ': {}'.format (self.children) if self.children else '')

t = Tree.fromString ('1 2 5 NIL 3 4 NIL NIL NIL NIL')
print (t)

t = Tree.fromString ('1 2 NIL 3 4 NIL 5 NIL 6 NIL NIL 7 NIL NIL')
print (t)

回答于 2025-04-17 由 Python大师

分享举报

在你的例子中，对于这个输入：

1 2 5 NIL 3 4 NIL NIL NIL NIL

你说这个应该是结果（注意我只是把你的版本格式化了一下，方便理解）：

Tree(1, [
    Tree(2, [
        Tree(5, []),
        Tree(3, [
            Tree(4)
        ])
    ])
])

看起来像这样：

从这个（还有nneonneo的有用评论）我们可以弄明白这些树是如何从字符串构建的。它的工作方式大概是这样的：

从一个理论上的根节点开始，认为它是“当前”节点。
对于每一个非空值，把它作为当前节点的子节点，并把它标记为新的当前节点。也就是说，向下走。
对于每一个空值，把当前节点的父节点标记为新的当前节点。也就是说，向上走。
当再次到达理论上的根节点时，我们就完成了（字符串应该被完全处理完）。

注意，为了回到根节点的尾部空值如果想节省空间可以省略。不过，包含它们可以在最后进行合理性检查。

根据我上面给出的思路，可以用迭代的方式来实现，而不需要递归。有些人可能更喜欢递归的解决方案，但无论哪种方式都同样有效，所以后者就留给你自己去练习了！

回答于 2025-04-17 由 Python大师

分享举报

使用栈解析字符串为树

3 个回答

撰写回答