Poszukiwane: Nawrót Formuła In-Order drzewa binarnego sposobu wyjścia

Question

jestem w trochę zacięcia szukasz wzoru nawrotom tej metody java

void printInorder(Node<T> v) { 
    if(v != null) { 
     printInorder(v.getLeft()); 
     System.out.println(v.getData()); 
     printInorder(v.getRight()); 
    } 
} 

Niektóre kryteria:

• jego kompletnym drzewo binarne (co wewnętrzny węzeł ma 2 dzieci, każdy listek ma taką samą głębokość)
• drzewa ma N węzłów i złożoność o (n)

Muszę znaleźć wzór powtarzania w odniesieniu do depth h drzewa z n knots, a jako dodatkowy bonus, muszę ekstrapolować jawną formułę prowadzącą do O (n) z tego.

Teraz, to jest to, co mam:

d = depth of the tree 
c = constant runtime for execution of the method itself 
d = 1: T(n) = c 
d = 3: T(n) = T(d=1) + T(d=2) + T(d=3) + c 

użyłem przykładu D = 3 do wyjaśnienia rzeczy dla siebie, mam trudności w dół łamiąc tym dalej. Czy moje założenie jest poprawne?

---

Edit: Następna próba rzeczy

[x] = { x in real numbers : max([x]) <= x }, [x] rounded down to next full number 
d = 1: T(d) = 1 
d > 1: T(d) = 2^(h-1) * T(n/(2^(h-1))) 

1: T(h) = T(i = 0) + T(i = 1) + ... T(i = h-1) 
2: T(h) <= (2^(0-1) + n/(2^(0-1))) + (2^(1-1) + n/(2^(1-1))) + ... + (2^(h-2) + n/(2^(h-2))) 
3: T(h) = n + n + ... + n 
4: T(h) = (h-1)n 
5: T(h) = O(n) 

Ponieważ każdy poziom głębokości drzewa zawiera dokładnie 2^(h-1) węzłów, współczynnik h w wierszu 4 mogą być ignorowane, ponieważ n ma większe znaczenie dla końcowego wyniku.

Answer 1

T (n) = T (n/2) + T (n/2) + 1

• poziom 0 zawiera 1 operacji.

• Poziom 1 ma 2 operacje.

• Poziom 2 ma 4 operacje.

• Poziom k ma 2^k operacji.

• Głębokość drzewa to lgn.

1 + 2 + ... + 2^LGN =
2^0 + 2^1 + 2^2 + ... + 2^LGN =
(2^(LGN + 1) -1)/(2-1) = 2 * 2^lgn =
2n.

Answer 2

Poniżej przedstawiono alternatywne podejście z wykorzystaniem reguły Gładkość (levitin, Design & Analiza algorytmów, wyd. 2, 481-82), co pozwala na związek nawrotom takim jak ten jest reprezentowany jako zamiast wykładnikiem.

czy podejście - do przodu i do tyłu podstawienia - są odpowiednie do tego problemu. Znalezienie wstecznej substytucji jest w wielu przypadkach łatwiejsze do strawienia.