Итеративен метод за наоѓање на висината на бинарното дрво


Ниво на тешкотија Медиум
Често прашувано во Аколит Adobe Амазон Фанатици Фуркити Крстоносните Snapdeal Yatra
Бинарно дрво редот Дрво

Изјава за проблем

Проблемот „Итеративен метод за наоѓање на висината на бинарното дрво“ наведува дека ви е даден а бинарно дрво, пронајдете ја висината на дрвото користејќи итеративен метод.

Примери

Внесете
Итеративен метод за наоѓање на висината на бинарното дрво

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

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 е бројот на јазли во бинарното стебло. Како што веќе беше кажано дека користевме редица за да ја пронајдеме висината, ги зачувавме елементите во таа редица. Така, вселенската комплексност е исто така линеарна.

Референци