ორობითი ხის მაქსიმალური სიღრმე


Რთული ტური Easy
ხშირად ეკითხებიან Amazon კადენს ინდოეთი კუპონი დუნია ფაქტები უფასო დატენვა MakeMyTrip მონოტიპის გადაწყვეტილებები Snapdeal ანოტაცია Teradata VMware Zoho
სიღრმისეული პირველი ძებნა ხე ხის გადაკვეთა

პრობლემის განცხადება

”ორობითი ხის მაქსიმალური სიღრმის” პრობლემა აღნიშნავს, რომ გეძლევათ ორობითი ხის მონაცემთა სტრუქტურა. დაბეჭდეთ მოცემული მაქსიმალური სიღრმე ორობითი ხე.

მაგალითი

შეყვანის

ორობითი ხის მაქსიმალური სიღრმე

2

განმარტება: მოცემული ხისთვის მაქსიმალური სიღრმეა 2. რადგან ფესვის ქვემოთ მხოლოდ ერთი ელემენტია (ანუ ფესვის დონემდე უფრო დიდი სიღრმეზე = 1) როგორც მარცხენა, ისე მარჯვენა ქვევრში.

შეყვანის

ორობითი ხის მაქსიმალური სიღრმე

3

განმარტება: არსებობს ორი ელემენტი დონეზე = 3, მარჯვენა ქვეჯგუფში. ამრიგად მაქსიმალური სიღრმე = 3.

ორობითი ხის მაქსიმალური სიღრმის ალგორითმი

1. Initialize a binary tree data structure.
2. Create a class node with a variable of integer type and the two-node type pointers left and right as it's private members.
3. Create a function newNode to create a new node of the binary tree which accepts a variable of integer type consisting of data as it's a parameter.
4. After that, initialize a new node inside it. Store the integer variable given as a parameter in the data of the node of the binary tree and update the value of it's left and the right pointer is null.
5. Return the newly created node.
6. Similarly, create a function to find the maximum depth of the binary tree which accepts a node pointer as it's a parameter.
7. Check if the node is equal to null, return 0.
8. Else create a variable left of integer type representing the depth of the left subtree. Make a recursive call to the function itself with the left of the node as it's a parameter and store the result returned in the variable left.
9. Similarly, create a variable right of integer type representing the depth of the right subtree. Make a recursive call to the function itself with the right of the node as it's a parameter and store the result returned in the variable right.
10. After that, check if the depth of the left subtree is greater than the depth of the right subtree return the depth of the left subtree + 1.
11. Else return the variable right i.e. the depth of the right subtree + 1.

In ორობითი ხის მონაცემთა სტრუქტურა, ჩვენ გვაქვს მარცხენა და მარჯვენა კვანძები, რომლებსაც შემდეგ თავად აქვთ მარცხენა და მარჯვენა ბოძები. ამრიგად, ხის მსგავსი მონაცემების სტრუქტურა ხდება. ორობით ხეში კვანძები უკავშირდება ქვეძლების წარმოებას. ამრიგად, ჩვენ განვსაზღვრავთ ორობითი ხის მონაცემთა სტრუქტურის გარკვეულ ტერმინოლოგიას. და ერთი მათგანია მაქსიმალური სიღრმე, რომელიც განისაზღვრება, როგორც ხის მაქსიმალური სიმაღლე ფესვიდან ფოთოლამდე. ფოთოლი სხვა არაფერია, თუ არა კვანძი, რომელსაც არ აქვს არც მარცხენა და არც მარჯვენა კვანძი.

მაქსიმალური სიღრმის დასადგენად გამოვთვლით მარცხენა და მარჯვენა ქვეტყის სიღრმეს. ამჟამინდელი ხის სიღრმე უდრის მარცხენა და მარჯვენა ქვეტყის +1 მაქსიმუმს. ამრიგად, ჩვენ ვიყენებთ რეკურსიულ მიდგომას მარცხენა და მარჯვენა ქვეტყის სიღრმის დასადგენად. რადგან ჩვენ ვიყენებთ რეკურსიას, უნდა გვქონდეს რამდენიმე ძირითადი შემთხვევა. აქ ძირითადი შემთხვევაა, თუ ჩვენ იმ კვანძთან ვართ, რომელიც ფოთოლია. ფოთლის კვანძს აქვს სიგრძე = 1.

კოდი

C ++ პროგრამა ორობითი ხის მაქსიმალური სიღრმის დასადგენად

#include <bits/stdc++.h> 
using namespace std; 
  
class node{  
    public: 
        int data;  
        node* left;  
        node* right;  
};  
  
int maxDepth(node* node){  
    if(node == NULL)  
        return 0;  
    else{  
        int left = maxDepth(node->left);  
        int right = maxDepth(node->right);  
      
        if(left > right)  
            return(left + 1);  
        else return(right + 1);  
    }  
}  
  
node* newNode(int data){  
    node* Node = new node(); 
    Node->data = data;  
    Node->left = NULL;  
    Node->right = NULL;  
      
    return(Node);  
}  
      
int main(){  
    node *root = newNode(2);  
  
    root->left = newNode(3);  
    root->right = newNode(8);  
    root->left->left = newNode(6);  
    root->left->right = newNode(9);  
      
    cout<<maxDepth(root);  
    return 0;  
}
3

Java პროგრამა ორობითი ხის მაქსიმალური სიღრმის მოსაძებნად

class Node{ 
    int data; 
    Node left, right; 
   
    Node(int item){ 
        data = item; 
        left = right = null; 
    } 
} 
   
class BinaryTree{ 
     Node root; 
   
    int maxDepth(Node node){ 
        if(node == null) 
            return 0; 
        else{ 
            int left = maxDepth(node.left); 
            int right = maxDepth(node.right); 
   
            if(left > right) 
                return (left + 1); 
             else 
                return (right + 1); 
        } 
    } 
       
    public static void main(String[] args){ 
        BinaryTree tree = new BinaryTree(); 
   
        tree.root = new Node(2); 
        tree.root.left = new Node(3); 
        tree.root.right = new Node(8); 
        tree.root.left.left = new Node(6); 
        tree.root.left.right = new Node(9); 
   
        System.out.println(tree.maxDepth(tree.root)); 
    } 
}
3

სირთულის ანალიზი

დროის სირთულე

O (N) სადაც n არის მოცემული ორობითი ხეში ჩასმული მონაცემთა კვანძების რაოდენობა.

სივრცის სირთულე

O (1) რადგან მუდმივი დამატებითი სივრცე გამოვიყენეთ.

ლიტერატურა