Dado un árbol binario no vacío, imprima el valor promedio de los Nodes en cada nivel.
Ejemplos:
C++
// C++ program to find averages of all levels
// in a binary tree.
#include <bits/stdc++.h>
using namespace std;
/* A binary tree node has data, pointer to
left child and a pointer to right child */
struct Node {
int val;
struct Node* left, *right;
};
/* Function to print the average value of the
nodes on each level */
void averageOfLevels(Node* root)
{
vector<float> res;
// Traversing level by level
queue<Node*> q;
q.push(root);
while (!q.empty()) {
// Compute sum of nodes and
// count of nodes in current
// level.
int sum = 0, count = 0;
queue<Node*> temp;
while (!q.empty()) {
Node* n = q.front();
q.pop();
sum += n->val;
count++;
if (n->left != NULL)
temp.push(n->left);
if (n->right != NULL)
temp.push(n->right);
}
q = temp;
cout << (sum * 1.0 / count) << " ";
}
}
/* Helper function that allocates a
new node with the given data and
NULL left and right pointers. */
Node* newNode(int data)
{
Node* temp = new Node;
temp->val = data;
temp->left = temp->right = NULL;
return temp;
}
// Driver code
int main()
{
/* Let us construct a Binary Tree
4
/ \
2 9
/ \ \
3 5 7 */
Node* root = NULL;
root = newNode(4);
root->left = newNode(2);
root->right = newNode(9);
root->left->left = newNode(3);
root->left->right = newNode(8);
root->right->right = newNode(7);
averageOfLevels(root);
return 0;
}
Java
// Java program to find averages of all levels
// in a binary tree.
import java.util.*;
class GfG {
/* A binary tree node has data, pointer to
left child and a pointer to right child */
static class Node {
int val;
Node left, right;
}
/* Function to print the average value of the
nodes on each level */
static void averageOfLevels(Node root)
{
//vector<float> res;
// Traversing level by level
Queue<Node> q = new LinkedList<Node> ();
q.add(root);
int sum = 0, count = 0;
while (!q.isEmpty()) {
// Compute sum of nodes and
// count of nodes in current
// level.
sum = 0;
count = 0;
Queue<Node> temp = new LinkedList<Node> ();
while (!q.isEmpty()) {
Node n = q.peek();
q.remove();
sum += n.val;
count++;
if (n.left != null)
temp.add(n.left);
if (n.right != null)
temp.add(n.right);
}
q = temp;
System.out.print((sum * 1.0 / count) + " ");
}
}
/* Helper function that allocates a
new node with the given data and
NULL left and right pointers. */
static Node newNode(int data)
{
Node temp = new Node();
temp.val = data;
temp.left = null;
temp.right = null;
return temp;
}
// Driver code
public static void main(String[] args)
{
/* Let us construct a Binary Tree
4
/ \
2 9
/ \ \
3 5 7 */
Node root = null;
root = newNode(4);
root.left = newNode(2);
root.right = newNode(9);
root.left.left = newNode(3);
root.left.right = newNode(5);
root.right.right = newNode(7);
System.out.println("Averages of levels : ");
System.out.print("[");
averageOfLevels(root);
System.out.println("]");
}
}
Python3
# Python3 program to find averages of # all levels in a binary tree. # Importing Queue from queue import Queue # Helper class that allocates a # new node with the given data and # None left and right pointers. class newNode: def __init__(self, data): self.val = data self.left = self.right = None # Function to print the average value # of the nodes on each level def averageOfLevels(root): # Traversing level by level q = Queue() q.put(root) while (not q.empty()): # Compute Sum of nodes and # count of nodes in current # level. Sum = 0 count = 0 temp = Queue() while (not q.empty()): n = q.queue[0] q.get() Sum += n.val count += 1 if (n.left != None): temp.put(n.left) if (n.right != None): temp.put(n.right) q = temp print((Sum * 1.0 / count), end = " ") # Driver code if __name__ == '__main__': # Let us construct a Binary Tree # 4 # / \ # 2 9 # / \ \ # 3 5 7 root = None root = newNode(4) root.left = newNode(2) root.right = newNode(9) root.left.left = newNode(3) root.left.right = newNode(8) root.right.right = newNode(7) averageOfLevels(root) # This code is contributed by PranchalK
C#
// C# program to find averages of all levels
// in a binary tree.
using System;
using System.Collections.Generic;
class GfG
{
/* A binary tree node has data, pointer to
left child and a pointer to right child */
class Node
{
public int val;
public Node left, right;
}
/* Function to print the average value of the
nodes on each level */
static void averageOfLevels(Node root)
{
//vector<float> res;
// Traversing level by level
Queue<Node> q = new Queue<Node> ();
q.Enqueue(root);
int sum = 0, count = 0;
while ((q.Count!=0))
{
// Compute sum of nodes and
// count of nodes in current
// level.
sum = 0;
count = 0;
Queue<Node> temp = new Queue<Node> ();
while (q.Count != 0)
{
Node n = q.Peek();
q.Dequeue();
sum += n.val;
count++;
if (n.left != null)
temp.Enqueue(n.left);
if (n.right != null)
temp.Enqueue(n.right);
}
q = temp;
Console.Write((sum * 1.0 / count) + " ");
}
}
/* Helper function that allocates a
new node with the given data and
NULL left and right pointers. */
static Node newNode(int data)
{
Node temp = new Node();
temp.val = data;
temp.left = null;
temp.right = null;
return temp;
}
// Driver code
public static void Main(String[] args)
{
/* Let us construct a Binary Tree
4
/ \
2 9
/ \ \
3 5 7 */
Node root = null;
root = newNode(4);
root.left = newNode(2);
root.right = newNode(9);
root.left.left = newNode(3);
root.left.right = newNode(5);
root.right.right = newNode(7);
Console.WriteLine("Averages of levels : ");
Console.Write("[");
averageOfLevels(root);
Console.WriteLine("]");
}
}
// This code has been contributed by
// 29AjayKumar
Javascript
<script>
// Javascript program to find averages of
// all levels in a binary tree.
class Node
{
constructor(data)
{
this.left = null;
this.right = null;
this.val = data;
}
}
// Function to print the average value
// of the nodes on each level
function averageOfLevels(root)
{
// Traversing level by level
let q = [];
q.push(root);
let sum = 0, count = 0;
while (q.length > 0)
{
// Compute sum of nodes and
// count of nodes in current
// level.
sum = 0;
count = 0;
let temp = [];
while (q.length > 0)
{
let n = q[0];
q.shift();
sum += n.val;
count++;
if (n.left != null)
temp.push(n.left);
if (n.right != null)
temp.push(n.right);
}
q = temp;
document.write((sum * 1.0 / count) + " ");
}
}
// Helper function that allocates a
// new node with the given data and
// NULL left and right pointers.
function newNode(data)
{
let temp = new Node(data);
return temp;
}
// Driver code
/* Let us construct a Binary Tree
4
/ \
2 9
/ \ \
3 5 7 */
let root = null;
root = newNode(4);
root.left = newNode(2);
root.right = newNode(9);
root.left.left = newNode(3);
root.left.right = newNode(5);
root.right.right = newNode(7);
document.write("Averages of levels : " + "</br>");
document.write("[");
averageOfLevels(root);
document.write("]" + "</br>");
// This code is contributed by divyeshrabadiya07
</script>
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA