ബൈനറി ട്രീയുടെ ഉയരം കണ്ടെത്തുന്നതിനുള്ള ആവർത്തന രീതി


വൈഷമ്യ നില മീഡിയം
പതിവായി ചോദിക്കുന്നു അക്കോലൈറ്റ് അഡോബി ആമസോൺ ഫനാറ്റിക്സ് ഫോർകൈറ്റുകൾ ഉയർത്തൽ സ്നാപ്ഡേൽ യാത്ര
ബൈനറി ട്രീ വരി വൃക്ഷം

പ്രശ്നം പ്രസ്താവന

“ബൈനറി ട്രീയുടെ ഉയരം കണ്ടെത്തുന്നതിനുള്ള ആവർത്തന രീതി” എന്ന പ്രശ്നം നിങ്ങൾക്ക് ഒരു നൽകിയിട്ടുണ്ടെന്ന് പറയുന്നു ബൈനറി ട്രീ, ആവർത്തന രീതി ഉപയോഗിച്ച് മരത്തിന്റെ ഉയരം കണ്ടെത്തുക.

ഉദാഹരണങ്ങൾ

ഇൻപുട്ട്
ബൈനറി ട്രീയുടെ ഉയരം കണ്ടെത്തുന്നതിനുള്ള ആവർത്തന രീതി

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

സങ്കീർണ്ണത വിശകലനം

സമയ സങ്കീർണ്ണത

O (n), ഇവിടെ n എന്നത് ബൈനറി ട്രീയിലെ നോഡുകളുടെ എണ്ണമാണ്. ഞങ്ങൾ ഒരു ക്യൂ ഉപയോഗിക്കുകയും ബൈനറി ട്രീയിലെ എല്ലാ നോഡുകളിലൂടെയും സഞ്ചരിക്കുകയും ചെയ്തതിനാൽ. അതിനാൽ സമയ സങ്കീർണ്ണത രേഖീയമാണെന്ന് വ്യക്തമാണ്.

ബഹിരാകാശ സങ്കീർണ്ണത

O (n), ഇവിടെ n എന്നത് ബൈനറി ട്രീയിലെ നോഡുകളുടെ എണ്ണം. ഉയരം കണ്ടെത്താൻ ഞങ്ങൾ ഒരു ക്യൂ ഉപയോഗിച്ചുവെന്ന് ഇതിനകം പറഞ്ഞതുപോലെ, ഞങ്ങൾ ആ ക്യൂവിലെ ഘടകങ്ങൾ സൂക്ഷിച്ചു. അങ്ങനെ സ്ഥല സങ്കീർണ്ണതയും രേഖീയമാണ്.

അവലംബം