从列表清单构建树

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