Блог

У меня есть список списка, который выглядит следующим образом: {{f, h, i}, {b, e, f, g}, {a, b, c, d}}

Мне нужно построить дерево с правилом:

• для каждого списка первым элементом является корень.
• остальные элементы являются дочерними.

для этого примера дерево выглядит:

              a
      b      c     d
   e  f   g
     h  i
  

можете ли вы помочь мне написать алгоритм для этого.

Спасибо!

Это простая рекурсивная процедура.

1. Если список содержит список, сначала рекурсивно обработайте этот список, затем замените его первым элементом (его корнем).

2. Теперь список содержит только буквы (представляющие узлы).

   a. Сделайте первую букву узлом.

   б. Отсортируйте другие элементы, меньшие, чем первая буква. Соедините их в нисходящую ветвь, обращенную вправо, и сделайте самую большую из них левым дочерним элементом первой буквы.

   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