Dado un árbol binario, encuentre su densidad haciendo un recorrido.
Density of Binary Tree = Size / Height
Ejemplos:
C++
//C++ program to find density of a binary tree
#include<bits/stdc++.h>
// A binary tree node
struct Node
{
int data;
Node *left, *right;
};
// Helper function to allocates a new node
Node* newNode(int data)
{
Node* node = new Node;
node->data = data;
node->left = node->right = NULL;
return node;
}
// Function to compute height and
// size of a binary tree
int heighAndSize(Node* node, int &size)
{
if (node==NULL)
return 0;
// compute height of each subtree
int l = heighAndSize(node->left, size);
int r = heighAndSize(node->right, size);
//increase size by 1
size++;
//return larger of the two
return (l > r) ? l + 1 : r + 1;
}
//function to calculate density of a binary tree
float density(Node* root)
{
if (root == NULL)
return 0;
int size = 0; // To store size
// Finds height and size
int _height = heighAndSize(root, size);
return (float)size/_height;
}
// Driver code to test above methods
int main()
{
Node* root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
printf("Density of given binary tree is %f",
density(root));
return 0;
}
Java
// Java program to find density of Binary Tree
// A binary tree node
class Node
{
int data;
Node left, right;
public Node(int data)
{
this.data = data;
left = right = null;
}
}
// Class to implement pass by reference of size
class Size
{
// variable to calculate size of tree
int size = 0;
}
class BinaryTree
{
Node root;
// Function to compute height and
// size of a binary tree
int heighAndSize(Node node, Size size)
{
if (node == null)
return 0;
// compute height of each subtree
int l = heighAndSize(node.left, size);
int r = heighAndSize(node.right, size);
//increase size by 1
size.size++;
//return larger of the two
return (l > r) ? l + 1 : r + 1;
}
//function to calculate density of a binary tree
float density(Node root)
{
Size size = new Size();
if (root == null)
return 0;
// Finds height and size
int _height = heighAndSize(root, size);
return (float) size.size / _height;
}
// Driver code to test above methods
public static void main(String[] args)
{
BinaryTree tree = new BinaryTree();
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
System.out.println("Density of given Binary Tree is : "
+ tree.density(tree.root));
}
}
// This code has been contributed by Mayank Jaiswal(mayank_24)
Python3
# Python3 program to find density
# of a binary tree
# A binary tree node
# Helper function to allocates a new node
class newNode:
def __init__(self, data):
self.data = data
self.left = self.right = None
# Function to compute height and
# size of a binary tree
def heighAndSize(node, size):
if (node == None) :
return 0
# compute height of each subtree
l = heighAndSize(node.left, size)
r = heighAndSize(node.right, size)
#increase size by 1
size[0] += 1
# return larger of the two
return l + 1 if(l > r) else r + 1
# function to calculate density
# of a binary tree
def density(root):
if (root == None) :
return 0
size = [0] # To store size
# Finds height and size
_height = heighAndSize(root, size)
return size[0] / _height
# Driver Code
if __name__ == '__main__':
root = newNode(1)
root.left = newNode(2)
root.right = newNode(3)
print("Density of given binary tree is ",
density(root))
# This code is contributed
# by SHUBHAMSINGH10
C#
// C# program to find density
// of Binary Tree
using System;
// A binary tree node
class Node
{
public int data;
public Node left, right;
public Node(int data)
{
this.data = data;
left = right = null;
}
}
// Class to implement pass
// by reference of size
class Size
{
// variable to calculate
// size of tree
public int size = 0;
}
class BinaryTree
{
Node root;
// Function to compute height
// and size of a binary tree
int heighAndSize(Node node,
Size size)
{
if (node == null)
return 0;
// compute height of each subtree
int l = heighAndSize(node.left, size);
int r = heighAndSize(node.right, size);
//increase size by 1
size.size++;
//return larger of the two
return (l > r) ? l + 1 : r + 1;
}
// function to calculate density
// of a binary tree
float density(Node root)
{
Size size = new Size();
if (root == null)
return 0;
// Finds height and size
int _height = heighAndSize(root, size);
return (float) size.size / _height;
}
// Driver code
static public void Main(String []args)
{
BinaryTree tree = new BinaryTree();
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
Console.WriteLine("Density of given " +
"Binary Tree is : " +
tree.density(tree.root));
}
}
// This code is contributed
// by Arnab Kundu
Javascript
<script>
// javascript program to find density
// of Binary Tree
// A binary tree node
class Node
{
constructor(data)
{
this.data = data;
this.left = null;
this.right = null;
}
}
// Class to implement pass
// by reference of size
class Size
{
constructor()
{
// variable to calculate
// size of tree
this.size = 0;
}
}
var root = null;
// Function to compute height
// and size of a binary tree
function heighAndSize(node, size)
{
if (node == null)
return 0;
// compute height of each subtree
var l = heighAndSize(node.left, size);
var r = heighAndSize(node.right, size);
//increase size by 1
size.size++;
//return larger of the two
return (l > r) ? l + 1 : r + 1;
}
// function to calculate density
// of a binary tree
function density(root)
{
var size = new Size();
if (root == null)
return 0;
// Finds height and size
var _height = heighAndSize(root, size);
return size.size / _height;
}
// Driver code
root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
document.write("Density of given " +
"Binary Tree is : " +
density(root));
// This code is contributed by itsok.
</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