Dado un Árbol Binario, la tarea es encontrar el Coeficiente de Rango en él.
El rango se define como la diferencia entre el valor máximo y mínimo en un conjunto de datos y el coeficiente de rango es la medida relativa de la dispersión del rango. Supongamos que el valor máximo en un conjunto de datos es maxVal y el valor mínimo es minVal , entonces el coeficiente de rango se puede definir como:
Coeficiente de rango = (maxVal – minVal)/(maxVal + minVal)
Considere el siguiente árbol binario:
Por ejemplo , el máximo en el árbol binario anterior es 9 y el mínimo es 1, por lo que el coeficiente de rango es ((9 – 1)/(9 + 1)) = 0,8.
Enfoque: en el árbol de búsqueda binaria , podemos encontrar el máximo al atravesar los punteros hacia la derecha hasta llegar al Node más a la derecha. Pero en Binary Tree , debemos visitar cada Node para calcular el máximo. Entonces, la idea es atravesar el árbol dado y para cada Node devolver un máximo de 3 valores.
- Datos del Node.
- Máximo en el subárbol izquierdo del Node.
- Máximo en el subárbol derecho del Node.
De manera similar, encuentre el valor mínimo en el árbol binario y calcule el coeficiente de rango.
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP program to find Coefficient of
// Range in a Binary Tree
#include <bits/stdc++.h>
using namespace std;
// A tree node
struct Node {
float data;
struct Node *left, *right;
};
// A utility function to create a new node
struct Node* newNode(float data)
{
struct Node* newnode = new Node();
newnode->data = data;
newnode->left = newnode->right = NULL;
return (newnode);
}
// Returns maximum value in a given Binary Tree
float findMax(struct Node* root)
{
// Base case
if (root == NULL)
return INT_MIN;
// Return maximum of 3 values:
// 1) Root's data 2) Max in Left Subtree
// 3) Max in right subtree
float res = root->data;
float lres = findMax(root->left);
float rres = findMax(root->right);
if (lres > res)
res = lres;
if (rres > res)
res = rres;
return res;
}
// Returns minimum value in a given Binary Tree
float findMin(struct Node* root)
{
// Base case
if (root == NULL)
return INT_MAX;
// Return minimum of 3 values:
// 1) Root's data 2) Min in Left Subtree
// 3) Min in right subtree
float res = root->data;
float lres = findMin(root->left);
float rres = findMin(root->right);
if (lres < res)
res = lres;
if (rres < res)
res = rres;
return res;
}
// Function to find the value of the Coefficient
// of range in the Binary Tree
float coefRange(Node* root)
{
float max = findMax(root);
float min = findMin(root);
return (max - min) / (max + min);
}
// Driver Code
int main(void)
{
// Construct the Binary Tree
struct Node* root = newNode(2);
root->left = newNode(7);
root->right = newNode(5);
root->left->right = newNode(6);
root->left->right->left = newNode(1);
root->left->right->right = newNode(11);
root->right->right = newNode(9);
root->right->right->left = newNode(4);
cout << "Coefficient of Range is " << coefRange(root);
return 0;
}
Java
// JAVA program to find Coefficient of
// Range in a Binary Tree
class GFG
{
// A tree node
static class Node
{
float data;
Node left, right;
};
// A utility function to create a new node
static Node newNode(float data)
{
Node node = new Node();
node.data = data;
node.left = node.right = null;
return (node);
}
// Returns maximum value in a given Binary Tree
static float findMax(Node root)
{
// Base case
if (root == null)
return Integer.MIN_VALUE;
// Return maximum of 3 values:
// 1) Root's data 2) Max in Left Subtree
// 3) Max in right subtree
float res = root.data;
float lres = findMax(root.left);
float rres = findMax(root.right);
if (lres > res)
res = lres;
if (rres > res)
res = rres;
return res;
}
// Returns minimum value in a given Binary Tree
static float findMin(Node root)
{
// Base case
if (root == null)
return Integer.MAX_VALUE;
// Return minimum of 3 values:
// 1) Root's data 2) Min in Left Subtree
// 3) Min in right subtree
float res = root.data;
float lres = findMin(root.left);
float rres = findMin(root.right);
if (lres < res)
res = lres;
if (rres < res)
res = rres;
return res;
}
// Function to find the value of the Coefficient
// of range in the Binary Tree
static float coefRange(Node root)
{
float max = findMax(root);
float min = findMin(root);
return (max - min) / (max + min);
}
// Driver Code
public static void main(String[] args)
{
// Construct the Binary Tree
Node root = newNode(2);
root.left = newNode(7);
root.right = newNode(5);
root.left.right = newNode(6);
root.left.right.left = newNode(1);
root.left.right.right = newNode(11);
root.right.right = newNode(9);
root.right.right.left = newNode(4);
System.out.print("Coefficient of Range is " + coefRange(root));
}
}
// This code is contributed by PrinciRaj1992
Python3
# Python3 program to find Coefficient of
# Range in a Binary Tree
from sys import maxsize
INT_MIN = -maxsize
INT_MAX = maxsize
# A tree node
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
# Returns maximum value in a given Binary Tree
def findMax(root: Node) -> float:
# Base case
if root is None:
return INT_MIN
# Return maximum of 3 values:
# 1) Root's data 2) Max in Left Subtree
# 3) Max in right subtree
res = root.data
lres = findMax(root.left)
rres = findMax(root.right)
if lres > res:
res = lres
if rres > res:
res = rres
return res
# Returns minimum value in a given Binary Tree
def findMin(root: Node) -> float:
# Base case
if root is None:
return INT_MAX
# Return minimum of 3 values:
# 1) Root's data 2) Min in Left Subtree
# 3) Min in right subtree
res = root.data
lres = findMin(root.left)
rres = findMin(root.right)
if lres < res:
res = lres
if rres < res:
res = rres
return res
# Function to find the value of the Coefficient
# of range in the Binary Tree
def coefRange(root: Node) -> float:
maxx = findMax(root)
minn = findMin(root)
return (maxx - minn) / (maxx + minn)
# Driver Code
if __name__ == "__main__":
# Construct the Binary Tree
root = Node(2)
root.left = Node(7)
root.right = Node(5)
root.left.right = Node(6)
root.left.right.left = Node(1)
root.left.right.right = Node(11)
root.right.right = Node(9)
root.right.right.left = Node(4)
print("Coefficient of Range is", coefRange(root))
# This code is contributed by
# sanjeev2552
C#
// C# program to find Coefficient of
// Range in a Binary Tree
using System;
class GFG
{
// A tree node
class Node
{
public float data;
public Node left, right;
};
// A utility function to create a new node
static Node newNode(float data)
{
Node node = new Node();
node.data = data;
node.left = node.right = null;
return (node);
}
// Returns maximum value in a given Binary Tree
static float findMax(Node root)
{
// Base case
if (root == null)
return int.MinValue;
// Return maximum of 3 values:
// 1) Root's data 2) Max in Left Subtree
// 3) Max in right subtree
float res = root.data;
float lres = findMax(root.left);
float rres = findMax(root.right);
if (lres > res)
res = lres;
if (rres > res)
res = rres;
return res;
}
// Returns minimum value in a given Binary Tree
static float findMin(Node root)
{
// Base case
if (root == null)
return int.MaxValue;
// Return minimum of 3 values:
// 1) Root's data 2) Min in Left Subtree
// 3) Min in right subtree
float res = root.data;
float lres = findMin(root.left);
float rres = findMin(root.right);
if (lres < res)
res = lres;
if (rres < res)
res = rres;
return res;
}
// Function to find the value of the Coefficient
// of range in the Binary Tree
static float coefRange(Node root)
{
float max = findMax(root);
float min = findMin(root);
return (max - min) / (max + min);
}
// Driver Code
public static void Main(String[] args)
{
// Construct the Binary Tree
Node root = newNode(2);
root.left = newNode(7);
root.right = newNode(5);
root.left.right = newNode(6);
root.left.right.left = newNode(1);
root.left.right.right = newNode(11);
root.right.right = newNode(9);
root.right.right.left = newNode(4);
Console.Write("Coefficient of Range is " +
coefRange(root));
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// javascript program to find Coefficient of
// Range in a Binary Tree
// A tree node
class Node {
constructor(val) {
this.data = val;
this.left = null;
this.right = null;
}
}
// A utility function to create a new node
function newNode(data) {
var node = new Node();
node.data = data;
node.left = node.right = null;
return (node);
}
// Returns maximum value in a given Binary Tree
function findMax(root) {
// Base case
if (root == null)
return Number.MIN_VALUE;
// Return maximum of 3 values:
// 1) Root's data 2) Max in Left Subtree
// 3) Max in right subtree
var res = root.data;
var lres = findMax(root.left);
var rres = findMax(root.right);
if (lres > res)
res = lres;
if (rres > res)
res = rres;
return res;
}
// Returns minimum value in a given Binary Tree
function findMin(root) {
// Base case
if (root == null)
return Number.MAX_VALUE;
// Return minimum of 3 values:
// 1) Root's data 2) Min in Left Subtree
// 3) Min in right subtree
var res = root.data;
var lres = findMin(root.left);
var rres = findMin(root.right);
if (lres < res)
res = lres;
if (rres < res)
res = rres;
return res;
}
// Function to find the value of the Coefficient
// of range in the Binary Tree
function coefRange(root) {
var max = findMax(root);
var min = findMin(root);
return (max - min) / (max + min);
}
// Driver Code
// Construct the Binary Tree
var root = newNode(2);
root.left = newNode(7);
root.right = newNode(5);
root.left.right = newNode(6);
root.left.right.left = newNode(1);
root.left.right.right = newNode(11);
root.right.right = newNode(9);
root.right.right.left = newNode(4);
document.write("Coefficient of Range is " + coefRange(root).toFixed(6));
// This code contributed by umadevi9616
</script>
Producción:
Coefficient of Range is 0.833333
Complejidad temporal: O(n) donde n es el número de Nodes. Espacio Auxiliar : O(n)
Publicación traducida automáticamente
Artículo escrito por VishalBachchas y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA