Cetus Group - Разработка программного обеспечения

Хитрые вещи в Python

Редакция 11.07.2006

А.Г. © Часть 1 - "Преобразование таблицы в дерево"

При решении некоторых задач может потребоваться преобразование табличных данных в дерево. Например, простым решением при заполнении ListView данными из курсора базы данных было бы формирование отдельного SQL-запроса для заполнения каждого узла ListView, что создает дополнительную нагрузку на СУБД. Представленная ниже программа формирует данные для ListView по результатам одного запроса к БД. С целью упрощения примера исходные данные сразу представлены в виде таблицы.

#!/usr/bin/python
# -*- coding: utf-8 -*-

from string import *

# входная таблица фирм, отделов и продавцов
src = [
	['Alfa','Products','Vasya'],
	['Alfa','Products','Petya'],
	['Alfa','Drinks','Misha'],
	['Alfa','Juices','Fedya'],
	['Beta','Products','Kolya'],
	['Beta','Bread','Masha'],
	['Alfa','Drinks','Tolya']
]

# выходное дерево
trg = []

# извлекаем строку входной таблицы
for inp in src:
# назначаем вывод на "ствол" дерева
	out = trg
# проходим по извлеченной строке
	for j in range(len(src[0])):
		fin = 0
		for o in range(len(out)):
# если назначение найдено
			if inp[j]==out[o]:
#   - продвигаем точку назначения для вывода  
				out = out[o+1]
				fin = 1
				break
# добавляем элемент в дерево
		if fin == 0:
			out.append(inp[j])
			if j != len(src[0])-1:
				out.append([])
#   и переходим на следующий уровень вложения
			out = out[-1]
print trg

В результате выполнения этой программы получены следующие результаты:
['Alfa', ['Products', ['Vasya', 'Petya'], 'Drinks', ['Misha', 'Tolya'], 'Juices', ['Fedya']], 'Beta', ['Products', ['Kolya'], 'Bread', ['Masha']]]
что соответствует:

+-['Alfa',
|     +-------['Products',
|     |           +-------['Vasya', 
|     |           +-------'Petya'], 
|     +-------'Drinks',
|     |           +-------['Misha', 
|     |           +-------'Tolya'], 
|     +-------'Juices',
|                 +-------['Fedya']], 
+-'Beta',
      +-------['Products',
      |           +-------['Kolya'], 
      +-------'Bread',
                  +-------['Masha']]]

Не менее эффектно эта задача может быть решена и с применением словаря.