從列表清單構建樹

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