د بائنري ونې لوړوالی موندلو لپاره د کارولو میتود


مشکل کچه منځني
په مکرر ډول دننه پوښتل کیږي اکولایټ ایڈوب ترلاسه کړئ Amazon انځورونه څلورکیټونه هیک سنیپډیل یاترا
دوهم ونې په ليکه کې ونې

ستونزه بیان

ستونزه "د بائنري ونې لوړوالی موندلو Iterative میتود" وايي چې تاسو ته a دوه لمبر ونه، د تکراري میتود په کارولو سره د ونې اوږدوالی ومومئ.

مثالونه

ننوتۍ
د بائنري ونې لوړوالی موندلو لپاره د کارولو میتود

3

ننوتۍ
د بائنري ونې لوړوالی موندلو لپاره د کارولو میتود

4

د بائنري ونې لوړوالی موندلو لپاره د Iterative میتود لپاره الګوریتم

د یوې ونې اوږدوالی هم مساوي دی د کچې کچه په ونه کې نو د تکرار په کارولو سره د لوړوالی موندلو لپاره ، یو کړئ د کچې آرډر د ونې او په هغې کې د کچې شمیرنه.

  1. جوړ کړئ په ليکه کې او ریښی دې ته فشار ورکړی. د 0 په څیر لوړوالی پیل کړئ.
  2. پداسې حال کې چې قطار د 3 او 4 ګامونو تکرار خالي ندی.
  3. پدې شیبه کې کتار د ونې یوه کچه لري. د 1. لخوا د لوړوالی لوړوالی د قطار اندازه کولو په څیر د اندازې بدلون پیل کړئ.
  4. له 1 څخه تر اندازې پورې یوه لوپ چل کړئ ، او په هر تکرار کې یو عنصر له قطار څخه لرې کړئ او خپل ماشومان قطار ته واچوئ. دا ګام به له قطار څخه یوه کچه لرې کړي او راتلونکي کچه به دې ته فشار ورکړي.
  5. بېرته راګرځول.

تشریح

هغه ونې په پام کې ونیسئ چې په لومړي مثال کې ښودل شوي ،

1 پړاو:

قطار ته کښینږئ او لوړوالی یې د 0 په توګه پیل کړئ ، دا دی ،
قطار = 2 ، قد = 0

2 پړاو:

3 او 4 مرحله تکرار کړئ پداسې حال کې چې قطار خالي ندی.

3 او Step مرحله:

لومړۍ برخه:
کتار کې د ونې لومړۍ کچه شتون لري.
لوړوالی لوړوالی ، نو قد = 1.
د قطار ټول عناصر لرې کړئ او خپل ماشومان په قطار کې شامل کړئ.
قطار = 7 -> 11

لومړۍ برخه:
کتار د ونې دوهمه کچه لري.
لوړوالی لوړوالی ، نو قد = 2.
د قطار ټول عناصر لرې کړئ او خپل ماشومان په قطار کې شامل کړئ.
قطار = 5 -> 9 -> 3

لومړۍ برخه:
کتار د ونې دریمه کچه لري.
لوړوالی لوړوالی ، نو قد = 3.
د قطار ټول عناصر لرې کړئ او خپل ماشومان په قطار کې شامل کړئ.
کتار = خالي

لکه څنګه چې قطار خالي کیږي ، نو موږ دلته ودروو.

5 پړاو:

بیرته راستنېدل ، نو د ونې قد 3 دی.

کوډ

د بائنري ونې لوړوالی موندلو لپاره د 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

د بائنري ونې لوړوالی موندلو لپاره د Iterative میتود لپاره C ++ کوډ

#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 په بائنري ونې کې د نوډونو شمیر دی. له هغه وخته چې موږ قطار وراضافه کړی او د بائنري ونې په ټولو نوډونو کې مو تیر کړی دی. نو دا روښانه ده چې د وخت پیچلتیا لاهم ده.

د ځای پیچلتیا

O (n) ، چیرې چې n په بائنری ونې کې د نوډونو شمیر دی. لکه څنګه چې دمخه مو وویل چې موږ د لوړوالي موندلو لپاره کتار کارولۍ ، موږ په دې کتار کې عناصر خوندي کړي وو. پدې توګه د ځای پیچلتیا هم خطي ده.

ماخذونه