从列表的列表生成树

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. 现在，该列表仅包含字母(表示节点(。

   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