Anzahl Binärbäume mit n inneren Knoten

Neue Frage »

binary Auf diesen Beitrag antworten »
Anzahl Binärbäume mit n inneren Knoten
Hallo!

Ich suche eine rekursive Formel für die Anzahl der Binarytrees mit n inneren Knoten.
Dabei ist ein binarytree bei uns so definiert:
1. ein Knoten hat 0,1 oder 2 Nachfolger
2. ein innerer Knoten ist ein Knoten, der mindestens einen Nachfolger hat.


Tja, ich bin bei der ganzen Geschichte nicht besonders weit gekommen.
Irgendwie habe ich mir in diesen 20Minuten bisher nur überlegen können, dass jeder innere Knoten 2 Möglichkeiten hat: 1 oder 2 Nachfolger.
2^n alleine tuts aber natürlich nicht...

Ich hoffe ihr könnt mir zumindest Denkanstöße geben!!

Dankescön! Freude
AD Auf diesen Beitrag antworten »

Sei die gesuchte Anzahl.

Du solltest das Problem bei der "Wurzel" packen, im wahrsten Sinne des Wortes! Für die gibt es im Fall nur zwei Möglichkeiten:


1.Fall: genau 1 Nachfolger

In dem Fall gibt es genau Möglichkeiten für den einen Unterbaum.


2.Fall: genau 2 Nachfolger

Hier hat der "linke" Unterbaum genau , und der rechte Unterbaum genau innere Knoten. Welche k da möglich sind, und wie man nun die Anzahlen der jeweiligen Unterbäume verknüpft, solltest du dir überlegen.
binary Auf diesen Beitrag antworten »

hi und danke schonmal!

Ok, also ich habe darüber nachgedacht, bin mir aber gar nicht sicher.

Also k muss logischerweise echt kleiner als n sein.
Im Fall "genau 2 Nachfolger" ist es also für a_n interessant, wie groß k ist.
k kann sein 1,2,...,n-1. Nehmen wir ein festes k dann wären doch sowas wie
alle möglichen Unterbäume, oder? Da k jetzt aber die oben genannten Zahlen durchläuft würde ich sagen, dass diese Zahl tatsächlich
ist. Um den Fall 1 auch noch zu berücksichtigen bin ich dann abschließend auf:
gekommen.

Als Abbruchbedingung würde ich a_1 = 2 vorschlagen, unter der Voraussetzung dass bei Blättern nicht mehr zwischen rechts und links unterschieden wird (so war das irgendwie in einer vorigen Aufgabe..)

Hoffe das war nicht allzu großer Mist, den ich hier verzapft hab... verwirrt
AD Auf diesen Beitrag antworten »

Ja, allerdings solltest du noch hinzunehmen (nur 1 Blatt, ohne innere Knoten).

Was mich allerdings jetzt stutzen lässt ist: Gibt es bei nur einem Nachfolger einen Unterschied zwischen einem "nur linken" bzw. "nur rechten" Nachfolger in Fall 1? Das ist jetzt keine mathematische, sondern eine Definitionsfrage, wann du zwei Bäume als verschieden ansiehst! verwirrt


Kann sein, dass ich jetzt Unsinn geredet habe, aber ich stell mir das gerade aus Programmierperspektive vor mit festen vorgesehenen Pointern für linken und rechten Teilbaum...
binary Auf diesen Beitrag antworten »

ah cool, dann war das gar nicht so schlecht, was ich oben erzählt hab? smile

richtig a0=1 sollte ich noch hinzunehmen.

Zitat:

Was mich allerdings jetzt stutzen lässt ist: Gibt es bei nur einem Nachfolger einen Unterschied zwischen einem "nur linken" bzw. "nur rechten" Nachfolger in Fall 1? Das ist jetzt keine mathematische, sondern eine Definitionsfrage, wann du zwei Bäume als verschieden ansiehst!

Du hast recht, dass ist wirklich eine Frage der Definition.
So ganz sicher bin ich mir da jetzt auch nicht, wie das gemeint ist. Bei einer Aufgabe davor war es, nach langem hin und her mit den Assistenten, so gemeint, dass man zwischen links und rechts unterscheiden muss, wenn der Knoten mindestens (hier dann wohl genau) 2 nicht leere Teilbäume hat.

Das hätten wir doch sogar richtig umgesetzt oder? Denn wir unterscheiden bei einem Nachfolger ja nicht zwischen links und rechts...
AD Auf diesen Beitrag antworten »

Genau - wenn es nicht unterschieden werden soll (bei genau einem Nachfolger), dann sollte deine Version bereits stimmen.
 
 
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »