Рубрики

Плотность бинарного дерева в одном обходе

По заданному бинарному дереву найдите его плотность, выполнив один обход.

Density of Binary Tree = Size / Height 

Примеры:

Input: Root of following tree
   10
  /   \
 20   30

Output: 1.5
Height of given tree = 2
Size of given tree = 3

Input: Root of following tree
     10
    /   
   20   
 /
30
Output: 1
Height of given tree = 3
Size of given tree = 3 

Плотность бинарного дерева указывает, насколько сбалансировано бинарное дерево. Например, плотность перекошенного дерева минимальна, а плотность идеального дерева максимальна.

Мы настоятельно рекомендуем вам свернуть браузер и попробовать это в первую очередь.

Два подхода, основанного на обходе, очень просты. Сначала найдите высоту, используя один обход, затем найдите размер, используя другой обход. Наконец, верните соотношение двух значений.
Чтобы сделать это за один проход, мы вычисляем размер двоичного дерева, находя его высоту. Ниже приведена реализация C ++.

C ++

// C ++ программа для определения плотности двоичного дерева
#include<stdio.h>
#include<stdlib.h>

  
// Узел двоичного дерева

struct Node

{

    int data;

    Node *left, *right;

};

  
// Вспомогательная функция для выделения нового узла

Node* newNode(int data)

{

    Node* node = new Node;

    node->data = data;

    node->left = node->right = NULL;

    return node;

}

  
// Функция для вычисления высоты и
// размер двоичного дерева

int heighAndSize(Node* node, int &size)

{

    if (node==NULL)

        return 0;

  

    // вычисляем высоту каждого поддерева

    int l = heighAndSize(node->left, size);

    int r = heighAndSize(node->right, size);

  

    // увеличиваем размер на 1

    size++;

  

    // вернуть большее из двух

    return (l > r) ? l + 1 : r + 1;

}

  
// функция для расчета плотности бинарного дерева

float density(Node* root)

{

    if (root == NULL)

        return 0;

  

    int size = 0; // Сохранить размер

  

    // Находит высоту и размер

    int _height = heighAndSize(root, size);

  

    return (float)size/_height;

}

  
// Код драйвера для тестирования вышеуказанных методов

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-программа для определения плотности двоичного дерева

  
// Узел двоичного дерева

class Node 

{

    int data;

    Node left, right;

  

    public Node(int data) 

    {

        this.data = data;

        left = right = null;

    }

}

  
// Класс для реализации передачи по ссылке размера

class Size 

{

    // переменная для расчета размера дерева

    int size = 0;

}

  

class BinaryTree 

{

    Node root;

  

    // Функция для вычисления высоты и

    // размер двоичного дерева

    int heighAndSize(Node node, Size size) 

    {

        if (node == null)

            return 0;

  

        // вычисляем высоту каждого поддерева

        int l = heighAndSize(node.left, size);

        int r = heighAndSize(node.right, size);

  

        // увеличиваем размер на 1

        size.size++;

  

        // вернуть большее из двух

        return (l > r) ? l + 1 : r + 1;

    }

  

    // функция для расчета плотности бинарного дерева

    float density(Node root) 

    {

        Size size = new Size();

        if (root == null)

            return 0;

                 

        // Находит высоту и размер

        int _height = heighAndSize(root, size);

  

        return (float) size.size / _height;

    }

  

    // Код драйвера для тестирования вышеуказанных методов

    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));

    }

  
}

  
// Этот код предоставлен Mayank Jaiswal (mayank_24)

python3

# Python3 программа для определения плотности
# двоичного дерева

  
# Узел двоичного дерева
# Вспомогательная функция для выделения нового узла

class newNode: 

    def __init__(self, data): 

        self.data = data 

        self.left = self.right = None

          
# Функция для вычисления высоты и
# размер двоичного дерева

def heighAndSize(node, size): 

  

    if (node == None) :

        return 0

  

    # вычислить высоту каждого поддерева

    l = heighAndSize(node.left, size) 

    r = heighAndSize(node.right, size) 

  

    # увеличить размер на 1

    size[0] += 1

  

    # вернуть больше из двух

    return l + 1 if(l > r) else r + 1

  
# функция для расчета плотности
# двоичного дерева

def density(root):

  

    if (root == None) :

        return 0

  

    size = [0] # Чтобы сохранить размер

  

    # Находит высоту и размер

    _height = heighAndSize(root, size) 

  

    return size[0] / _height 

  
Код водителя

if __name__ == '__main__':

    root = newNode(1

    root.left = newNode(2

    root.right = newNode(3

  

    print("Density of given binary tree is ",

                               density(root))

  
# Этот код добавлен
# от SHUBHAMSINGH10

C #

// C # программа для определения плотности
// бинарного дерева

using System;

  
// Узел двоичного дерева

class Node 

    public int data; 

    public Node left, right; 

  

    public Node(int data) 

    

        this.data = data; 

        left = right = null

    

  
// Класс для реализации pass
// по размеру

class Size 

    // переменная для расчета

    // размер дерева

    public int size = 0; 

  

class BinaryTree 


Node root; 

  
// Функция для вычисления высоты
// и размер двоичного дерева

int heighAndSize(Node node,

                 Size size) 

    if (node == null

        return 0; 

  

    // вычисляем высоту каждого поддерева

    int l = heighAndSize(node.left, size); 

    int r = heighAndSize(node.right, size); 

  

    // увеличиваем размер на 1

    size.size++; 

  

    // вернуть большее из двух

    return (l > r) ? l + 1 : r + 1; 

  
// функция для расчета плотности
// двоичного дерева

float density(Node root) 

    Size size = new Size(); 

    if (root == null

        return 0; 

              

    // Находит высоту и размер

    int _height = heighAndSize(root, size); 

  

    return (float) size.size / _height; 

  
// Код драйвера

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)); 


  
// Этот код добавлен
// Арнаб Кунду

Выход:

Density of given binary tree is 1.5

Ссылка:
http://www.eem.anadolu.edu.tr/egermen/EEM%20480/icerik/EEM%20480%20Algorithms%20and%20Complexity%20Week%208.pdf

Эта статья предоставлена Aditya Goel . Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Плотность бинарного дерева в одном обходе

0.00 (0%) 0 votes