mishadoffs tanker

public class BinaryNode<T> { public T data; public BinaryNode<T> left; public BinaryNode<T> right;}

left_child(i) = 2 * i + 1right_child(i) = 2 * i + 2parent(i) = (i - 1) / 2

public int bfs(Predicate<T> predicate) { for (int i = 0; i < array.length; i++) { if (array != null && predicate.test(array)) return i; } return -1; // not found}

Depth-first search er lidt vanskeligere.

Ved brug af stakdatastruktur kan det implementeres på samme måde som for klassisk binært træ,bare sæt indekser ind i stakken.

Fra dette punkt er rekursion slet ikke anderledes,du bruger bare implicit metodeopkaldsstakken i stedet for datastrukturstakken.

Hvad nu hvis vi kunne implementere DFS uden stak og rekursion.I sidste ende er det bare et valg af korrekt indeks på hvert trin?

Nå, lad os prøve.

DFS for Binary Tree Array (uden stak og rekursion)

Som i BFS starter vi fra rodindekset 0.
Derpå skal vi inspicere dens venstre barn, hvis indeks kan beregnes ved formel 2*i+1.
Lad os kalde processen med at gå til næste venstre barn fordobling.

Vi fortsætter med at fordoble indekset, indtil vi ikke stopper ved bladknuden.

Så hvordan kan vi forstå, at det er en bladknude?

Hvis næste venstre barn producerer index out of array bounds exceptionskal vi stoppe fordoblingen og hoppe til det højre barn.

Det er en gyldig løsning, men vi kan undgå unødvendig fordobling.Observationen her er, at antallet af elementer i træet med nogle height er to gange større (og plus en)end træet med height - 1.

For træet med height = 2 har vi 7 elementer, for træet med height = 3 har vi 7*2+1 = 15 elementer.

Med denne observation bygger vi en simpel betingelse

i < array.length / 2

Du kan tjekke, at denne betingelse er gyldig for enhver ikke-bladet knude i træet.

Nice so far. Vi kan køre fordobling, og vi ved endda, hvornår vi skal stoppe. men på denne måde kan vi kun kontrollere venstre børn af knuderne.

Når vi sidder fast ved bladknuden og ikke kan anvende fordobling længere, udfører vi springoperation.Dybest set, hvis fordobling er at gå til venstre barn, er spring at gå til forælder og gå til højre barn.

Sådan springoperation kan gennemføres ved blot at øge bladindekset.Men når vi sidder fast i den næste bladknude, flytter en forøgelse ikke knuden til den næste knude, hvilket er nødvendigt for DFS.Så vi er nødt til at lave et dobbelthop

For at gøre det mere generisk kunne vi for vores algoritme definere operationen hop N, som angiver, hvor mange hop til forældrene det kræver, og som altid afsluttes med et hop til det rigtige barn.

For træet med højde 1 har vi brug for ét hop, hop 1

For træet med højde 2 har vi brug for ét hop, ét dobbelthop, og så ét hop igen

For træet med højde 3 kan man anvende de samme regler og få 7 hop.

Ser du mønsteret?

Hvis du anvender den samme regel på træet med højde 4 og kun skriver springværdierne ned, får du næste sekvensnummer

1 2 1 3 1 2 1 4 1 2 1 3 1 2 1

Denne sekvens er kendt som Zimin-ord, og den har rekursiv definiton,hvilket ikke er godt, fordi vi ikke må bruge rekursion.

Lad os finde en anden måde at beregne det på.

Hvis man ser nøje på springsekvensen, kan man se et ikke-rekursivt mønster.

Vi kan spore indeks for det aktuelle blad j, som svarer til indekset i sekvensmatrixen ovenfor.

For at verificere udsagn som “Hvert 8. element starter fra 3” kontrollerer vi blot j % 8 == 3,hvis det er sandt, springer tre spring til den nødvendige overliggende knude.

Iterativ springproces vil være følgende

• Start med k = 1
• Spring én gang til den overordnede ved at anvende i = (i - 1)/2
• Hvis leaf % 2*k == k - 1 alle spring er udført, afsluttes
• I modsat fald skal k sættes til 2*k og gentages.

Hvis du sætter alt sammen, hvad vi har diskuteret

public int dfs(Predicate<T> predicate) { int i = 0; int leaf = 0; while (i < array.length) { if (array != null && predicate.test(array)) return i; // node found if (i < array.length / 2) { // not leaf node, can be advanced i = 2 * i + 1; // try left child } else { // leaf node, jump int k = 1; while (true) { i = (i - 1) / 2; // jump to the parent int p = k * 2; if (leaf % p == k - 1) break; // correct number of jumps found k = p; } // after we jumped to the parent, go to the right child i = 2 * i + 2; leaf++; // next leaf, please } } return -1;}