Bei einem gegebenen Binärbaum besteht die Aufgabe darin, die Höhe des Baums zu ermitteln. Die Höhe des Baumes ist die Anzahl der Eckpunkte im Baum von der Wurzel bis zum tiefsten Knoten.

Notiz: Die Höhe eines leeren Baumes beträgt 0 und die Höhe eines Baumes mit einem einzelnen Knoten beträgt 1 .

Beispiel eines Binärbaums

Govinda-Schauspieler

Berechnen Sie rekursiv die Höhe des links und das Rechts Teilbäume eines Knotens und weisen Sie dem Knoten eine Höhe zu als Maximale Körpergröße von zwei Kindern plus 1 . Einzelheiten finden Sie unten im Pseudocode und im Programm.

Illustration:

Betrachten Sie den folgenden Baum:

Beispiel für einen Baum

maxDepth(‘1’) = max(maxDepth(‘2’), maxDepth(‘3’)) + 1 = 2 + 1

Java-Arraylist sortiert

weil rekursiv
maxDepth('2') = max (maxDepth('4'), maxDepth('5')) + 1 = 1 + 1 und (da die Höhe von '4' und '5' 1 ist)
maxDepth(‘3’) = 1

Befolgen Sie die folgenden Schritte, um die Idee umzusetzen:

• Führen Sie rekursiv eine Tiefensuche durch.
• Wenn der Baum leer ist, wird 0 zurückgegeben
• Andernfalls gehen Sie wie folgt vor
  • Ermitteln Sie rekursiv die maximale Tiefe des linken Teilbaums, d. h. rufen Sie maxDepth( tree->left-subtree) auf.
  • Ermitteln Sie rekursiv die maximale Tiefe des rechten Teilbaums, d. h. rufen Sie maxDepth( tree->right-subtree) auf.
  • Holen Sie sich das Maximum an maximalen Tiefen von links Und Rechts Teilbäume und 1 hinzufügen dazu für den aktuellen Knoten.
    • 
• Gibt max_ Depth zurück.

Nachfolgend finden Sie die Umsetzung des oben genannten Ansatzes:

C++

>

>

C

>

>

Java

>

>

Python3

>

>

C#

>

>

Javascript

>

>

Height of tree is 3>

Zeitkomplexität: O(N) (Siehe bitte den Beitrag auf Baumdurchquerung für Details)
Hilfsraum: O(N) aufgrund des rekursiven Stapels.

Java für Pause

Finden Sie die maximale Tiefe oder Höhe eines Baumes mit Level-Order-Traversal :

Tun Level-Order-Traversal , während Knoten auf jeder Ebene hinzugefügt werden Befolgen Sie die folgenden Schritte, um die Idee umzusetzen:

Kajal Aggarwal

• Durchlaufen Sie den Baum in der Ebenenreihenfolge, beginnend mit Wurzel .
  • Initialisieren Sie eine leere Warteschlange Q , eine Variable Tiefe und schieben Wurzel , dann drücken Null in die Q .
  • Führen Sie eine While-Schleife aus, bis Q ist nicht leer.
    • Bewahren Sie das vordere Element auf Q und das vordere Element herausziehen.
    • Wenn die Vorderseite von Q Ist NULL dann erhöhen Tiefe um eins und wenn die Warteschlange nicht leer ist, drücken Sie NULL in die Q .
    • Andernfalls, wenn das Element nicht vorhanden ist NULL Dann prüfen Sie, ob es so ist links Und Rechts Kinder und wenn nicht NULL drücke sie hinein Q .
• Zurückkehren Tiefe .

Nachfolgend finden Sie die Umsetzung des oben genannten Ansatzes:

C++

#include> #include> using> namespace> std;> // A Tree node> struct> Node {> >int> key;> >struct> Node *left, *right;> };> // Utility function to create a new node> Node* newNode(>int> key)> {> >Node* temp =>new> Node;> >temp->key = key;> >temp->links = temp->rechts = NULL;> >return> (temp);> }> /*Function to find the height(depth) of the tree*/> int> height(>struct> Node* root)> {> >// Initialising a variable to count the> >// height of tree> >int> depth = 0;> >queue q;> >// Pushing first level element along with NULL> >q.push(root);> >q.push(NULL);> >while> (!q.empty()) {> >Node* temp = q.front();> >q.pop();> >// When NULL encountered, increment the value> >if> (temp == NULL) {> >depth++;> >}> >// If NULL not encountered, keep moving> >if> (temp != NULL) {> >if> (temp->links) {> >q.push(temp->links);> >}> >if> (temp->rechts) {> >q.push(temp->rechts);> >}> >}> >// If queue still have elements left,> >// push NULL again to the queue.> >else> if> (!q.empty()) {> >q.push(NULL);> >}> >}> >return> depth;> }> // Driver program> int> main()> {> >// Let us create Binary Tree shown in above example> >Node* root = newNode(1);> >root->left = newNode(2);> >root->right = newNode(3);> >root->left->left = newNode(4);> >root->links->rechts = newNode(5);> >cout <<>'Height(Depth) of tree is: '> << height(root);> }>

>

>

Java

// Java program for above approach> import> java.util.LinkedList;> import> java.util.Queue;> class> GFG {> >// A tree node structure> >static> class> Node {> >int> key;> >Node left;> >Node right;> >}> >// Utility function to create> >// a new node> >static> Node newNode(>int> key)> >{> >Node temp =>new> Node();> >temp.key = key;> >temp.left = temp.right =>null>;> >return> temp;> >}> >/*Function to find the height(depth) of the tree*/> >public> static> int> height(Node root)> >{> >// Initialising a variable to count the> >// height of tree> >int> depth =>0>;> >Queue q =>new> LinkedList();> >// Pushing first level element along with null> >q.add(root);> >q.add(>null>);> >while> (!q.isEmpty()) {> >Node temp = q.peek();> >q.remove();> >// When null encountered, increment the value> >if> (temp ==>null>) {> >depth++;> >}> >// If null not encountered, keep moving> >if> (temp !=>null>) {> >if> (temp.left !=>null>) {> >q.add(temp.left);> >}> >if> (temp.right !=>null>) {> >q.add(temp.right);> >}> >}> >// If queue still have elements left,> >// push null again to the queue.> >else> if> (!q.isEmpty()) {> >q.add(>null>);> >}> >}> >return> depth;> >}> >// Driver Code> >public> static> void> main(String args[])> >{> >Node root = newNode(>1>);> >root.left = newNode(>2>);> >root.right = newNode(>3>);> >root.left.left = newNode(>4>);> >root.left.right = newNode(>5>);> >System.out.println(>'Height(Depth) of tree is: '> >+ height(root));> >}> }> // This code is contributed by jana_sayantan.>

>

>

Python3

# Python code to implement the approach> # A Tree node> class> Node:> >def> __init__(>self>):> >self>.key>=> 0> >self>.left,>self>.right>=> None>,>None> # Utility function to create a new node> def> newNode(key):> >temp>=> Node()> >temp.key>=> key> >temp.left, temp.right>=> None>,>None> >return> temp> # Function to find the height(depth) of the tree> def> height(root):> ># Initialising a variable to count the> ># height of tree> >depth>=> 0> >q>=> []> ># appending first level element along with None> >q.append(root)> >q.append(>None>)> >while>(>len>(q)>>0>):> >temp>=> q[>0>]> >q>=> q[>1>:]> ># When None encountered, increment the value> >if>(temp>=>=> None>):> >depth>+>=> 1> ># If None not encountered, keep moving> >if>(temp !>=> None>):> >if>(temp.left):> >q.append(temp.left)> >if>(temp.right):> >q.append(temp.right)> ># If queue still have elements left,> ># append None again to the queue.> >elif>(>len>(q)>>0>):> >q.append(>None>)> >return> depth> # Driver program> # Let us create Binary Tree shown in above example> root>=> newNode(>1>)> root.left>=> newNode(>2>)> root.right>=> newNode(>3>)> root.left.left>=> newNode(>4>)> root.left.right>=> newNode(>5>)> print>(f>'Height(Depth) of tree is: {height(root)}'>)> # This code is contributed by shinjanpatra>

>

>

C#

// C# Program to find the Maximum Depth or Height of Binary Tree> using> System;> using> System.Collections.Generic;> // A Tree node> public> class> Node {> >public> int> data;> >public> Node left, right;> >public> Node(>int> item)> >{> >data = item;> >left =>null>;> >right =>null>;> >}> }> public> class> BinaryTree {> >Node root;> >// Function to find the height(depth) of the tree> >int> height()> >{> >// Initialising a variable to count the> >// height of tree> >int> depth = 0;> >Queue q =>new> Queue();> >// Pushing first level element along with NULL> >q.Enqueue(root);> >q.Enqueue(>null>);> >while> (q.Count != 0) {> >Node temp = q.Dequeue();> >// When NULL encountered, increment the value> >if> (temp ==>null>)> >depth++;> >// If NULL not encountered, keep moving> >if> (temp !=>null>) {> >if> (temp.left !=>null>) {> >q.Enqueue(temp.left);> >}> >if> (temp.right !=>null>) {> >q.Enqueue(temp.right);> >}> >}> >// If queue still have elements left,> >// push NULL again to the queue> >else> if> (q.Count != 0) {> >q.Enqueue(>null>);> >}> >}> >return> depth;> >}> >// Driver program> >public> static> void> Main()> >{> >// Let us create Binary Tree shown in above example> >BinaryTree tree =>new> BinaryTree();> >tree.root =>new> Node(1);> >tree.root.left =>new> Node(2);> >tree.root.right =>new> Node(3);> >tree.root.left.left =>new> Node(4);> >tree.root.left.right =>new> Node(5);> >Console.WriteLine(>'Height(Depth) of tree is: '> >+ tree.height());> >}> }> // This code is contributed by Yash Agarwal(yashagarwal2852002)>

>

>

Javascript

> // JavaScript code to implement the approach> // A Tree node> class Node{> >constructor(){> >this>.key = 0> >this>.left =>null> >this>.right =>null> >}> }> // Utility function to create a new node> function> newNode(key){> >let temp =>new> Node()> >temp.key = key> >temp.left =>null> >temp.right =>null> >return> temp> }> // Function to find the height(depth) of the tree> function> height(root){> >// Initialising a variable to count the> >// height of tree> >let depth = 0> >let q = []> > >// pushing first level element along with null> >q.push(root)> >q.push(>null>)> >while>(q.length>0){> >let temp = q.shift()> > >// When null encountered, increment the value> >if>(temp ==>null>)> >depth += 1> > >// If null not encountered, keep moving> >if>(temp !=>null>){> >if>(temp.left)> >q.push(temp.left)> > >if>(temp.right)> >q.push(temp.right)> >}> > >// If queue still have elements left,> >// push null again to the queue.> >else> if>(q.length>0)> >q.push(>null>)> >}> >return> depth> }> // Driver program> // Let us create Binary Tree shown in above example> let root = newNode(1)> root.left = newNode(2)> root.right = newNode(3)> root.left.left = newNode(4)> root.left.right = newNode(5)> document.write(`Height(Depth) of tree is: ${height(root)}`,>''>)> // This code is contributed by shinjanpatra> >

>

>

Ausgabe

Height(Depth) of tree is: 3>

Zeitkomplexität: AN)
Hilfsraum: AN)

Eine weitere Methode, um die Höhe zu ermitteln Level-Order-Traversal :

Diese Methode verwendet auch das Konzept des Level Order Traversal, aber wir werden der Warteschlange keine Null hinzufügen. Erhöhen Sie einfach die Schalter Wenn die Ebene steigt und die untergeordneten Knoten des aktuellen Knotens in die Warteschlange verschoben werden, werden dann alle Knoten der aktuellen Ebene aus der Warteschlange entfernt.

C++

// C++ program for above approach> #include> using> namespace> std;> // A Tree node> struct> Node {> >int> key;> >struct> Node *left, *right;> };> // Utility function to create a new node> Node* newNode(>int> key)> {> >Node* temp =>new> Node;> >temp->key = key;> >temp->links = temp->rechts = NULL;> >return> (temp);> }> /*Function to find the height(depth) of the tree*/> int> height(Node* root)> {> >// Initialising a variable to count the> >// height of tree> >queue q;> >q.push(root);> >int> height = 0;> >while> (!q.empty()) {> >int> size = q.size();> >for> (>int> i = 0; i Node* temp = q.front(); q.pop(); if (temp->left != NULL) { q.push(temp->left); } if (temp->right != NULL) { q.push(temp->right); } } height++; } return height; } // Treiberprogramm int main() { // Lassen Sie uns den im obigen Beispiel gezeigten Binärbaum erstellen Node* root = newNode(1); root->left = newNode(2); root->right = newNode(3); root->left->left = newNode(4); root->left->right = newNode(5); cout<< 'Height(Depth) of tree is: ' << height(root); } // This code is contributed by Abhijeet Kumar(abhijeet19403)>

>

>

Java

// Java program for above approach> import> java.util.LinkedList;> import> java.util.Queue;> class> GFG {> >// A tree node structure> >static> class> Node {> >int> key;> >Node left;> >Node right;> >}> >// Utility function to create> >// a new node> >static> Node newNode(>int> key)> >{> >Node temp =>new> Node();> >temp.key = key;> >temp.left = temp.right =>null>;> >return> temp;> >}> >/*Function to find the height(depth) of the tree*/> >public> static> int> height(Node root)> >{> >// Initialising a variable to count the> >// height of tree> >Queue q =>new> LinkedList();> >q.add(root);> >int> height =>0>;> >while> (!q.isEmpty()) {> >int> size = q.size();> >for> (>int> i =>0>; i Node temp = q.poll(); if (temp.left != null) { q.add(temp.left); } if (temp.right != null) { q.add(temp.right); } } height++; } return height; } // Driver Code public static void main(String args[]) { Node root = newNode(1); root.left = newNode(2); root.right = newNode(3); root.left.left = newNode(4); root.left.right = newNode(5); System.out.println('Height(Depth) of tree is: ' + height(root)); } }>

>

>

Python3

# Python3 program to find the height of a tree> > # A binary tree node> class> Node:> > ># Constructor to create a new node> >def> __init__(>self>, data):> >self>.key>=> data> >self>.left>=> None> >self>.right>=> None> > # Function to find height of tree> def> height(root):> ># Base Case> >if> root>is> None>:> >return> 0> > ># Create an empty queue for level order traversal> >q>=> []> > ># Enqueue Root and initialize height> >q.append(root)> >height>=> 0> > ># Loop while queue is not empty> >while> q:> > ># nodeCount (queue size) indicates number of nodes> ># at current level> >nodeCount>=> len>(q)> > ># Dequeue all nodes of current level and Enqueue all> ># nodes of next level> >while> nodeCount>>0>:> >node>=> q.pop(>0>)> >if> node.left>is> not> None>:> >q.append(node.left)> >if> node.right>is> not> None>:> >q.append(node.right)> >nodeCount>->=> 1> >height>+>=> 1> > >return> height> > # Driver Code> root>=> Node(>1>)> root.left>=> Node(>2>)> root.right>=> Node(>3>)> root.left.left>=> Node(>4>)> root.left.right>=> Node(>5>)> > print>(>'Height(Depth) of tree is'>, height(root))>

>

>

C#

using> System;> using> System.Collections.Generic;> class> GFG {> >// A Tree node> >class> Node {> >public> int> key;> >public> Node left, right;> >public> Node(>int> key)> >{> >this>.key=key;> >this>.left=>this>.right=>null>;> >}> >}> >// Utility function to create a new node> >/*Node newNode(int key)> >{> >Node* temp = new Node;> >temp.key = key;> >temp.left = temp.right = NULL;> >return (temp);> >}*/> >/*Function to find the height(depth) of the tree*/> >static> int> height(Node root)> >{> >// Initialising a variable to count the> >// height of tree> >Queue q=>new> Queue();> >q.Enqueue(root);> >int> height = 0;> >while> (q.Count>0) {> >int> size = q.Count;> >for> (>int> i = 0; i Node temp = q.Peek(); q.Dequeue(); if (temp.left != null) { q.Enqueue(temp.left); } if (temp.right != null) { q.Enqueue(temp.right); } } height++; } return height; } // Driver program public static void Main() { // Let us create Binary Tree shown in above example Node root = new Node(1); root.left = new Node(2); root.right = new Node(3); root.left.left = new Node(4); root.left.right = new Node(5); Console.Write('Height(Depth) of tree is: ' + height(root)); } } // This code is contributed by poojaagarwal2.>

>

>

Javascript

// JavaScript program for above approach> // a tree node> class Node{> >constructor(key){> >this>.key = key;> >this>.left =>this>.right =>null>;> >}> }> // utility function to create a new node> function> newNode(key){> >return> new> Node(key);> }> // function to find the height of the tree> function> height(root){> >// initialising a variable to count the> >// height of tree> >let q = [];> >q.push(root);> >let height = 0;> >while>(q.length>0){> >let size = q.length;> >for>(let i = 0; i let temp = q.shift(); if(temp.left != null){ q.push(temp.left); } if(temp.right != null){ q.push(temp.right); } } height++; } return height; } // driver code let root = newNode(1); root.left = newNode(2); root.right = newNode(3); root.left.left = newNode(4); root.left.right = newNode(5); document.write('Height(Depth) of tree is: ' + height(root)); // this code is contributed by Kirti Agarwal(kirtiagarwal23121999)>

>

>

Ausgabe

Height(Depth) of tree is: 3>

Zeitkomplexität: AN)
Hilfsraum: AN)