Udowodnienie, że drzewo binarne ma co najwyżej

Próbuję udowodnić, że drzewo binarne z węzłami ma co najwyżej ⌈ $n$liści. Jak miałbym to robić z indukcją?$\left\lceil \frac{n}{2} \right\rceil$

Dla osób, które śledziły pierwotne pytanie o stosy, zostało tu przeniesione .

Zakładam teraz, że pytanie jest następujące:

Biorąc pod uwagę drzewo binarne z węzłami, udowodnij, że zawiera co najwyżej ⌈ $n$liści.$\left\lceil \frac{n}{2} \right\rceil$

Pracujmy z definicją drzewa . Do T takiego drzewa, niech n T liczba węzłów T i L T liczba liści T .$\mathrm{Tree}= \mathrm{Empty}\mid \mathrm{Leaf} \mid \mathrm{Node}(\mathrm{Tree},\mathrm{Tree})$$T$$n_T$$T$$l_T$$T$

Masz rację, robiąc to indukcyjnie, ale potrzebujesz indukcji strukturalnej, która podąża za strukturą drzewa. W przypadku drzew jest to często wykonywane jako całkowita indukcja powyżej wysokości drzew.$h(T)$

Kotwica indukcyjna składa się z dwóch części. Po pierwsze, dla mamy T = E m p t y z l T = n T = 0 ; roszczenie wyraźnie odnosi się do pustego drzewa. Dla h ( t ) = 1 , tj. T = L e a f , podobnie mamy l T = 1 = ⌈ n $h(t)=0$$T=\mathrm{Empty}$$l_T=n_T=0$$h(t)=1$$T = \mathrm{Leaf}$, więc roszczenie dotyczy liści.$l_T=1=\left\lceil \frac{n_T}{2} \right\rceil$

Hipoteza indukcyjna jest następująca: Załóżmy, że twierdzenie dotyczy wszystkich (binarnych) drzew z h ( T ) ≤ k , k ≥ 1 arbitralnie, ale ustalone.$T$$h(T)\leq k$$k\geq 1$

W kroku indukcyjnym rozważ dowolne drzewo binarne z h ( T ) = k + 1 . A k ≥ 1 , T = N O d e ( L , R ) , a n , T = n L + n R + 1 . Ponieważ L i R są również drzewami binarnymi (inaczej T nie byłby) i h ( L ) , h $T$$h(T)=k+1$$k\geq 1$$T=\mathrm{Node}(L,R)$$n_T = n_L+ n_R+1$$L$$R$$T$$h(L),h(R)\leq k$, the induction hypothesis applies and have

$\qquad \displaystyle l_L \leq \left\lceil \frac{n_L}{2} \right\rceil \text{ and } l_R \leq \left\lceil \frac{n_R}{2} \right\rceil.$

As all leaves of $T$ are either in $L$ or $R$, we have that

$\qquad \begin{align*} l_T &= l_L + l_R \\ &\leq \left\lceil \frac{n_L}{2} \right\rceil + \left\lceil \frac{n_R}{2} \right\rceil \\ &\leq \left\lceil \frac{n_L + n_R + 1}{2} \right\rceil \qquad (*)\\ &= \left\lceil \frac{n_T}{2} \right\rceil \end{align*}$

The inequality marked with $(*)$ can be checked by (four way) case distinction over whether $n_L,n_R\in 2\mathbb{N}$. By the power of induction, this concludes the proof.

As an exercise, you can use the same technique to prove the following statements:

• Every perfect binary tree of height $h$ has $2^h-1$ nodes.
• Every full binary tree has an odd number of nodes.

I am a little confused by the question. If you are interested in trees with degree at most $3$, which is what Wikipedia says you want, then we run into the problem that a single edge has $n=2$ nodes and $n=2$ leaves, but $n/2 = 1$. Anyway, here is something close that has an easy argument.

Let $T$ be such a tree with $n$ nodes and $L$ leaves. Since $T$ is a tree, there are $n-1$ edges, and double counting them, we see that