Algorithmus: Tiefe Baum

Question

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.

Answer 1

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.