در این مطلب، روش نوشتن برنامه محاسبه حداکثر عمق درخت مورد بررسی قرار گرفته است. فرض می‌شود که یک درخت دودویی داده شده و هدف پیدا کردن حداکثر عمق آن است. ارتفاع درخت خالی صفر (۰) و ارتفاع درختی که در تصویر زیر آمده، برابر با ۳ است.

با استفاده از روش بازگشتی، می‌توان ارتفاع زیردرخت سمت چپ و راست یک گره را محاسبه کرد و ارتفاع را به عنوان حداکثر ارتفاع دو فرزند به علاوه یک، به گره تخصیص دارد. شرح دقیق‌تر این روش، در ادامه بیان شده است.

الگوریتم محاسبه حداکثر عمق درخت

()maxDepth

1. اگر درخت خالی است، صفر را بازگردان.
2. در غیر این صورت
   1. حداکثر عمق زیر درخت سمت چپ را به صورت بازگشتی حساب کن. یعنی، (maxDepth( tree->left-subtree را فراخوانی کن.
   2. حداکثر عمق زیر درخت سمت راست را به صورت بازگشتی حساب کن. یعنی (maxDepth( tree->right-subtree را فراخوانی کن.
   3. حداکثر مقدار حداکثر عمق زیردرخت‌های راست و چپ را بازگردان و ۱ واحد به آن برای گره کنونی اضافه کن. یعنی max_depth = max(max dept of left subtree, max depth of right subtree) + 1
   4. max_depth را بازگردان.

برای شفافیت بیشتر پیرامون چگونگی اجرای تابع بازگشتی ()maxDepth در درخت بالا، نمودار زیر قابل توجه است.

برنامه محاسبه حداکثر عمق درخت در ++C

// C++ program to find height of tree 
#include <bits/stdc++.h> 
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->left);  
        int rDepth = maxDepth(node->right);  
      
        /* 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->left = NULL;  
    Node->right = NULL;  
      
    return(Node);  
}  
      
// Driver code     
int main()  
{  
    node *root = newNode(1);  
  
    root->left = newNode(2);  
    root->right = newNode(3);  
    root->left->left = newNode(4);  
    root->left->right = newNode(5);  
      
    cout << "Height of tree is " << maxDepth(root);  
    return 0;  
}  
  
// This code is contributed by rathbhupendra

برنامه محاسبه حداکثر عمق درخت در C

#include<stdio.h> 
#include<stdlib.h> 
  
  
/* 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->left); 
       int rDepth = maxDepth(node->right); 
  
       /* 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->left = NULL; 
    node->right = NULL; 
    
    return(node); 
} 
    
int main() 
{ 
    struct node *root = newNode(1); 
  
    root->left = newNode(2); 
    root->right = newNode(3); 
    root->left->left = newNode(4); 
    root->left->right = newNode(5);  
    
    printf("Height of tree is %d", maxDepth(root)); 
    
    getchar(); 
    return 0; 
}

برنامه محاسبه حداکثر عمق درخت در جاوا

// 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 Mayank Jaiswal(mayank_24)

برنامه محاسبه حداکثر عمق درخت در پایتون ۳

# 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 Nikhil Kumar Singh(nickzuck_007)

برنامه محاسبه حداکثر عمق درخت در #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 29AjayKumar

خروجی

خروجی قطعه کدهای به صورت زیر است.

Height of tree is 3

پیچیدگی زمانی این روش از درجه (O(n است.

اگر نوشته بالا برای شما مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

• مجموعه آموزش‌‌های برنامه‌‌‌نویسی
• آموزش برنامه‌نویسی C++‎
• مجموعه آموزش‌های ریاضیات
• یافتن دور همیلتونی با الگوریتم پس گرد — به زبان ساده
• برنامه تشخیص وجود دور در گراف جهت دار — راهنمای کاربردی
• برنامه بررسی وجود دور در گراف بدون جهت — راهنمای کاربردی
• حل مساله n وزیر با الگوریتم پس‌گرد (Backtracking) — به زبان ساده

 

منبع [+]