提问者:小点点

从列表列表构建树


我有一个列表,如下所示:{{f, h,i},{b,e,f,g},{a,b,c,d}}

我需要用规则构建一棵树:

  • 对于每个列表,第一个元素是根。
  • 其余元素是子元素。

对于这个例子,树看起来:

             a
      b      c     d
   e  f   g
     h  i

你能帮我写一下这个的算法吗?

谢谢!


共1个答案

匿名用户

这是一个简单的递归过程。

>

  • 如果列表包含一个列表,首先递归处理该列表,然后用它的第一个元素(它的根)替换它。

    现在该列表仅包含字母(表示节点)。

    a.将第一个字母设为节点。

    b.对比第一个字母小的其他元素进行排序。将它们链接到一个向下向右的分支中,并使最大的一个成为第一个字母的左孩子。

    C。类似地,对比第一个字母大的其他元素进行排序。将它们链接到一个向下向右的分支中,并使最小的一个成为第一个字母的左孩子。

    在伪代码中:

    def make_into_tree(l):
        for e in l:
            if type(e) == list:
                e = make_into_tree(e)
    
        root = e[0]
    
        smaller = sorted(all letters smaller than e[0])
        for each s in smaller (except for first):
            make s a right child of its predecessor
        smaller_root = smaller[0]
        make smaller_root left child of root
    
        larger = sorted(all letter larger than e[0])
        for each l in larger (except for first):
            make l a right child of its predecessor
        larger_root = smaller[0]
        make larger_root right child of root
    
        return root