Finden Sie die maximale Tiefe des Baumes

Ich habe eine Baumstruktur mit N first-level child-Knoten, die Kinder auch.

Beispiel:

  • Root
    • Node1
      • Node11
        • Node111
          • Node1111
      • Node12
    • Node2
      • Node21
        • Node211

Ich würde gerne wissen, welche von den Fächern hat die größte Tiefe. Wie im vorherigen Beispiel wird es

Node1 - Node11 - Node111 - Node1111

dass hat eine Tiefe von vier Ebenen.

Jede Anregung?

Dank!

  • Ist dieses Hausaufgaben?
  • Was meinst du mit Hausaufgaben?
  • Sie weiß, was Hausaufgabe ist, richtig?
InformationsquelleAutor Vincenzo | 2010-02-21
  1. 4

    Überprüfen Sie alle Knoten. Vor einigen Monaten habe ich implementiert diesen Algorithmus in dieser Weise:

    class Node
{
    public String Name { get; private set; }
    public IList<Node> Childs { get; private set; }

    public Node(String name)
    {
        Name = name;
        Childs = new List<Node>();
    }

    public List<Node> Depth
    {
        get
        {
            List<Node> path = new List<Node>();
            foreach (Node node in Childs)
            {
                List<Node> tmp = node.Depth;
                if (tmp.Count > path.Count)
                    path = tmp;
            }
            path.Insert(0, this);
            return path;
        }
    }

    public override string ToString()
    {
        return Name;
    }
}

    Beispiel testen:

    Node node1111 = new Node("Node1111");
Node node111 = new Node("Node111");
Node node11 = new Node("Node11");
Node node12 = new Node("Node12");
Node node1 = new Node("Node1");
Node root = new Node("Root");
Node node2 = new Node("Node2");
Node node21 = new Node("Node21");
Node node211 = new Node("Node211");
root.Childs.Add(node1);
root.Childs.Add(node2);
node1.Childs.Add(node11);
node1.Childs.Add(node12);
node11.Childs.Add(node111);
node111.Childs.Add(node1111);
node2.Childs.Add(node21);
node21.Childs.Add(node211);

List<Node> path = root.Depth;
foreach (Node n in path)
    Console.Write(String.Format("{0} - ", n.ToString()));

Console.WriteLine();

Node node2111 = new Node("Node2111");
node2111.Childs.Add(new Node("Node21111"));
node211.Childs.Add(node2111);

path = root.Depth;
foreach (Node n in path)
    Console.Write(String.Format("{0} - ", n.ToString()));

Console.WriteLine();

    Ausgabe der Konsole:

    Root - Node1 - Node11 - Node111 - Node1111 -
Root - Node2 - Node21 - Node211 - Node2111 - Node21111 -
    • Dies ist fast die gleiche Art, wie ich es Tat, aber ich musste die Implementierung in C.
    • Schöne Lösung. Zwei Anregungen. Zuerst, "Tiefe" ist schlecht benannt. Nicht wieder die Tiefe. Es sollte aufgerufen werden, "PathToDeepestLeaf". Zweite, Eigenschaften vorbehalten sein sollte (1) Dinge, die sind logisch Eigenschaften, wie Farbe oder Tiefe, nicht zu Komplex berechnet, Dinge wie "der Weg zum untersten Blatt", (2) Dinge, die sehr schnell zu berechnen, auf der gleichen Geschwindigkeit wie der Zugriff auf ein Feld. Ich würde diese eine Methode, nicht eine Eigenschaft.
    • Eine Herausforderung für Sie: der Baum kann sehr, sehr tief. Angenommen, es ist ein tausend Knoten tief und so viel Rekursion wird Schlag den stack. Können tun Sie es ohne Rekursion?
    • Danke für deine Tipps. Ich werde versuchen zu schreiben, den Algorithmus ohne Rekursion.Rekursion-version ist für mich am einfachsten.
    • Vielen Dank für Eure Antworten und Kommentare! Neben Eric Lippert Kommentare, auf die ich Stimme fast vollständig, die Lösung die du vorgeschlagen hast war auch meine erste Idee. Ich habe codiert mit Rekursion und es funktionierte perfekt. Aber....es ist ein bisschen "un-optimiert"! Irgendeinen Vorschlag dazu?
    InformationsquelleAutor Michał Ziober
  2. 0

    Die einfachste ist ein brute-force-Algorithmus die zählt jeder Weg, speichert Zeiger auf alle die Knoten, und misst die Tiefe. Für jeden Pfad, die länger als einen letzten Weg, vergessen Sie alle anderen Wege, und erinnere nur an den längsten.

    InformationsquelleAutor wallyk
  3. 0
    The deepest branch from a node is:
    the longest of the respective deepest branches from each child node
    prepended with the current node.
    InformationsquelleAutor Svante
  4. 0

    Traverse den Baum depth-first oder breadth-first, ist die Zuweisung an jeden Knoten seine Tiefe. Denken Sie daran, die Knoten mit der höchsten Tiefe.

    Navigieren recusrivle wieder von diesem Knoten zur Wurzel. Dies gibt Ihnen die lngest Zweig. Möglicherweise gibt es mehr als eine Verzweigung mit der gleichen Länge.

    InformationsquelleAutor Carsten
  5. 0

    Wenn Sie irgendeine form von iterator über Ihren Baum können Sie dann eine vollkommen Banale Herangehensweise an die max Tiefe.

    Hier dumme one-liner zeigt das Konzept für die Suche nach maximal erreichbare Dateisystem Tiefe mit UNIX find, awk und tr:

    find / -depth | tr -dc '/\n' \
    | awk '{if (length($0) > max) { max=length($0)}}; END {print max}'

    ... find ist der iterator tr ist ein Daten-manipulation "übersetzen" einen Satz von Zeichen in eine andere (in diesem Fall ist es verwendet wird, um -d (delete) das Komplement (- ) c) der single-Zeichensatz angegeben wird (/). Also es wandelt UNIX-vollständigen Pfad in der /Separatoren. Von dort find ich nur die längste Zeile der Eingabe ... und das ist mein Ergebnis.

    Natürlich dieser Ansatz wird nicht viel helfen, mit Ihren Hausaufgaben. Aber das Konzept sollte klar sein. 🙂

    InformationsquelleAutor Jim Dennis
Schreibe einen Kommentar