[python] Trideni stromu.

[Radek Kaňovský]

On Fri, Oct 14, 2005 at 01:46:15PM +0200, David Michal wrote:

> >ale metoda sort() je rekurzivni. K tomu reseni - melo by stacit si 
> >uvedomit, jake jsou vztahy mezi jednotlivymi polozkami toho listu a podle 
> >toho je mezi sebou srovnat.
> >
> Tady trosku plavu, vztah mezi polozkami je ten ze pokud a[n][-1] == 
> a[posledni_rodic][0] tak a[n] je potomkem posledniho rodice. Jak bych 
> mohl podstrcit metode sort() vlastni fci, ktera by umela toto porovnat?

sort() nepomuze, protoze napriklad o prvcich (323,5),(1024,49) nelze z
hlediska porovnani nic rict bez dalsiho kontextu. Jestli spravne chapu
zadani, tak se vlastne jedna o prochazeni stromu do sirky. Zkuste tohle:

    root = 0
    tree = [(1,0), (5,2), (7,3), (2,0), (3,1), (4,2)]

    branches = {}
    for item in tree:
        branches.setdefault(item[1],[]).append(item)

    bfs = [(root,None)]
    i = 0
    while branches:
        node = bfs[i]
        bfs.extend(branches.pop(node[0], []))
        i += 1
    print bfs

Radek Kaňovský