Коэффициент дальности в двоичном дереве

Опубликовано: 5 Января, 2022

Для данного двоичного дерева задача состоит в том, чтобы найти в нем коэффициент диапазона .
Диапазон определяется как разница между максимальным и минимальным значением в наборе данных, а коэффициент диапазона является относительной мерой разброса диапазона. Предположим, что максимальное значение в наборе данных - maxVal, а минимальное значение - minVal, тогда коэффициент диапазона может быть определен как:

Coefficient of range = (maxVal – minVal)/(maxVal + minVal)

Рассмотрим двоичное дерево ниже:

Например , максимальное значение в приведенном выше двоичном дереве равно 9, а минимальное - 1, поэтому коэффициент диапазона равен ((9 - 1) / (9 + 1)) = 0,8.

Подход: в двоичном дереве поиска мы можем найти максимум, перемещаясь по правым указателям, пока не дойдем до крайнего правого узла. Но в двоичном дереве мы должны посетить каждый узел, чтобы вычислить максимум. Итак, идея состоит в том, чтобы пройти по заданному дереву и для каждого узла вернуть максимум 3 значения.

Данные узла.
Максимум в левом поддереве узла.
Максимум в правом поддереве узла.

Аналогичным образом найдите минимальное значение в двоичном дереве и вычислите коэффициент диапазона.
Ниже представлена реализация описанного выше подхода:

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( data) float
 {
    struct Node* node = ( struct Node*)
        malloc ( sizeof ( struct Node));
    node->data = data;
    node->left = node->right = NULL;
    return (node);
 }
 // 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 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( data) float
 {
    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
 {
    data; public float
    public Node left, right;
 };
 // A utility function to create a new node
 static Node newNode( data) float
 {
    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>

Выход:

 Коэффициент дальности 0,833333

Сложность по времени: O (n), где n - количество узлов.

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.

Technical Scripter Структуры данных

Коэффициент дальности в двоичном дереве

C ++

Джава

Python3

C #

Javascript

РЕКОМЕНДУЕМЫЕ СТАТЬИ