Создание списков из деревьев, сохраняющих структуру дерева

Question

Для приложения, которое я пишу, мне нужно проверить ветви дерева Хаффмана для определенного свойства. С этой целью я подумал о запросе узла и возвращении плоского списка, который содержит подсписки, представляющие элементы в каждой ветке.

Например, если у меня было это дерево:

-a 
|-b 
|-c 
|-d 

Я хотел бы создать список, запрашивая верхний элемент («а») и возвращает список:

[[a],[b,c,d]] 

Если переспросила я второй лист ('B') Я хочу, чтобы вернуться:

[[b].[c,d]] 

и т.д.

До сих пор я храню мое дерево, как кортеж, так как:

(1.0,(0.5,(0.25, (0.125,'d'),(0.125,'c')),(0.25,'b')),(0.5,'a')) 

У меня есть функция, которая печатает информацию о листьях:

def printTree(tree, prefix = ''): 
    if len(tree) == 2: 
     print tree[1], prefix 
    else: 
     printTree(tree[1], prefix + '0') 
     printTree(tree[2], prefix + '1') 

Я пытался создать функцию который заменяет операторы печати операторами list(), но это не сработало.

Есть ли у кого-нибудь идеи о том, как я могу это сделать?

Answer 1

Таким образом, вы ищете что-то вроде:

def printTree(tree, prefix = '', res=[]): 
    if len(tree) == 2: 
     res.append((tree[1], prefix)) 
     print tree[1], prefix 
    else: 
     printTree(tree[1], prefix + '0', res=res) 
     printTree(tree[2], prefix + '1', res=res) 
    return res 

res проведет свои результаты, а в рекурсии, и в конце концов он бы вернуться.

С вашим деревом это вернет: [('d', '000'), ('c', '001'), ('b', '01'), ('a', '1')] , это было то, что вы хотели?