辞書型のテーブルをTree状に再形成させる

タイトル通りだけどなんのこっちゃかわからないかと。

以下のようなテーブルがあるとする。idという唯一の数値とparentという親idを持ったレコードがあるとする。それらは既に辞書型になってparentとidで降順ソートをしている状態にあるとする。

なおparentが0の時は、root要素とする。

id	parent	title
1	0	root
2	1	test2
3	1	test3
4	1	test4
6	1	test6
8	1	test7
5	2	test5
7	5	test7
9	6	test6

上の表をしたのaaのようにしたい。

`- 1:root
　　|`- 2:test2
　　|　　`- 5:test5
　　|　　　　`- 7:test7
　　|`- 3:test3
　　|`- 3:test3
　　|`- 4:test4
　　|`- 6:test6
　　|　　`- 9:test9
　　`- 8:test8

実行結果。ちょっと見やすいように整形済み

[yasui@negro: ~/python/tree][1:45] $ ./tree.py
[
	{'child': [
		{'child': [
			{'child': [
				{'child': [], 'id': 7, 'parent': 5, 'title': 'test7'}
			],'id': 5, 'parent': 2, 'title': 'test5'}
		], 'id': 2, 'parent': 1, 'title': 'test2'},
		{'child': [], 'id': 3, 'parent': 1, 'title': 'test3'},
		{'child': [], 'id': 4, 'parent': 1, 'title': 'test4'},
		{'child': [
			{'child': [], 'id': 9, 'parent': 6, 'title': 'test6'}
		], 'id': 6, 'parent': 1, 'title': 'test6'},
		{'child': [], 'id': 8, 'parent': 1, 'title': 'test7'}
	], 'id': 1, 'parent': 0, 'title': 'root'}
]

プログラムメイン*1

#!/usr/bin/python2.5
#
# -*- encoding: utf8 -*-
#

def makeTree (buffer):
	g = []
	for e in buffer:
		if e['parent'] > 0:
			def search (arr, item):
				for childrens in arr:
					if childrens['id'] == item['parent']:
						childrens['child'].append(item)
						return True
					
					if len(childrens['child']):
						if search(childrens['child'], item):
							return True
				return False
			
			if not search(g, e):
				g.append(e)
		else:
			g.append(e)
	
	return g


def main() :
	d = [dict(id=1, parent=0, title="root", child=[]),
			dict(id=2, parent=1, title="test2", child=[]),
			dict(id=3, parent=1, title="test3", child=[]),
			dict(id=4, parent=1, title="test4", child=[]),
			dict(id=6, parent=1, title="test6", child=[]),
			dict(id=8, parent=1, title="test7", child=[]),
			dict(id=5, parent=2, title="test5", child=[]),
			dict(id=7, parent=5, title="test7", child=[]),
			dict(id=9, parent=6, title="test6", child=[])];
	
	tree = makeTree(d)
	
	print tree

if __name__ == '__main__':
	main()

*1:タブ幅がぶっ飛んで見える……