[python] Trideni stromu.

[Radek Kaňovský]

On Fri, Oct 14, 2005 at 02:39:55PM +0200, David Michal wrote:

> >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
> > 
> >
> To neni uplne ono, tohle dava vysledek: [(0, None), (1, 0), (2, 0), (3, 
> 1), (5, 2), (4, 2), (7, 3)]
> ale ja bych potreboval [(0,None), (1,0), (3,1), (7,3), (2,0), (5,2), (4,2)]

    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)

    def dfs(branches, node):
        yield node
        for child in branches.get(node[0],()):
            for n in dfs(branches, child):
                yield n

    print list(dfs(branches, (root,None)))

Radek Kaňovský