Wie man eine Höhe eines Baumes berechnet

Question

Ich versuche DSA zu lernen und blieb bei einem Problem stecken.

So berechnen Sie die Höhe eines Baumes. Ich meine normalen Baum, keine spezifische Implementierung von Baum wie BT oder BST.

Ich habe versucht google aber scheint jeder über Binary Tree und nichts ist für den normalen Baum verfügbar.

Kann mir jemand helfen, auf einige Seiten oder Artikel umzuleiten, um die Höhe eines Baumes zu berechnen.

Answer 1

Nehmen wir an, ein typischer Knoten in Ihrem Baum wird als Java-Klasse dargestellt.

class Node{ 
    Entry entry; 
    ArrayList<Node> children; 
    Node(Entry entry, ArrayList<Node> children){ 
     this.entry = entry; 
     this.children = children; 
    } 
    ArrayList<Node> getChildren(){ 
     return children; 
    } 
} 

Dann kann eine einfache Höhenfunktion sein -

int getHeight(Node node){ 
    if(node == null){ 
     return 0; 
    }else if(node.getChildren() == null){ 
     return 1; 
    } else{ 
     int childrenMaxHeight = 0; 
     for(Node n : node.getChildren()){ 
      childrenMaxHeight = Math.max(childrenMaxHeight, getHeight(n)); 
     } 
     return 1 + childrenMaxHeight; 
    } 
} 

Dann brauchen Sie nur diese Funktion aufrufen, die Wurzel des Baumes als Argument übergeben. Da es alle Knoten genau einmal durchläuft, ist die Laufzeit O (n).

Answer 2

Im Falle eines 'normalen Baumes' können Sie rekursiv die Höhe des Baumes in ähnlicher Weise wie bei einem Binärbaum berechnen, aber hier müssen Sie alle Kinder an einem Knoten betrachten und nicht nur zwei.

Answer 3

Um eine Baumhöhe zu finden, wird eine BFS-Iteration funktionieren.

aufbereiteter Form Wikipedia:

Breadth-First-Search(Graph, root): 

    create empty set S 
    create empty queues Q1, Q2  

    root.parent = NIL 

    height = -1 

    Q1.enqueue(root)      
    while Q1 is not empty: 

     height = height + 1 
     switch Q1 and Q2 

     while Q2 is not empty: 
      for each node n that is adjacent to current: 
       if n is not in S: 
        add n to S 
        n.parent = current 
        Q1.enqueue(n) 

Sie können sehen, dass eine andere Warteschlange hinzugefügt mir erlaubt, von dem Baum zu wissen, auf welcher Ebene. Es iteriert für jede Ebene und für jeden Modus in dieser Ebene.

Dies ist eine diskursive Möglichkeit, dies zu tun (Gegenteil von rekursiv). Du musst dir deswegen auch keine Sorgen machen.

Laufzeit ist O (| V | + | E |).