Ternärer Baum als Pseudocode?

In dieser Aufgabe betrachten wir gewurzelte ternäre Bäume. Jeder Knoten v kann also ein linkes Kind v.L, ein mittleres Kind v.M und/oder ein rechtes Kind v.R haben. Wir möchten nun herausfinden, wie viele Knoten im Baum sind.Gebe jeweils einen rekursiven Algorithmus in Pseudocode an, der durch den Aufruf count(v0) die Anzahl n der Knoten im Baum mit Wurzel v0 bestimmt. Begründe die Korrektheit der Algorithmen.

a) Gehe für den Entwurf deines Algorithmus zuerst davon aus, dass der Baum vollständig ist, also jeder Knoten entweder genau drei Kinder oder gar kein Kind besitzt und für jedes Blatt der Weg von der Wurzel die gleiche Länge hat. Stelle eine Rekursionsgleichung für die Laufzeit auf und löse diese mithilfe des Master-Theorems. Der Algorithmus soll eine Laufzeit von o(n)haben.

b) Wie verändern sich Algorithmus und Laufzeit, wenn Sie allgemeine ternäre Bäume betrachten?

________________________________________________________

Es geht um Pseudo-Code. In der Vorlesung benutzen wir C (obwohl wir C eigentlich erst nächstes Semester lernen), also wir lassen immer Klammern auf und schließen diese erst in der nächsten oder ubernächsten Zeile und erhöhen Variablen durch i++.

Ich habe mir überlegt, weil das ganze ein ternärer Baum sein soll und die Länge gezählt wird:

var counter = 0
    for b = 0; b ≤ n; b++) {
        for (l = 1, l++) {
             l = l + 1
}
        for (m = m, m++) {
             m = m + 1
}
        for (r = r, r++) {
             r = r + 1
}
        counter = counter + 1
}

wobei b die, ich nenn's jetzt einfach mal "Oberschleife" ,für den Baum an sich ist und l, m und r jeweils Unterschleifen, wobei l = links, m = mitte, r = rechts. Glaube aber, dass ich's mir hiermit zu einfach mache.

Zudem muss das Ganze ja noch als rekursive Funktion geschrieben werden, also der Form T (n) = a * T (n/b) + f(n), wobei b in diesem Fall = 3 ist, weil es ja ein ternärer Baum ist. Aber was ist a? Man könnte ja theoretisch unendlich viele Kinderknoten haben? Oder versteh ich da was falsch?

Answer 1

[KarlRanseierIII]

Einfacher Pseudocode für rekursive Variante:

int count(v0):
   if (v0)=NULL:
      return 0 #Abbruchbedingung
   return 1+count(v0.l)+count(v0.m)+count(v0.r)

Das wars schon, kurz und schmerzlos.

Answer 2

[regex9]

Es geht um Pseudo-Code (...)

Für deine einzelnen Schleifen solltest du dennoch eine Laufzeitbedingung angeben, so wie du es bei der obersten Schleife auch getan hast. Auch die öffnende Klammer vor dem b fehlt. 😀

Insgesamt ist dein Pseudocode wohl kaum funktionstüchtig. Im Vorfeld wäre es notwendig, n zu kennen - also die Anzahl an Ebenen. Wozu die inneren Schleifen dienen, verstehe ich nicht. Die rekursive Formulierung ist hier viel einfacher.

Zudem muss das Ganze ja noch als rekursive Funktion geschrieben werden (...)

Je Schritt läufst du über alle Kindknoten des aktuellen Knotens und rufst zu diesen jeweils wieder den nächsten Schritt auf.

traverse(root):
  iterate over root.children:
    traverse(child)

Dazu muss noch die Zählung ergänzt werden. Du hast hierfür verschiedene Optionen, bspw. eine globale Variable oder besser, wenn du die Anzahl an Kindknoten in jedem Schritt zurückgibst, wobei natürlich die Kindknoten der folgenden rekursiven Aufrufe mit dazu addiert werden müssen:

traverse(root):
  sum = count(root.children)

  iterate over root.children:
    sum += traverse(child)

  return sum

Man könnte ja theoretisch unendlich viele Kinderknoten haben? Oder versteh ich da was falsch?

Der Baum kann eine Tiefe von n haben, wobei jeder Knoten maximal drei Kindknoten besitzt.

Comments

[regex9]

Nachtrag zu obigem Algorithmus: Die Wurzel sollte man noch mitrechnen, sofern es um die Anzahl aller Knoten im Baum geht.