Рубрики

Плотность бинарного дерева с использованием уровня обхода порядка

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

Плотность бинарного дерева определяется как:

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 the following tree
     10
    /   
   20   
 /
30
Output : 1
Height of given tree = 3
Size of given tree = 3 

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

Для вычисления высоты двоичного дерева идея состоит в том, чтобы использовать указатель «NULL» в качестве разделителя между двумя уровнями. Всякий раз, когда во время обхода появляется «NULL», высота увеличивается.

Чтобы вычислить размер двоичного дерева, увеличьте счетчик для каждого нового узла, обнаруженного во время обхода порядка уровней.

Наконец, используйте приведенную выше формулу для расчета плотности бинарного дерева.

Ниже приведена реализация вышеуказанного подхода:

C ++

// C ++ реализация вышеуказанного подхода
#include <bits/stdc++.h>

using namespace std;

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

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;

}

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

float density(Node* root)

{

    queue<Node*> q;

  

    // сначала помещаем root в очередь

    q.push(root);

      

    // вставляем NULL как разделитель

    q.push(NULL);

    int height = 1, size = 0;

    while (!q.empty()) {

        Node* t = q.front();

        q.pop();

        if (t)

            size++;

        else {

  

            // Если после нажатия NULL очередь

            // пусто, затем выходим из цикла т.е.

            // остановить прохождение уровня ордера.

            if (q.empty())

                break;

            q.push(NULL);

            height++;

            continue;

        }

  

        // если т оставил ребенка

        // затем помещаем его в очередь

        if (t->left) {

            q.push(t->left);

        }

  

        // если т имеет правильного потомка

        // затем помещаем его в очередь

        if (t->right) {

            q.push(t->right);

        }

    }

    return (float)size / height;

}

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

int main()

{

    Node* root = newNode(1);

    root->left = newNode(2);

    root->right = newNode(3);

  

    cout << density(root) << endl;

    return 0;

}

Джава

// Java реализация вышеуказанного подхода

import java.util.*;

  

class Solution

{

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

static class Node

    int data; 

    Node left, right; 

}

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

static Node newNode(int data) 

    Node node = new Node(); 

    node.data = data; 

    node.left = node.right = null

    return node; 

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

static float density(Node root) 

    Queue<Node> q = new LinkedList<Node>(); 

  

    // сначала добавляем root в очередь

    q.add(root); 

      

    // добавить ноль в качестве разделителя

    q.add(null); 

    int height = 1, size = 0

    while (q.size() > 0)

    

        Node t = q.peek(); 

        q.remove(); 

        if (t != null

            size++; 

        else

        

  

            // Если после удаления нулевая очередь

            // пусто, затем выходим из цикла т.е.

            // остановить прохождение уровня ордера.

            if (q.size() == 0

                break

            q.add(null); 

            height++; 

            continue

        

  

        // если т оставил ребенка

        // затем добавляем его в очередь

        if (t.left !=null

        

            q.add(t.left); 

        

  

        // если т имеет правильного потомка

        // затем добавляем его в очередь

        if (t.right != null)

        

            q.add(t.right); 

        

    

    return ((float)size )/ height; 

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

public static void main(String args[])

    Node root = newNode(1); 

    root.left = newNode(2); 

    root.right = newNode(3); 

  

    System.out.println(density(root)); 

}

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

C #

// C # реализация вышеуказанного подхода

using System; 

using System.Collections.Generic; 

  

class GFG

{

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

public class Node

    public int data; 

    public Node left, right; 

}

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

static Node newNode(int data) 

    Node node = new Node(); 

    node.data = data; 

    node.left = node.right = null

    return node; 

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

static float density(Node root) 

    Queue<Node> q = new Queue<Node>(); 

  

    // сначала добавляем root в очередь

    q.Enqueue(root); 

      

    // добавить ноль в качестве разделителя

    q.Enqueue(null); 

    int height = 1, size = 0; 

    while (q.Count > 0)

    

        Node t = q.Peek(); 

        q.Dequeue(); 

        if (t != null

            size++; 

        else

        

  

            // Если после удаления нулевая очередь

            // пусто, затем выходим из цикла т.е.

            // остановить прохождение уровня ордера.

            if (q.Count == 0) 

                break

            q.Enqueue(null); 

            height++; 

            continue

        

  

        // если т оставил ребенка

        // затем добавляем его в очередь

        if (t.left !=null

        

            q.Enqueue(t.left); 

        

  

        // если т имеет правильного потомка

        // затем добавляем его в очередь

        if (t.right != null)

        

            q.Enqueue(t.right); 

        

    

    return ((float)size ) / height; 

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

public static void Main(String []args)

    Node root = newNode(1); 

    root.left = newNode(2); 

    root.right = newNode(3); 

  

    Console.WriteLine(density(root)); 

}
}

  
// Этот код предоставлен PrinciRaj1992

Выход:

1.5

Сложность времени: O (N)

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

Плотность бинарного дерева с использованием уровня обхода порядка

0.00 (0%) 0 votes