Vraag Iteratief boomlopen


Het is al een tijdje geleden dat ik nam gegevensstructuren en algoritmen op school, dus ik was onlangs verrast door een suggestie dat recursie misschien niet zo is de weg (tm) om de boom te doorlopen. Om een ​​of andere reden is iteratief, wachtrijgebaseerd traversaal geen techniek die ik ooit heb gebruikt.

Wat zijn de voordelen van een iteratieve versus recursieve traversal? In welke situaties kan ik de ene in plaats van de andere gebruiken?


14
2018-04-16 01:24


oorsprong


antwoorden:


Als u eerst een zoekopdracht uitvoert, moet de natuurlijke implementatie bestaan ​​uit het in een wachtrij duwen van knooppunten, niet om recursie te gebruiken.

Als u een diepte-zoekopdracht uitvoert, is recursie de meest natuurlijke manier om de traversal te coderen. Tenzij uw compiler de recursie van de staart optimaliseert in iteratie, zal uw recursieve implementatie langzamer zijn dan een iteratief algoritme en zal deze sterven met een stack overflow op een boom die diep genoeg is.

Een snelle Python om het verschil te illustreren:

#A tree is a tuple of an int and a tree. 
t = (1, (2,(4, (6), (7, (9)) )), (3, (5, (8)) ))
def bfs(t):
    to_visit = [t]
    while len(to_visit) > 0:
        c = to_visit[0]
        if type(c) is int:
            print c
        else: 
            print c[0]
            to_visit.append(c[1])
            if len(c) > 2: to_visit.append(c[2])
        to_visit = to_visit[1:]

def dfs(t):
    if type(t) is int:
        print t
        return 
    print t[0]
    dfs(t[1])
    if len(t) > 2: dfs(t[2]) 

bfs(t)
dfs(t)

19
2018-04-16 01:30



Als u een vaste hoeveelheid geheugen voor de stapel hebt, zoals u vaak doet (dit is vooral een probleem in veel Java JVM-configuraties), werkt recursie mogelijk niet goed als u een diepe boom hebt (of als de recursiediepte hoog is in een willekeurige ander scenario); het veroorzaakt een overloop van de stapel. Een iteratieve benadering, het duwen van knooppunten om te bezoeken in een wachtrij (voor BFS-achtige traversal) of stack (voor DFS-achtige traversal) heeft op verschillende manieren betere geheugeneigenschappen, dus als dit van belang is, gebruik dan een iteratieve benadering.

Het voordeel van recursie is eenvoud / elegantie van expressie, niet prestatie. Onthouden dat is de sleutel tot het kiezen van de juiste aanpak voor een bepaald algoritme, probleemomvang en machine-architectuur.


8
2018-04-16 01:31



Het hangt ervan af of je de Depth-First of Breadth-First traversal wilt doen. Depth-first is het eenvoudigst te implementeren via recursie. Met Breadth-first moet je een rij knopen bijhouden om uit te breiden in de toekomst.


1
2018-04-16 01:31



Eigenlijk zou je de wachtrij moeten gebruiken voor de eerste zoekactie in de breedte en voor de diepte voor de eerste keer zoeken, en voer je algoritme uit vanuit een while-lus. Het maken van recursieve functie-aanroepen kan uw programma aanzienlijk slepen als u het eenvoudig doet tijdens het doorlopen en kan een stapeloverloop veroorzaken, maar tegenwoordig zou u dat doen Moet heel hard proberen om er een te zien.

Heb gewoon een hash aan de zijkant om al bezochte nodes bij te houden voor het geval dat niet het geval is een boom maar een goed verbonden grafiek.


1
2018-04-16 02:29



Ga met recursief, omdat je eigenlijk een stack overflow error kunt krijgen, en dit is tenslotte stackoverflow.com.


-1
2017-09-12 23:17