Wanted: Formula tái phát trong thứ tự cây nhị phân phương pháp sản lượng

Question

tôi đang ở trong một chút của một mứt tìm kiếm công thức tái phát của phương pháp này java

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

Một số tiêu chí:

• của nó một cây nhị phân hoàn chỉnh (mỗi nút bên trong có 2 con, mỗi lá có cùng độ sâu)
• cây có n nút và độ phức tạp của O (n)

Tôi phải tìm công thức lặp lại liên quan đến depth h của cây với n knots, và như là một tiền thưởng thêm, tôi cần phải ngoại suy công thức rõ ràng dẫn đến O (n) từ đó.

Bây giờ, đây là những gì tôi nhận:

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 

tôi đã sử dụng các ví dụ d = 3 để làm rõ mọi thứ cho bản thân mình, tôi đang gặp khó khăn phá vỡ này xuống thấp hơn nữa. Giả định của tôi có đúng không?

---

Edit: Tiếp nỗ lực điều

[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) 

Bởi vì mỗi mức độ sâu của cây chứa chính xác 2^(h-1) nút, các yếu tố h trong dòng 4 có thể được bỏ qua bởi vì n là phù hợp hơn cho kết quả cuối cùng.

Answer 1

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

• Cấp 0 có 1 hoạt động.

• Cấp 1 có 2 hoạt động.

• Cấp 2 có 4 hoạt động.

• Cấp k có hoạt động 2^k.

• Độ sâu của cây là 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

Dưới đây là một cách tiếp cận khác bằng cách sử dụng quy tắc Smoothness (Levitin, Design & Phân tích các thuật toán, 2nd Ed., 481-82), cho phép một mối quan hệ tái phát như thế này để được biểu diễn như một số mũ để thay thế.

Hoặc cách tiếp cận - về phía trước hoặc thay lạc hậu - là thích hợp cho vấn đề này. Tôi tìm thấy sự thay thế lạc hậu trong nhiều trường hợp để dễ tiêu hóa hơn.