이진 트리의 레벨 평균


난이도 쉽게
자주 묻는 질문 페이스북 서비스
이진 트리 나무

바이너리 수준의 평균 나무 이진 트리에 주어진 문제는 트리의 모든 레벨에있는 모든 노드의 평균을 인쇄합니다.

입력:

이진 트리의 레벨 평균
출력: 
{10.0, 25.0, 45.0, 70.0}
설명 :
첫 번째 수준 : 평균 = (10) / 1 = 10.0
두 번째 레벨 : 평균 = (20 + 30) / 2 = 25.0
세 번째 수준 : 평균 = (40 + 50) / 2 = 45.0
네 번째 수준 : 평균 = (60 + 70 + 80) = 70.0

이진 트리의 레벨 평균 알고리즘

레벨 순서 순회를 수행하고 트리의 각 레벨에 대해 레벨에있는 모든 노드의 평균을 찾으십시오.

  1. 큐라는 이름의 큐를 만들어 트리에서 수준 순서를 순회하고 루트 요소를 큐에 푸시합니다.
  2. 대기열이 비어 있지 않으면 3 ~ 6 단계를 반복합니다.
  3. 두 변수 합계 및 합계를 0으로 초기화합니다. 여기서 합계는 수준에있는 모든 노드의 합계를 나타내고 합계는 해당 수준에있는 총 노드 수를 나타냅니다. temp라는 다른 대기열을 만듭니다.
  4. 큐가 비어 있지 않은 동안 하나씩 큐에서 모든 요소를 ​​제거하고 현재 요소의 값을 합계 및 증분 합계에 추가하고 제거 된 노드의 자식을 큐 임시에 추가합니다.
  5. 평균 현재 수준은 (합계 / 합계)입니다. 그것을 인쇄하십시오.
  6. 큐 temp에서 큐 'queue'로 모든 요소를 ​​전송합니다.

이진 트리의 레벨 평균에 대한 설명

나무를 고려하십시오.

이진 트리의 레벨 평균

단계 1

큐를 만들고 루트를 푸시합니다.
대기열 = 2

단계 2

대기열이 비어 있지 않은 상태에서 3 ~ 6 단계를 반복합니다.

3 ~ 6 단계 

반복 1
합계와 합계를 0, 즉 합계 = 0 및 합계 = 0으로 초기화합니다.
큐 'queue'에서 요소를 제거하고 합계를 증가시키고 현재 요소의 값을 합계에 추가합니다. 또한 제거 된 요소의 하위 항목을 임시 대기열로 푸시합니다.
합계 = 2, 합계 = 1, 온도 = 7-> 11
이 수준의 평균 = (2/1) = 2.0
큐 temp의 모든 요소를 ​​큐 'queue'로 전송합니다.
대기열 = 7-> 11

반복 2
합계와 합계를 0, 즉 합계 = 0 및 합계 = 0으로 초기화합니다.
큐 'queue'에서 요소를 제거하고 합계를 증가시키고 현재 요소의 값을 합계에 추가합니다. 또한 제거 된 요소의 하위 항목을 임시 대기열로 푸시합니다.
합계 = (7+ 11) = 18, 합계 = 2, 온도 = 5-> 9-> 3
이 수준의 평균 = (18/2) = 9.0
큐 temp의 모든 요소를 ​​큐 'queue'로 전송합니다.
대기열 = 5-> 9-> 3

반복 3
합계와 합계를 0, 즉 합계 = 0 및 합계 = 0으로 초기화합니다.
큐 'queue'에서 요소를 제거하고 합계를 증가시키고 현재 요소의 값을 합계에 추가합니다. 또한 제거 된 요소의 하위 항목을 임시 대기열로 푸시합니다.
합계 = (5 + 9 + 3) = 17, 합계 = 3, 임시 = null
이 수준의 평균 = (17/3) = 6.7
큐 temp의 모든 요소를 ​​큐 'queue'로 전송합니다.
대기열 = null

대기열이 null이되면 여기서 중지합니다.

이진 트리의 레벨 평균을위한 JAVA 코드

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

이진 트리의 평균 수준에 대한 C ++ 코드

#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

복잡성 분석

시간 복잡성 = O (N)
공간 복잡성 = O (N)
여기서 n은 트리의 총 노드 수입니다.

참조