J'essaie de prouver qu'un arbre binaire avec nœuds a au plus feuilles. Comment pourrais-je procéder avec l'induction?
Pour les personnes qui suivaient la question initiale sur les tas, elle a été déplacée ici .
J'essaie de prouver qu'un arbre binaire avec nœuds a au plus feuilles. Comment pourrais-je procéder avec l'induction?
Pour les personnes qui suivaient la question initiale sur les tas, elle a été déplacée ici .
Réponses:
Je suppose maintenant que la question est la suivante:
Travaillons avec la définition d'arbre . Pour T un tel arbre, soit n T le nombre de nœuds dans T et l T le nombre de feuilles dans TTree=Empty∣Leaf∣Node(Tree,Tree) T nT T lT T .
Vous avez raison de le faire par induction, mais vous aurez besoin d' une induction structurelle qui suit la structure de l'arbre. Pour les arbres, cela se fait souvent en induction complète sur la hauteurh(T) des arbres.
L'ancre à induction a deux parties. Premièrement, pour nous avons T = E m p t y avec l T = n T = 0 ; la revendication vaut clairement pour l'arbre vide. Pour h ( t ) = 1 , c'est-à-dire T = L e a f , nous avons de même l T = 1 = ⌈ n Th(t)=0 T=Empty lT=nT=0 h(t)=1 T=Leaf lT=1=⌈nT2⌉ , donc la demande est valable pour les feuilles.
L'hypothèse d'induction est: Supposons que la revendication s'applique à tous les arbres (binaires) avec h ( T ) ≤ k , k ≥ 1 arbitraire mais fixe.T h(T)≤k k≥1
Pour l'étape inductive, considérons un arbre binaire arbitraire avec h ( T ) = k + 1 . Comme k ≥ 1 , T = N o d e ( L , R ) et n T = n L + n R + 1 . Comme L et R sont également des arbres binaires (sinon T ne le serait pas) et h ( L ) , h (T h(T)=k+1 k≥1 T=Node(L,R) nT=nL+nR+1 L R T , l'hypothèse d'induction s'applique et ah(L),h(R)≤k
Comme toutes les feuilles de sont soit en L soit en R , nous avons celaT L R
L'inégalité marquée avec peut être vérifiée par une distinction de casse (quadridirectionnelle) pour savoir si n L , n R ∈ 2 N(∗) nL,nR∈2N . Par la puissance de l'induction, cela conclut la preuve.
Comme exercice, vous pouvez utiliser la même technique pour prouver les affirmations suivantes:
la source
Je suis un peu confus par la question. Si vous êtes intéressé par les arbres avec un degré au plus , ce que Wikipédia dit que vous voulez, alors nous rencontrons le problème qu'un seul bord a n = 23 n=2 nœuds et feuilles, mais n / 2 = 1 . Quoi qu'il en soit, voici quelque chose de proche qui a un argument facile. n=2 n/2=1
Soit un tel arbre à n nœuds et L feuilles. Puisque T est un arbre, il y a n - 1 arêtes, et en les comptant deux fois, nous voyons que 2 n - 2 ≤ L + 3 ( n - L ) qui dit queT n L T n - 1
la source