İkili Ağacdakı Səviyyə Ortalamaları

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Facebook
İkili ağac AğacBaxılıb 83

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

İkili səviyyələrdə orta səviyyələrdə ağac ikili bir ağac verdiyimiz problem, ağacdakı hər səviyyənin bütün qovşaqlarının ortalamalarını yazdırın.

misal

Input:

İkili Ağacdakı Səviyyə OrtalamalarıPin
Çıxış: 
{10.0, 25.0, 45.0, 70.0}
Explanation:
Birinci Səviyyə: Orta = (10) / 1 = 10.0
İkinci Səviyyə: Orta = (20 + 30) / 2 = 25.0
Üçüncü Səviyyə: Orta = (40 + 50) / 2 = 45.0
Dördüncü Səviyyə: Orta = (60 + 70 + 80) = 70.0

İkili ağacdakı səviyyələrin ortalamaları üçün alqoritm

Bir səviyyə düzəlişini edin və ağacın hər səviyyəsi üçün bir səviyyədə bütün qovşaqların ortalamasını tapın.

  1. Ağacda səviyyə sifarişini keçmək üçün növbə adlı bir növbə yaradın, kök elementini növbəyə itələyin.
  2. Növbə boş olmasa da, 3-6 addımları təkrarlayın.
  3. Cəmi bir səviyyədəki bütün qovşaqların cəmini, cəmi isə bu səviyyədəki qovşaqların ümumi sayını təmsil etdiyi 0 və cəmi iki dəyişən başlayın. Temp adlı başqa bir növbə yaradın.
  4. Növbə boş olmasa da, növbədə olan bütün elementləri bir-bir silir, cari elementin dəyərini cəmi və artım cəminə əlavə edir və silinmiş node uşaqlarını növbə tempinə əlavə edir.
  5. Orta cari səviyyə (cəmi / cəmi). Çap et.
  6. Bütün elementləri növbə tempindən növbəyə 'növbə' vəziyyətinə köçürün.

İkili Ağacdakı Səviyyə Ortalamaları üçün İzahat

Ağacı düşün

İkili Ağacdakı Səviyyə OrtalamalarıPin

Step 1

Bir növbə yaradın və kökü ona itələyin.
növbə = 2

Step 2

Sıra boş olmadığı halda, Adım 3-dən 6-a qədər təkrarlayın.

Addım 3 - 6 

Təkrarlama 1
Cəmi və cəmi 0 olaraq başlayın, yəni cəmi = 0 və cəmi = 0
Elementləri 'növbə' sırasından silin, cəmi artırın və cari elementin dəyərini cəmi əlavə edin. Silinmiş elementlərin uşaqlarını növbə tempinə sövq edin.
cəmi = 2, cəmi = 1, temp = 7 -> 11
Bu səviyyənin ortalaması = (2/1) = 2.0
Bütün növbə tempinin elementlərini 'növbə' növbəsinə köçürün.
növbə = 7-> 11

Təkrarlama 2
Cəmi və cəmi 0 olaraq başlayın, yəni cəmi = 0 və cəmi = 0
Elementləri 'növbə' sırasından silin, cəmi artırın və cari elementin dəyərini cəmi əlavə edin. Silinmiş elementlərin uşaqlarını növbə tempinə sövq edin.
cəmi = (7+ 11) = 18, cəmi = 2, temp = 5 -> 9 -> 3
Bu səviyyənin ortalaması = (18/2) = 9.0
Bütün növbə tempinin elementlərini 'növbə' növbəsinə köçürün.
növbə = 5 -> 9 -> 3

Təkrarlama 3
Cəmi və cəmi 0 olaraq başlayın, yəni cəmi = 0 və cəmi = 0
Elementləri 'növbə' sırasından silin, cəmi artırın və cari elementin dəyərini cəmi əlavə edin. Silinmiş elementlərin uşaqlarını növbə tempinə sövq edin.
cəmi = (5 + 9 + 3) = 17, cəmi = 3, temp = sıfır
Bu səviyyənin ortalaması = (17/3) = 6.7
Bütün növbə tempinin elementlərini 'növbə' növbəsinə köçürün.
növbə = boş

Növbəti boşaldıqca burada dayanırıq.

İkili Ağacdakı Səviyyə Ortalamaları üçün JAVA Kodu

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

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

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

    private static void averages(Node root) {
        if (root == null) {
            return;
        }

        // create a queue for level order traversal
        Queue<Node> queue = new LinkedList<>();
        // add root to queue
        queue.add(root);
        
        while (!queue.isEmpty()) {
            // initialize sum and total as 0
            int sum = 0;
            int total = 0;
            // create another queue temp
            Queue<Node> temp = new LinkedList<>();
            while (!queue.isEmpty()) {
                Node curr = queue.poll();
                // add the data of current node to sum
                sum += curr.data;
                // increment total
                total++;
                // add children of curr node to queue temp
                if (curr.left != null) {
                    temp.add(curr.left);
                }
                if (curr.right != null) {
                    temp.add(curr.right);
                }
            }
            
            // average of current level is (sum / total)
            double average = (double) sum / (double) total;
            System.out.format("%.1f ", average);
            
            // move all the elements of queue temp to queue 'queue'
            queue = temp;
        }
        System.out.println();
    }
    
    public static void main(String[] args) {
        // Example tree
        Node root = new Node(10);
        root.left = new Node(20);
        root.right = new Node(30);
        root.right.left = new Node(40);
        root.right.right = new Node(50);
        root.right.left.left = new Node(60);
        root.right.right.left = new Node(70);
        root.right.right.right = new Node(80);

        averages(root);
    }
}
10.0 25.0 45.0 70.0

İkili Ağacdakı Səviyyə Ortalamaları üçün C ++ Kodu

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

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

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

void averages(Node *root) {
    if (root == NULL) {
        return;
    } 
    
    // create a queue for level order traversal
    queue<Node *> q;
    // add root to queue
    q.push(root);
    
    while (!q.empty()) {
        // initialize sum and total as 0
        int sum = 0;
        int total = 0;
        // create another queue temp
        queue<Node *> temp;
        while (!q.empty()) {
            Node *curr = q.front();
            q.pop();
            // add the data of current node to sum
            sum += curr->data;
            // increment total
            total++;
            // add children of curr node to queue temp
            if (curr->left != NULL) {
                temp.push(curr->left);
            }
            if (curr->right != NULL) {
                temp.push(curr->right);
            }
        }
        
        // average of current level is (sum / total)
        double average = (double) sum / (double) total;
        printf("%.1f ", average);
        
        // move all the elements of queue temp to queue q
        q = temp;
    }
    cout<<endl;
}

int main() {
    // Example tree
    Node *root = newNode(10);
    root->left = newNode(20);
    root->right = newNode(30);
    root->right->left = newNode(40);
    root->right->right = newNode(50);
    root->right->left->left = newNode(60);
    root->right->right->left = newNode(70);
    root->right->right->right = newNode(80);
    
    averages(root);
    
    return 0;
}
10.0 25.0 45.0 70.0

Mürəkkəblik təhlili

Zaman Mürəkkəbliyi = O (n)
Kosmik Mürəkkəblik = O (n)
burada n - ağacdakı qovşaqların ümumi sayı

References

Crack Sistemi Dizayn Müsahibələri
Translate »