बाइनरी रूखको उचाई पत्ता लगाउन Iterative विधि


कठिनाई तह मध्यम
बारम्बार सोधिन्छ समग्र एडोब अमेजन कट्टरपन्थी फोरकाइट्स हाइड स्नैपडल यता
बाइनरी रूख लाम ट्री

समस्या वक्तव्य

समस्या "बाइनरी ट्रीको उचाई पत्ता लगाउनको लागि Iterative तरीका" बताउँछ कि तपाईंलाई a बाइनरी रूख, पुनरावृत्ति विधि प्रयोग गरेर रूखको उचाई पत्ता लगाउनुहोस्।

उदाहरण

आगत
बाइनरी रूखको उचाई पत्ता लगाउन Iterative विधि

3

आगत
बाइनरी रूखको उचाई पत्ता लगाउन Iterative विधि

4

बाइनरी ट्रीको उचाई पत्ता लगाउन Iterative विधिको लागि एल्गोरिथ्म

रूखको उचाई पनि बराबर छ स्तरको संख्या रूखमा। त्यसैले पुनरावृत्ति प्रयोग गरेर उचाई पत्ता लगाउन, गर्नुहोस् स्तर अर्डर ट्राभर्सल रूखको र यसमा स्तरहरूको संख्या गणना गर्नुहोस्।

  1. एक सिर्जना गर्नुहोस् लाम र जरा यसलाई धक्का। ० को रूपमा उचाइ सुरु गर्नुहोस्।
  2. जबकि पue्क्ति खाली दोहोर्याउने चरणहरू 3 र not खाली छैन।
  3. यस क्षणमा लामले रूखको एक स्तर समावेश गर्दछ। १. द्वारा उचाइ वृद्धि गर्नुहोस्। लामको आकारको रूपमा एक चर आकार सुरु गर्नुहोस्।
  4. १ देखि आकारमा लूप चलाउनुहोस्, र प्रत्येक पुनरावृत्तिमा लामबाट तत्व हटाउनुहोस् र यसका बच्चाहरूलाई लाममा धक्का दिनुहोस्। यस चरणले लामबाट एक स्तर हटाउनेछ र अर्को चरणलाई यसमा धक्का दिन्छ।
  5. उचाई फिर्ता।

स्पष्टीकरण

पहिलो उदाहरणमा देखाइएको रूखलाई विचार गर्नुहोस्,

चरण 1:

प root्क्तिलाई पue्क्तिमा थिच्नुहोस् र उचाइ ० को रूपमा आरम्भ गर्नुहोस्, जुन हो।
पue्क्ति = २, उचाई = ०

चरण 2:

चरण and र Rep दोहोर्याउनुहोस् जबकि पue्क्ति खाली छैन।

चरण and र::

Iteration १:
लाममा रूखको पहिलो स्तर हुन्छ।
वृद्धि उचाइ, त्यसैले उचाई = १।
लामका सबै तत्व हटाउनुहोस् र उनीहरूका बच्चाहरूलाई लाममा थप गर्नुहोस्।
पue्क्ति = - -> ११

Iteration १:
पue्क्तिले रूखको दोस्रो स्तर समावेश गर्दछ।
वृद्धि उचाइ, त्यसैले उचाई = १।
लामका सबै तत्व हटाउनुहोस् र उनीहरूका बच्चाहरूलाई लाममा थप गर्नुहोस्।
पue्क्ति = - -> - ->।

Iteration १:
पue्क्तिले रूखको तेस्रो तह समावेश गर्दछ।
वृद्धि उचाइ, त्यसैले उचाई = १।
लामका सबै तत्व हटाउनुहोस् र उनीहरूका बच्चाहरूलाई लाममा थप गर्नुहोस्।
पue्क्ति = शून्य

प the्क्ति खाली भएपछि, हामी यहाँ रोकिन्छौं।

चरण 5:

उचाई फर्काउनुहोस्, त्यसैले रूखको उचाई is छ।

कोड

बाइनरी ट्रीको उचाई पत्ता लगाउन Iterative विधिको लागि जाभा कोड

import java.util.LinkedList;
import java.util.Queue;

class IterativeMethodToFindHeightOfBinaryTree {
    // class representing node of a binary tree
    static class Node {
        int data;
        Node left, right;

        public Node(int data) {
            this.data = data;
        }
    }

    private static int height(Node root) {
        if (root == null) {
            return 0;
        }

        // create a queue and push root to it
        Queue<Node> q = new LinkedList<>();
        q.add(root);
        // initialise height as 0
        int height = 0;

        // do a level order traversal
        // while queue is not empty
        while (!q.isEmpty()) {
            // increment height
            height++;
            // initialise size as size of queue
            int size = q.size();
            // Remove current level from queue and push next level
            for (int i = 0; i < size; i++) {
                // remove an element from queue
                Node curr = q.poll();
                // push current element's children to the queue
                if (curr.left != null)
                    q.add(curr.left);
                if (curr.right != null)
                    q.add(curr.right);
            }
        }
        
        // return height
        return height;
    }

    public static void main(String[] args) {
        // Example Tree 1
        Node root1 = new Node(2);
        root1.left = new Node(7);
        root1.right = new Node(11);
        root1.left.left = new Node(5);
        root1.right.left = new Node(9);
        root1.right.right = new Node(3);

        System.out.println(height(root1));

        // Example Tree 2
        Node root2 = new Node(1);
        root2.left = new Node(2);
        root2.right = new Node(3);
        root2.left.left = new Node(4);
        root2.left.right = new Node(5);
        root2.right.right = new Node(6);
        root2.left.left.left = new Node(7);
        root2.left.left.right = new Node(8);
        root2.right.right.left = new Node(9);
        root2.right.right.right = new Node(10);

        System.out.println(height(root2));
    }
}
3
4

C ++ बाइनरी ट्रीको उचाई पत्ता लगाउन Iterative विधिको लागि कोड

#include <bits/stdc++.h>
using namespace std;

// class representing node of a binary tree
class Node {
    public:
    int data;
    Node *left;     
    Node *right;
    
    Node(int d) {
        data = d;
        left = right = NULL;
    }
};

// function to create a new node with data d
Node* newNode(int d) {
    Node *node = new Node(d);
    return node;
}

int height(Node *root) {
    if (root == NULL) {
        return 0;
    }
    
    // create a queue and push root to it
    queue<Node*> q;
    q.push(root);
    // initialise height as 0
    int height = 0;
    
    // do a level order traversal
    // while queue is not empty
    while (!q.empty()) {
        // increment height
        height++;
        // initialise size as size of queue
        int size = q.size();
        // Remove current level from queue and push next level
        for (int i = 0; i < size; i++) {
            // remove an element from queue
            Node *curr = q.front();
            // push current element's children to the queue
            q.pop();
            if (curr->left != NULL)
                q.push(curr->left);
            if (curr->right != NULL)
                q.push(curr->right);
        }
    }
    
    // return height
    return height;
}

int main() {
    // Example Tree 1
    Node *root1 = newNode(2);
    root1->left = newNode(7);
    root1->right = newNode(11);
    root1->left->left = newNode(5);
    root1->right->left = newNode(9);
    root1->right->right = newNode(3);

    cout<<height(root1)<<endl;

    // Example Tree 2
    Node *root2 = newNode(1);
    root2->left = newNode(2);
    root2->right = newNode(3);
    root2->left->left = newNode(4);
    root2->left->right = newNode(5);
    root2->right->right = newNode(6);
    root2->left->left->left = newNode(7);
    root2->left->left->right = newNode(8);
    root2->right->right->left = newNode(9);
    root2->right->right->right = newNode(10);

    cout<<height(root2)<<endl;
    
    return 0;
}
3
4

जटिलता विश्लेषण

समय जटिलता

ऊ)जहाँ n बाइनरी रूखमा नोडहरूको संख्या हो। किनकि हामीले एक प used्क्ति प्रयोग गरिसकेका छौं र बाइनरी रूखमा सबै नोडहरू माथि यात्रा गरेका छौं। त्यसोभए यो स्पष्ट छ कि समयको जटिलता रैखिक हो।

ठाउँ जटिलता

O (n), जहाँ n बाइनरी रूखमा नोडहरूको संख्या हो। पहिले नै भनिएको छ कि हामीले उचाई पत्ता लगाउन कतार प्रयोग गर्यौं, हामीले त्यस लाममा एलिमेन्टहरू भण्डार गरेका थियौं। यसैले स्पेस जटिलता पनि रैखिक छ।

सन्दर्भ