Zum Inhalt springen
View in the app

A better way to browse. Learn more.
Fachinformatiker.de

A full-screen app on your home screen with push notifications, badges and more.

To install this app on iOS and iPadOS
  1. Tap the Share icon in Safari
  2. Scroll the menu and tap Add to Home Screen.
  3. Tap Add in the top-right corner.
To install this app on Android
  1. Tap the 3-dot menu (⋮) in the top-right corner of the browser.
  2. Tap Add to Home screen or Install app.
  3. Confirm by tapping Install.

Beweis Anzahl Knoten eines Baumes

Gast DaKa
Gast DaKa
in Algorithmik

Empfohlene Antworten

Hallo,

wir müssen für unsere nächste Klausur eine Formel beweisen.

Ich kann zwar durch ausprobieren erkennen, dass die Formel korrekt ist, aber habe keine Ahnung wie ich das beweisen kann.

********************************

FOLGENDE PROBLEMSTELLUNG:

- wie berechnet man die Anzahl aller Knoten eines Baumes, wobei die Baumgröße zum einen von der Tiefe des Baumes, zum anderen davon abhängt, wie viele Kindknoten jedes Kind hat.

Es gilt:

- die Tiefe aller Blaetter ist gleich

- er ist echt dÄr (alle Knoten außer den Blättern haben denselben Grad)

FORMEL:

(d^(t+1)-1)/d-1

t:= Tiefe des Baumes

d:= Grad

Setze ich für z.B. d = 3 und t = 2 ein, erhalte ich 13. Dies ist z.B. ja auch die Korrekte Anzahl der Knoten dieses Baumes.

Wie kann ich das allgemeiner beweisen oder diese Formel herleiten?

Vielen Dank für Eure Mühen,

André

vielen Dank für die schnelle Antwort. Hat geklappt -> Induktion war der entscheidende Tipp

Archiv

Dieses Thema wurde archiviert und kann nicht mehr beantwortet werden.

Zur Themenliste gehen

Konto

Navigation

Suchen

Suchen

Configure browser push notifications
Chrome (Android)
  1. Tap the lock icon next to the address bar.
  2. Tap Permissions → Notifications.
  3. Adjust your preference.
Chrome (Desktop)
  1. Click the padlock icon in the address bar.
  2. Select Site settings.
  3. Find Notifications and adjust your preference.