Vzhľadom na binárny strom je úlohou nájsť výšku stromu. Výška stromu je počet vrcholov v strome od koreňa po najhlbší uzol.

Poznámka: Výška prázdneho stromu je 0 a výška stromu s jedným uzlom je 1 .

Príklad binárneho stromu

Rekurzívne vypočítajte výšku vľavo a správny podstromy uzla a priraďte výšku uzlu ako maximálna výška dvoch detí plus 1 . Podrobnosti nájdete v pseudokóde a programe nižšie.

Ilustrácia:

Zvážte nasledujúci strom:

Príklad stromu

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

stiahnite si video z youtube pomocou vlc

pretože rekurzívne
maxDepth(‘2‘) = max (maxDepth(‘4‘), maxDepth(‘5‘)) + 1 = 1 + 1 a (keďže výška ‚4‘ aj ‚5‘ je 1)
maxDepth('3') = 1

Pri implementácii nápadu postupujte podľa nasledujúcich krokov:

• Rekurzívne vykonajte hĺbkové vyhľadávanie.
• Ak je strom prázdny, vráťte 0
• V opačnom prípade postupujte nasledovne
  • Získajte maximálnu hĺbku ľavého podstromu rekurzívne, t. j. zavolajte maxDepth( strom->ľavý-podstrom)
  • Získajte maximálnu hĺbku pravého podstromu rekurzívne, t. j. zavolajte maxDepth( strom->pravý-podstrom)
  • Získajte maximálnu maximálnu hĺbku vľavo a správny podstromy a pridať 1 k nemu pre aktuálny uzol.
    • 
• Vráti maximálnu_hĺbku.

Nižšie je uvedená implementácia vyššie uvedeného prístupu:

C++

>

>

C

>

>

Java

>

>

Python3

>

>

C#

>

>

Javascript

>

>

Height of tree is 3>

Časová zložitosť: O(N) (Pozrite si príspevok na Prechádzanie stromom pre podrobnosti)
Pomocný priestor: O(N) kvôli rekurzívnemu zásobníku.

Nájdite maximálnu hĺbku alebo výšku stromu pomocou Prechádzanie objednávky úrovne :

Do Prechádzanie objednávky úrovne , pričom pridávate uzly na každej úrovni do Pri implementácii nápadu postupujte podľa nasledujúcich krokov:

• Prechádzajte stromom v poradí úrovne, začínajúc od koreň .
  • Inicializujte prázdny front Q , premenná hĺbka a tlačiť koreň , potom zatlačte nulový do Q .
  • Spustite chvíľu cyklu, kým Q nie je prázdny.
    • Uložte predný prvok z Q a Vysuňte predný prvok.
    • Ak je predná časť Q je NULOVÝ potom zvýšiť hĺbka o jeden a ak fronta nie je prázdna, stlačte NULOVÝ do Q .
    • V opačnom prípade, ak prvok nie je NULOVÝ potom skontrolujte jeho vľavo a správny deti a ak nie sú NULOVÝ zatlačte ich do Q .
• Návrat hĺbka .

Nižšie je uvedená implementácia vyššie uvedeného prístupu:

podčiarknuť v značke

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->kľúč = kľúč;> >temp->vľavo = teplota->vpravo = 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->vľavo) {> >q.push(temp->vľavo);> >}> >if> (temp->vpravo) {> >q.push(temp->vpravo);> >}> >}> >// 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->vpravo = newNode(3);> >root->left->left = newNode(4);> >root->left->right = 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> >

>

>

Výkon

Height(Depth) of tree is: 3>

Časová zložitosť: O(N)
Pomocný priestor: O(N)

Ďalšia metóda na zistenie výšky pomocou Prechádzanie objednávky úrovne :

Táto metóda tiež používa koncept prechodu objednávky na úrovni, ale do fronty nebudeme pridávať hodnotu null. Jednoducho zvýšte počítadlo keď sa úroveň zvýši a zatlačí deti aktuálneho uzla do frontu, potom odstráňte všetky uzly z frontu aktuálnej úrovne.

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->kľúč = kľúč;> >temp->vľavo = teplota->vpravo = 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->vľavo != NULL) { q.push(temp->left); } if (temp->vpravo != NULL) { q.push(temp->vpravo); } } vyska++; } výška návratu; } // Program ovládača int main() { // Vytvorme binárny strom zobrazený v príklade vyššie 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)>

>

>

Výkon

Height(Depth) of tree is: 3>

Časová zložitosť: O(N)
Pomocný priestor: O(N)