10. juni 2003 - 13:52Der er
9 kommentarer og 1 løsning
Søgning i struktur: rekursion
Jeg har fået placeret en masse ord (String) i et binært træ ved rekursivt at kalde en indsaet(nytOrd). Så langt så godt. Nu sidder jeg og skal finde (i samme træ) med en metode find(soegPaa), allt de ord i træet der begynder med soegPaa. Eksempel: rod -> midte, venstre node -> midt, højre node -> midten. Der skal metoden find("mid") give alle tre noder (muligvis også undernoder).
Jeg har lavet en metode, men den når ikke længere end til roden. Mangler jeg noget, eller kan det slet ikke lade sig gøre med et binært træ?
find-alle(node, start-af-ord, liste) { if match list.add(ord) if lchild find-alle(lchild, start-af-ord, liste) if rchild find-alle(rchild, start-af-ord, liste) }
find-alle(rod)
men det er jo reelt en sekventiel scan, hvilket næppe var hensigten med et binært træ.
Jeg prøver, og hvis jeg kommer nærmere får du point. Det var i teorien meningen at søgningen skulle forløbe hurtigst muligt (altså ikke liste, men hvis alt andet fejler...)
find-alle(node, start-af-ord, liste) { if match list.add(ord) if lchild and start-af-ord < node find-alle(lchild, start-af-ord, liste) if rchild and start-af-ord + "ZZZ" > node find-alle(rchild, start-af-ord, liste) }
Jeg har sendt dig en mail med metoden som jeg har lavet den. Den virker kun halvt. Kan du se hvad jeg mangler at referere til?
Synes godt om
Ny brugerNybegynder
Din løsning...
Tilladte BB-code-tags: [b]fed[/b] [i]kursiv[/i] [u]understreget[/u] Web- og emailadresser omdannes automatisk til links. Der sættes "nofollow" på alle links.
