Μέγιστο βάθος δυαδικού δέντρου


Επίπεδο δυσκολίας Εύκολος
Συχνές ερωτήσεις αμαζόνα Cadence Ινδία Κουπόνι Ντούνια Γεγονότα Χωρίς χρέωση MakeMyTrip Μονοτυπικές Λύσεις Snapdeal Synopsys Τερατάτα 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.

Σε δυαδική δομή δεδομένων δέντρων, έχουμε αριστερούς και δεξί κόμβους, οι οποίοι στη συνέχεια έχουν αριστερά και δεξιά σώματα. Έτσι, δημιουργώντας μια δομή δεδομένων που μοιάζει με δέντρο. Σε ένα δυαδικό δέντρο, οι κόμβοι συνδέονται για τη δημιουργία υποδένδρων. Έτσι, ορίζουμε κάποια ορολογία για τη δομή δεδομένων δυαδικών δέντρων. Και ένα από αυτά είναι το μέγιστο βάθος, το οποίο ορίζεται ως το μέγιστο ύψος του δέντρου, η απόσταση από τη ρίζα έως το φύλλο. Ένα φύλλο δεν είναι παρά ένας κόμβος που δεν έχει ούτε τον αριστερό ή τον δεξιό κόμβο.

Για την εύρεση του μέγιστου βάθους υπολογίζουμε το βάθος του αριστερού και του δεξιού υποδέντρου. Το βάθος του τρέχοντος δέντρου ισούται με το μέγιστο αριστερό και δεξιό υπόστρωμα +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

Ανάλυση πολυπλοκότητας

Χρόνος πολυπλοκότητας

ΕΠΙ) όπου n είναι ο αριθμός των κόμβων δεδομένων που έχουν εισαχθεί στο δεδομένο δυαδικό δέντρο.

Διαστημική πολυπλοκότητα

Ο (1) γιατί χρησιμοποιήσαμε σταθερό επιπλέον χώρο.

αναφορές