Givet ett binärt träd är uppgiften att hitta höjden på trädet. Trädets höjd är antalet hörn i trädet från roten till den djupaste noden.
Notera: Höjden på ett tomt träd är 0 och höjden på ett träd med en enda nod är 1 .
Exempel på binärt träd
Rekommenderad övning Höjd på binärt träd Prova det!Beräkna rekursivt höjden på vänster och den höger underträd till en nod och tilldela noden höjd som max längd av två barn plus 1 . Se nedan pseudokoden och programmet för detaljer.
Illustration:
Tänk på följande träd:
Exempel på träd
maxDepth(‘1’) = max(maxDepth(‘2’), maxDepth(‘3’)) + 1 = 2 + 1
eftersom rekursivt
maxDepth('2') = max (maxDepth('4'), maxDepth('5')) + 1 = 1 + 1 och (eftersom höjden på både '4' och '5' är 1)
maxDepth('3') = 1
Följ stegen nedan för att implementera idén:
- Gör rekursivt en djup-först-sökning.
- Om trädet är tomt, returnera 0
- Annars gör du följande
- Få maxdjupet för det vänstra underträdet rekursivt, dvs anrop maxDepth(träd->vänster-underträd)
- Få maxdjupet för det högra underträdet rekursivt, d.v.s. anrop maxDepth (träd->höger-underträd)
- Få max max djup av vänster och höger underträd och lägg till 1 till den för den aktuella noden.
-
- Retur max_depth.
Nedan är implementeringen av ovanstående tillvägagångssätt:
C++
// C++ program to find height of tree> #include> using> namespace> std;> /* A binary tree node has data, pointer to left child> and a pointer to right child */> class> node {> public>:> >int> data;> >node* left;> >node* right;> };> /* Compute the 'maxDepth' of a tree -- the number of> >nodes along the longest path from the root node> >down to the farthest leaf node.*/> int> maxDepth(node* node)> {> >if> (node == NULL)> >return> 0;> >else> {> >/* compute the depth of each subtree */> >int> lDepth = maxDepth(node->vänster);> >int> rDepth = maxDepth(node->höger);> >/* use the larger one */> >if> (lDepth>rDepth)> >return> (lDepth + 1);> >else> >return> (rDepth + 1);> >}> }> /* Helper function that allocates a new node with the> given data and NULL left and right pointers. */> node* newNode(>int> data)> {> >node* Node =>new> node();> >Node->data = data;> >Node->vänster = NULL;> >Node->höger = NULL;> >return> (Node);> }> // Driver code> int> main()> {> >node* root = newNode(1);> >root->vänster = newNode(2);> >root->höger = newNode(3);> >root->vänster->vänster = newNode(4);> >root->vänster->höger = newNode(5);> >cout <<>'Height of tree is '> << maxDepth(root);> >return> 0;> }> // This code is contributed by Amit Srivastav> |
>
>
C
#include> #include> /* A binary tree node has data, pointer to left child> >and a pointer to right child */> struct> node {> >int> data;> >struct> node* left;> >struct> node* right;> };> /* Compute the 'maxDepth' of a tree -- the number of> >nodes along the longest path from the root node> >down to the farthest leaf node.*/> int> maxDepth(>struct> node* node)> {> >if> (node == NULL)> >return> 0;> >else> {> >/* compute the depth of each subtree */> >int> lDepth = maxDepth(node->vänster);> >int> rDepth = maxDepth(node->höger);> >/* use the larger one */> >if> (lDepth>rDepth)> >return> (lDepth + 1);> >else> >return> (rDepth + 1);> >}> }> /* Helper function that allocates a new node with the> >given data and NULL left and right pointers. */> struct> node* newNode(>int> data)> {> >struct> node* node> >= (>struct> node*)>malloc>(>sizeof>(>struct> node));> >node->data = data;> >node->vänster = NULL;> >node->höger = NULL;> >return> (node);> }> int> main()> {> >struct> node* root = newNode(1);> >root->vänster = newNode(2);> >root->höger = newNode(3);> >root->vänster->vänster = newNode(4);> >root->vänster->höger = newNode(5);> >printf>(>'Height of tree is %d'>, maxDepth(root));> >getchar>();> >return> 0;> }> |
>
>
Java
// Java program to find height of tree> // A binary tree node> class> Node {> >int> data;> >Node left, right;> >Node(>int> item)> >{> >data = item;> >left = right =>null>;> >}> }> class> BinaryTree {> >Node root;> >/* Compute the 'maxDepth' of a tree -- the number of> >nodes along the longest path from the root node> >down to the farthest leaf node.*/> >int> maxDepth(Node node)> >{> >if> (node ==>null>)> >return> 0>;> >else> {> >/* compute the depth of each subtree */> >int> lDepth = maxDepth(node.left);> >int> rDepth = maxDepth(node.right);> >/* use the larger one */> >if> (lDepth>rDepth)> >return> (lDepth +>1>);> >else> >return> (rDepth +>1>);> >}> >}> >/* Driver program to test above functions */> >public> static> void> main(String[] args)> >{> >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>);> >System.out.println(>'Height of tree is '> >+ tree.maxDepth(tree.root));> >}> }> // This code has been contributed by Amit Srivastav> |
>
>
Python3
# Python3 program to find the maximum depth of tree> # A binary tree node> class> Node:> ># Constructor to create a new node> >def> __init__(>self>, data):> >self>.data>=> data> >self>.left>=> None> >self>.right>=> None> # Compute the 'maxDepth' of a tree -- the number of nodes> # along the longest path from the root node down to the> # farthest leaf node> def> maxDepth(node):> >if> node>is> None>:> >return> 0> >else>:> ># Compute the depth of each subtree> >lDepth>=> maxDepth(node.left)> >rDepth>=> maxDepth(node.right)> ># Use the larger one> >if> (lDepth>rDepth):> >return> lDepth>+>1> >else>:> >return> rDepth>+>1> # Driver program to test above function> root>=> Node(>1>)> root.left>=> Node(>2>)> root.right>=> Node(>3>)> root.left.left>=> Node(>4>)> root.left.right>=> Node(>5>)> print>(>'Height of tree is %d'> %> (maxDepth(root)))> # This code is contributed by Amit Srivastav> |
>
>
C#
// C# program to find height of tree> using> System;> // A binary tree node> public> class> Node {> >public> int> data;> >public> Node left, right;> >public> Node(>int> item)> >{> >data = item;> >left = right =>null>;> >}> }> public> class> BinaryTree {> >Node root;> >/* Compute the 'maxDepth' of a tree -- the number of> >nodes along the longest path from the root node> >down to the farthest leaf node.*/> >int> maxDepth(Node node)> >{> >if> (node ==>null>)> >return> 0;> >else> {> >/* compute the depth of each subtree */> >int> lDepth = maxDepth(node.left);> >int> rDepth = maxDepth(node.right);> >/* use the larger one */> >if> (lDepth>rDepth)> >return> (lDepth + 1);> >else> >return> (rDepth + 1);> >}> >}> >/* Driver code */> >public> static> void> Main(String[] args)> >{> >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 of tree is '> >+ tree.maxDepth(tree.root));> >}> }> // This code has been contributed by> // Correction done by Amit Srivastav> |
>
>
Javascript
> // JavaScript program to find height of tree> // A binary tree node> class Node> {> >constructor(item)> >{> >this>.data=item;> >this>.left=>this>.right=>null>;> >}> }> >let root;> > >/* Compute the 'maxDepth' of a tree -- the number of> >nodes along the longest path from the root node> >down to the farthest leaf node.*/> >function> maxDepth(node)> >{> >if> (node ==>null>)> >return> 0;> >else> >{> >/* compute the depth of each subtree */> >let lDepth = maxDepth(node.left);> >let rDepth = maxDepth(node.right);> > >/* use the larger one */> >if> (lDepth>rDepth)> >return> (lDepth + 1);> >else> >return> (rDepth + 1);> >}> >}> > >/* Driver program to test above functions */> > >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);> > >document.write(>'Height of tree is : '> +> >maxDepth(root));> // This code is contributed by rag2127> //Correction done by Amit Srivastav> > |
>
>
Produktion
Height of tree is 3>
Tidskomplexitet: O(N) (Se inlägget på Tree Traversal för detaljer)
Hjälputrymme: O(N) på grund av rekursiv stack.
Hitta maximalt djup eller höjd för ett träd med hjälp av Nivå Order Traversal :
Do Nivå Order Traversal , samtidigt som du lägger till noder på varje nivå till Följ stegen nedan för att implementera idén:
- Traversera trädet i nivåordning med början från rot .
- Initiera en tom kö F , en variabel djup och tryck rot , tryck sedan null in i F .
- Kör en stund loop till F är inte tom.
- Förvara det främre elementet av F och skjut ut frontelementet.
- Om framsidan av F är NULL öka sedan djup en och om kön inte är tom tryck på NULL in i F .
- Annars om elementet inte är det NULL kolla sedan efter det vänster och höger barn och om de inte är det NULL tryck in dem F .
- Lämna tillbaka djup .
Nedan är implementeringen av ovanstående tillvägagångssätt:
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->nyckel = nyckel;>>temp->vänster = temp->höger = 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änster) {>>q.push(temp->vänster);>>}>>if>(temp->höger) {>>q.push(temp->höger);>>}>>}>>// 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->vänster = newNode(2);>>root->höger = newNode(3);>>root->vänster->vänster = newNode(4);>>root->vänster->höger = 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>>>>
ProduktionHeight(Depth) of tree is: 3>Tidskomplexitet: PÅ)
Hjälputrymme: PÅ)En annan metod för att hitta höjd med hjälp av Nivå Order Traversal :
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->nyckel = nyckel;>>temp->vänster = temp->höger = 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änster != NULL) { q.push(temp->vänster); } if (temp->right != NULL) { q.push(temp->right); } } höjd++; } returhöjd; } // Drivrutinsprogram int main() { // Låt oss skapa binärt träd som visas i ovanstående exempel Node* root = newNode(1); root->left = newNode(2); root->right = newNode(3); root->vänster->vänster = newNode(4); root->vänster->höger = 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)>>>
ProduktionHeight(Depth) of tree is: 3>Tidskomplexitet: PÅ)
Hjälputrymme: PÅ)