0 Daumen
40 Aufrufe

Frage:  Gegeben sei ein ungerichteter gewurzelter Baum B = (V, E) in Kind-Geschwister-Darstellung. Die Wurzel sei r.
Entwerfen Sie einen möglichst effzienten Algorithmus, welcher die Länge eines längsten einfachen
Weges in B berechnet. Geben Sie Ihren Algorithmus in Pseudocode an, analysieren Sie seine Laufzeit
und begründen Sie seine Korrektheit.

Der Pseudocode wäre schon eine sehr große Hilfe bzw. Ansätze dazu.

von

1 Antwort

0 Daumen
struct tree {
  struct tree* child;
  struct tree* next_sibling;
};

int depth(struct tree* n) {
  int c = 0;
  int s = 0;
  if (n->child != 0) {
      c = 1 + depth(n->child);
  }
  if (n->next_sibling != 0) {
      s = depth(n->next_sibling);
  }
  return s > c ? s : c;
}

Linear in der Anzahl der Knoten.

von 4,0 k

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community