바이너리 수준의 평균 나무 이진 트리에 주어진 문제는 트리의 모든 레벨에있는 모든 노드의 평균을 인쇄합니다.
차례
예
입력:
출력:
{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
이진 트리의 레벨 평균 알고리즘
레벨 순서 순회를 수행하고 트리의 각 레벨에 대해 레벨에있는 모든 노드의 평균을 찾으십시오.
- 큐라는 이름의 큐를 만들어 트리에서 수준 순서를 순회하고 루트 요소를 큐에 푸시합니다.
- 대기열이 비어 있지 않으면 3 ~ 6 단계를 반복합니다.
- 두 변수 합계 및 합계를 0으로 초기화합니다. 여기서 합계는 수준에있는 모든 노드의 합계를 나타내고 합계는 해당 수준에있는 총 노드 수를 나타냅니다. temp라는 다른 대기열을 만듭니다.
- 큐가 비어 있지 않은 동안 하나씩 큐에서 모든 요소를 제거하고 현재 요소의 값을 합계 및 증분 합계에 추가하고 제거 된 노드의 자식을 큐 임시에 추가합니다.
- 평균 현재 수준은 (합계 / 합계)입니다. 그것을 인쇄하십시오.
- 큐 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은 트리의 총 노드 수입니다.
