ಬೈನರಿ ಮರದ ಎತ್ತರವನ್ನು ಕಂಡುಹಿಡಿಯಲು ಪುನರಾವರ್ತಿಸುವ ವಿಧಾನ


ತೊಂದರೆ ಮಟ್ಟ ಮಧ್ಯಮ
ಆಗಾಗ್ಗೆ ಕೇಳಲಾಗುತ್ತದೆ ಅಕೋಲೈಟ್ ಅಡೋಬ್ ಅಮೆಜಾನ್ ಫ್ಯಾನಟಿಕ್ಗಳು ಫೋರ್‌ಕೈಟ್‌ಗಳು ಪಾದಯಾತ್ರೆ ಸ್ನ್ಯಾಪ್ಡಿಯಲ್ ಯಾತ್ರೆ
ಬೈನರಿ ಟ್ರೀ ಕ್ಯೂ ಮರ

ಸಮಸ್ಯೆ ಹೇಳಿಕೆ

“ಬೈನರಿ ಮರದ ಎತ್ತರವನ್ನು ಕಂಡುಹಿಡಿಯಲು ಪುನರಾವರ್ತಿಸುವ ವಿಧಾನ” ಎಂಬ ಸಮಸ್ಯೆ ನಿಮಗೆ ನೀಡಲಾಗಿದೆ ಎಂದು ಹೇಳುತ್ತದೆ ಬೈನರಿ ಮರ, ಪುನರಾವರ್ತಿಸುವ ವಿಧಾನವನ್ನು ಬಳಸಿಕೊಂಡು ಮರದ ಎತ್ತರವನ್ನು ಹುಡುಕಿ.

ಉದಾಹರಣೆಗಳು

ಇನ್ಪುಟ್
ಬೈನರಿ ಮರದ ಎತ್ತರವನ್ನು ಕಂಡುಹಿಡಿಯಲು ಪುನರಾವರ್ತಿಸುವ ವಿಧಾನ

3

ಇನ್ಪುಟ್
ಬೈನರಿ ಮರದ ಎತ್ತರವನ್ನು ಕಂಡುಹಿಡಿಯಲು ಪುನರಾವರ್ತಿಸುವ ವಿಧಾನ

4

ಬೈನರಿ ಮರದ ಎತ್ತರವನ್ನು ಕಂಡುಹಿಡಿಯಲು ಪುನರಾವರ್ತಿಸುವ ವಿಧಾನಕ್ಕಾಗಿ ಅಲ್ಗಾರಿದಮ್

ಮರದ ಎತ್ತರವು ಸಹ ಸಮನಾಗಿರುತ್ತದೆ ಮಟ್ಟಗಳ ಸಂಖ್ಯೆ ಮರದಲ್ಲಿ. ಆದ್ದರಿಂದ ಪುನರಾವರ್ತನೆಯನ್ನು ಬಳಸಿಕೊಂಡು ಎತ್ತರವನ್ನು ಕಂಡುಹಿಡಿಯಲು, a ಮಾಡಿ ಮಟ್ಟದ ಆದೇಶ ಅಡ್ಡಹಾಯುವಿಕೆ ಮರದ ಮತ್ತು ಅದರಲ್ಲಿನ ಮಟ್ಟಗಳ ಸಂಖ್ಯೆಯನ್ನು ಎಣಿಸಿ.

  1. ಒಂದು ರಚಿಸಿ ಕ್ಯೂ ಮತ್ತು ಅದಕ್ಕೆ ಮೂಲವನ್ನು ತಳ್ಳಿರಿ. ಎತ್ತರವನ್ನು 0 ಎಂದು ಪ್ರಾರಂಭಿಸಿ.
  2. ಕ್ಯೂ ಖಾಲಿಯಾಗಿಲ್ಲದಿದ್ದರೂ 3 ಮತ್ತು 4 ಹಂತಗಳನ್ನು ಪುನರಾವರ್ತಿಸಿ.
  3. ಈ ಕ್ಷಣದಲ್ಲಿ ಕ್ಯೂ ಮರದ ಒಂದು ಹಂತವನ್ನು ಹೊಂದಿರುತ್ತದೆ. ಎತ್ತರವನ್ನು 1. ಹೆಚ್ಚಿಸಿ ವೇರಿಯಬಲ್ ಗಾತ್ರವನ್ನು ಕ್ಯೂನ ಗಾತ್ರದಂತೆ ಪ್ರಾರಂಭಿಸಿ.
  4. 1 ರಿಂದ ಗಾತ್ರಕ್ಕೆ ಲೂಪ್ ಅನ್ನು ಚಲಾಯಿಸಿ, ಮತ್ತು ಪ್ರತಿ ಪುನರಾವರ್ತನೆಯಲ್ಲೂ ಕ್ಯೂನಿಂದ ಒಂದು ಅಂಶವನ್ನು ತೆಗೆದುಹಾಕಿ ಮತ್ತು ಅದರ ಮಕ್ಕಳನ್ನು ಸರದಿಗೆ ತಳ್ಳಿರಿ. ಈ ಹಂತವು ಕ್ಯೂನಿಂದ ಒಂದು ಹಂತವನ್ನು ತೆಗೆದುಹಾಕುತ್ತದೆ ಮತ್ತು ಮುಂದಿನ ಹಂತವನ್ನು ಅದಕ್ಕೆ ತಳ್ಳುತ್ತದೆ.
  5. ಹಿಂತಿರುಗಿ ಎತ್ತರ.

ವಿವರಣೆ

ಮೊದಲ ಉದಾಹರಣೆಯಲ್ಲಿ ತೋರಿಸಿರುವ ಮರವನ್ನು ಪರಿಗಣಿಸಿ,

ಹಂತ 1:

ಕ್ಯೂಗೆ ಮೂಲವನ್ನು ಒತ್ತಿ ಮತ್ತು ಎತ್ತರವನ್ನು 0 ಎಂದು ಪ್ರಾರಂಭಿಸಿ, ಅಂದರೆ,
ಕ್ಯೂ = 2, ಎತ್ತರ = 0

ಹಂತ 2:

ಕ್ಯೂ ಖಾಲಿಯಾಗಿರದಿದ್ದಾಗ ಹಂತ 3 ಮತ್ತು 4 ಅನ್ನು ಪುನರಾವರ್ತಿಸಿ.

ಹಂತ 3 ಮತ್ತು 4:

ಪುನರಾವರ್ತನೆ 1:
ಕ್ಯೂ ಮೊದಲ ಹಂತದ ಮರವನ್ನು ಒಳಗೊಂಡಿದೆ.
ಹೆಚ್ಚಳ ಎತ್ತರ, ಆದ್ದರಿಂದ ಎತ್ತರ = 1.
ಕ್ಯೂನ ಎಲ್ಲಾ ಅಂಶಗಳನ್ನು ತೆಗೆದುಹಾಕಿ ಮತ್ತು ಅವರ ಮಕ್ಕಳನ್ನು ಸರದಿಗೆ ಸೇರಿಸಿ.
ಕ್ಯೂ = 7 -> 11

ಪುನರಾವರ್ತನೆ 2:
ಕ್ಯೂ ಮರದ ಎರಡನೇ ಹಂತವನ್ನು ಒಳಗೊಂಡಿದೆ.
ಹೆಚ್ಚಳ ಎತ್ತರ, ಆದ್ದರಿಂದ ಎತ್ತರ = 2.
ಕ್ಯೂನ ಎಲ್ಲಾ ಅಂಶಗಳನ್ನು ತೆಗೆದುಹಾಕಿ ಮತ್ತು ಅವರ ಮಕ್ಕಳನ್ನು ಸರದಿಗೆ ಸೇರಿಸಿ.
ಕ್ಯೂ = 5 -> 9 -> 3

ಪುನರಾವರ್ತನೆ 3:
ಕ್ಯೂ ಮರದ ಮೂರನೇ ಹಂತವನ್ನು ಒಳಗೊಂಡಿದೆ.
ಹೆಚ್ಚಳ ಎತ್ತರ, ಆದ್ದರಿಂದ ಎತ್ತರ = 3.
ಕ್ಯೂನ ಎಲ್ಲಾ ಅಂಶಗಳನ್ನು ತೆಗೆದುಹಾಕಿ ಮತ್ತು ಅವರ ಮಕ್ಕಳನ್ನು ಸರದಿಗೆ ಸೇರಿಸಿ.
ಕ್ಯೂ = ಶೂನ್ಯ

ಕ್ಯೂ ಖಾಲಿಯಾಗುತ್ತಿದ್ದಂತೆ, ನಾವು ಇಲ್ಲಿ ನಿಲ್ಲುತ್ತೇವೆ.

ಹಂತ 5:

ಹಿಂತಿರುಗಿ ಎತ್ತರ, ಆದ್ದರಿಂದ ಮರದ ಎತ್ತರ 3 ಆಗಿದೆ.

ಕೋಡ್

ಬೈನರಿ ಮರದ ಎತ್ತರವನ್ನು ಕಂಡುಹಿಡಿಯಲು ಪುನರಾವರ್ತಿಸುವ ವಿಧಾನಕ್ಕಾಗಿ ಜಾವಾ ಕೋಡ್

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

ಬೈನರಿ ಮರದ ಎತ್ತರವನ್ನು ಕಂಡುಹಿಡಿಯಲು ಪುನರಾವರ್ತಿಸುವ ವಿಧಾನಕ್ಕಾಗಿ ಸಿ ++ ಕೋಡ್

#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 ಎನ್ನುವುದು ಬೈನರಿ ಮರದಲ್ಲಿನ ನೋಡ್‌ಗಳ ಸಂಖ್ಯೆ. ನಾವು ಕ್ಯೂ ಅನ್ನು ಬಳಸಿದ್ದರಿಂದ ಮತ್ತು ಬೈನರಿ ಮರದ ಎಲ್ಲಾ ನೋಡ್‌ಗಳ ಮೇಲೆ ಸಂಚರಿಸಿದ್ದೇವೆ. ಆದ್ದರಿಂದ ಸಮಯದ ಸಂಕೀರ್ಣತೆಯು ರೇಖೀಯವಾಗಿದೆ ಎಂಬುದು ಸ್ಪಷ್ಟವಾಗಿದೆ.

ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆ

ಒ (ಎನ್), ಇಲ್ಲಿ n ಎನ್ನುವುದು ಬೈನರಿ ಟ್ರೀನಲ್ಲಿನ ನೋಡ್ಗಳ ಸಂಖ್ಯೆ. ಎತ್ತರವನ್ನು ಕಂಡುಹಿಡಿಯಲು ನಾವು ಕ್ಯೂ ಅನ್ನು ಬಳಸಿದ್ದೇವೆ ಎಂದು ಈಗಾಗಲೇ ಹೇಳಿದಂತೆ, ನಾವು ಆ ಸರದಿಯಲ್ಲಿರುವ ಅಂಶಗಳನ್ನು ಸಂಗ್ರಹಿಸಿದ್ದೇವೆ. ಹೀಗಾಗಿ ಜಾಗದ ಸಂಕೀರ್ಣತೆಯೂ ರೇಖೀಯವಾಗಿರುತ್ತದೆ.

ಉಲ್ಲೇಖಗಳು