Beräkna höjden på valfritt träd i Java (icke-binärt träd)

Att beräkna höjden på ett träd inom datavetenskap är mycket vanligt. De flesta av exemplen och onlinediskussioner handlar om att beräkna höjden på ett binärt träd.

Exempelmetoden jag delar kan användas för att beräkna höjden på vilket träd som helst. Så även om du har ett icke-binärt träd kan du använda den här metoden för att få trädets höjd.

Eftersom vi pratar om ett icke-binärt träd kan en nod ha fler än två barn, så vi måste deklarera barnen som en lista i Node-klassen. Här är min Node-klass.

class Node<E> {
	int height;
	Node<E> parent;
	List<Node<E>>childern;
}

Som du kan se har vi ett fält av typen Node för att referera till den överordnade noden, och en lista med noder för att referera till barnen till denna nod.

Med den här klassdefinitionen med rekursion kan vi beräkna höjden på ett träd (inklusive icke-binärt träd).

getTreeHeight:

public int getTreeHeight(Node<Integer> root) {
   int height = 0;
    if (root == null ) {
	return height;
    }
    if (root.childern == null) {
	return 1;
  }

   for (Node<Integer> child : root.childern) {
	height = Math.max(height, getTreeHeight(child));
  }
   return height + 1;
}