jak zapisac to zadanie

[Keendr]

Udowodnij przez indukcję po h, że drzewo binarne o wysokości h ma nie więcej niż \(\displaystyle{ 2^h}\) liści.

Pewnie to proste tylko cos nie moge tego zapisac


[edit]

dalej nie wiem jak zapisac to zadanko przypuszczam ze są ludzie ktorzy moga pomoc

[PanCiasteczko]

1)drzewo o wysokosci 0 ma max 1 lisc i drzewo o wysokosci 1 ma max 2 liscie

jesli drzewo o wysokosci n moze miec maxymalnie x lisci to dzrewo o jeden poziom wyzsze(n+1) bedzie mialo maxymalni 2*x lisci (z definicji drzewa binarnego, z kazdego liscia wyrosna maxymalnie 2) czyli:

2)jezeli drzewo o wysokosci n moze miec niewiecej niz \(\displaystyle{ 2^{n}}\) lisci to drzewo o wysokosci (n+1) moze miec maxymalnie \(\displaystyle{ 2*2^{n}}\)

z 1 i 2 wynika To Co Nalezala Udowodnic;