Finne dybden av et tre?

[Lily]

Jeg har et binært søketre som jeg skal finne største dybde og gjennomsnittlig dybde av, men hvordan i all verden gjør jeg det da??

[HolgerL]

Du kan traverse gjennom treet med algoritmer som depth first search (dfs) eller breadth first search (bfs). Mens du traverserer lagrer du dybden til alle nodene (er som regel allerede implementert i algoritmen til dfs og bfs), og når du kommer til en løvnode (node uten barn) lagrer du dybden dens i en tabell. Etter traverseringen finner du største dybden i tabellen og regner ut snittet.

 

Algoritmene for dfs og bfs finner du på nett. Sjekk om dybdelagring er implementert i algoritmen eller implementer den selv.

[blackbrrd]

fine søkeord i google er da f.eks: binary tree java