algorithm - 从列表的列表构建树

Question

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

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

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

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

             a
      b      c     d
   e  f   g
     h  i

你能帮我写一个算法吗？

谢谢!

Answer 1

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

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

2. 现在列表只包含字母(代表节点)。

   一个。将第一个字母作为节点。

   对小于第一个字母的其他元素进行排序。将它们链接成一个面向右下的分支，并使最大的一个成为第一个字母的左子节点。

   同样，对其他大于首字母的元素进行排序。将它们链接成一个面向右下的分支，并使最小的一个成为第一个字母的左子节点。

在伪代码中:

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