Gitt et binært tre, er oppgaven å finne høyden på treet. Høyden på treet er antall topper i treet fra roten til den dypeste noden.

Merk: Høyden på et tomt tre er 0 og høyden på et tre med enkelt node er 1 .

Eksempel på binært tre

for loop java

Beregn rekursivt høyden på venstre og Ikke sant undertrær til en node og tilordne høyde til noden som maks høyden til to barn pluss 1 . Se pseudokoden og programmet nedenfor for detaljer.

Illustrasjon:

Tenk på følgende tre:

Eksempel på tre

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

fordi rekursivt
maxDepth(‘2’) = maks (maxDepth(‘4’), maxDepth(‘5’)) + 1 = 1 + 1 og (ettersom høyden på både ‘4’ og ‘5’ er 1)
maxDepth('3') = 1

i streng i java

Følg trinnene nedenfor for å implementere ideen:

• Gjør et dybde-først-søk rekursivt.
• Hvis treet er tomt, returner 0
• Ellers gjør du følgende
  • Få maksdybden til venstre undertre rekursivt, dvs. kall maxDepth(tre->venstre-undertre)
  • Få maksdybden til høyre undertre rekursivt, dvs. kall maxDepth(tre->høyre-undertre)
  • Få maks maks dybder av venstre og Ikke sant undertrær og legg til 1 til den for gjeldende node.
    • 
• Retur max_depth.

Nedenfor er implementeringen av tilnærmingen ovenfor:

C++

>

>

C

>

>

Java

>

>

Python3

>

>

C#

>

>

Javascript

>

>

Height of tree is 3>

Tidskompleksitet: O(N) (Se innlegget på Traversering av tre for detaljer)
Hjelpeplass: O(N) på grunn av rekursiv stabel.

Finn maksimal dybde eller høyde på et tre ved å bruke Nivå ordregjennomgang :

Gjøre Nivå ordregjennomgang , mens du legger til noder på hvert nivå til Følg trinnene nedenfor for å implementere ideen:

• Traverser treet i nivårekkefølge gjennomgang fra rot .
  • Initialiser en tom kø Q , en variabel dybde og dytte rot , trykk deretter null inn i det Q .
  • Kjør en stund løkke til Q er ikke tom.
    • Lagre frontelementet av Q og Pop ut frontelementet.
    • Hvis forsiden av Q er NULL deretter øke dybde av én og hvis køen ikke er tom, trykk NULL inn i det Q .
    • Ellers hvis elementet ikke er det NULL så sjekk for det venstre og Ikke sant barn og hvis de ikke er det NULL dytte dem inn Q .
• Komme tilbake dybde .

Nedenfor er implementeringen av tilnærmingen ovenfor:

string replaceall java

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->nøkkel = nøkkel;> >temp->venstre = temp->høyre = 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->venstre) {> >q.push(temp->venstre);> >}> >if> (temp->høyre) {> >q.push(temp->høyre);> >}> >}> >// 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->venstre = nyNode(2);> >root->høyre = nyNode(3);> >root->venstre->venstre = nyNode(4);> >root->venstre->høyre = nyNode(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> >

>

>

Produksjon

Height(Depth) of tree is: 3>

Tidskompleksitet: PÅ)
Hjelpeplass: PÅ)

En annen metode for å finne høyde ved hjelp av Nivå ordregjennomgang :

Denne metoden bruker også konseptet Level Order Traversal, men vi vil ikke legge til null i køen. Bare øk disk når nivået øker og skyver barna til gjeldende node inn i køen, fjern deretter alle nodene fra køen til gjeldende nivå.

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->nøkkel = nøkkel;> >temp->venstre = temp->høyre = 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->venstre != NULL) { q.push(temp->venstre); } if (temp->right != NULL) { q.push(temp->right); } } høyde++; } returhøyde; } // Driverprogram int main() { // La oss lage binært tre vist i eksempelet ovenfor Node* root = newNode(1); root->venstre = nyNode(2); root->right = newNode(3); root->venstre->venstre = nyNode(4); root->venstre->høyre = nyNode(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)>

>

>

Produksjon

Height(Depth) of tree is: 3>

Tidskompleksitet: PÅ)
Hjelpeplass: PÅ)