Рубрики

Проверьте, является ли данное двоичное дерево кучей

Для заданного двоичного дерева нам нужно проверить, есть ли у него свойство кучи или нет. Двоичное дерево должно удовлетворять следующим двум условиям:

  1. Это должно быть полное дерево (т.е. все уровни, кроме последнего, должны быть полными).
  2. Значение каждого узла должно быть больше или равно его дочернему узлу (учитывая max-heap).

Например, это дерево содержит свойство кучи —

Хотя это не так —

Мы проверяем каждое из вышеперечисленных условий отдельно, для проверки полноты написана isComplete и для проверки куча написана функция isHeapUtil.
Подробно о функции isComplete можно узнать здесь .

Функция isHeapUtil написана с учетом следующих вещей:

  1. Каждый узел может иметь 2 дочерних, 0 дочерних (узлы последнего уровня) или 1 дочерний (может быть не более одного такого узла).
  2. Если Node не имеет дочернего элемента, то это листовой узел, который возвращает true (базовый случай)
  3. Если у Node есть один дочерний элемент (его нужно оставить дочерним, потому что он является полным деревом), тогда нам нужно сравнить этот узел только с его единственным дочерним элементом.
  4. Если у узла есть оба дочерних элемента, то проверьте свойство кучи в узле в recur для обоих поддеревьев.
    Полный код

Реализация

C / C ++

/ * C программа для проверки, является ли двоичное дерево максимальной кучей или нет * /
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>

  
/ * Древовидная структура * /

struct Node

{

    int key;

    struct Node *left;

    struct Node *right;

};

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

struct Node *newNode(int k)

{

    struct Node *node = (struct Node*)malloc(sizeof(struct Node));

    node->key = k;

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

    return node;

}

  
/ * Эта функция подсчитывает количество узлов в двоичном дереве * /

unsigned int countNodes(struct Node* root)

{

    if (root == NULL)

        return (0);

    return (1 + countNodes(root->left) + countNodes(root->right));

}

  
/ * Эта функция проверяет, является ли двоичное дерево полным или нет * /

bool isCompleteUtil (struct Node* root, unsigned int index,

                     unsigned int number_nodes)

{

    // Пустое дерево завершено

    if (root == NULL)

        return (true);

  

    // Если индекс, присвоенный текущему узлу, больше

    // количество узлов в дереве, то дерево не завершено

    if (index >= number_nodes)

        return (false);

  

    // Повтор для левого и правого поддеревьев

    return (isCompleteUtil(root->left, 2*index + 1, number_nodes) &&

            isCompleteUtil(root->right, 2*index + 2, number_nodes));

}

  
// Эта функция проверяет свойство кучи в дереве.

bool isHeapUtil(struct Node* root)

{

    // Базовый случай: один узел удовлетворяет свойству

    if (root->left == NULL && root->right == NULL)

        return (true);

  

    // узел будет на втором последнем уровне

    if (root->right == NULL)

    {

        // проверяем свойство кучи на узле

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

        return (root->key >= root->left->key);

    }

    else

    {

        // Проверка свойства кучи на узле и

        // Рекурсивная проверка свойства кучи на левом и правом поддереве

        if (root->key >= root->left->key &&

            root->key >= root->right->key)

            return ((isHeapUtil(root->left)) &&

                    (isHeapUtil(root->right)));

        else

            return (false);

    }

}

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

bool isHeap(struct Node* root)

{

    // Эти два используются в isCompleteUtil ()

    unsigned int node_count = countNodes(root);

    unsigned int index = 0;

  

    if (isCompleteUtil(root, index, node_count) && isHeapUtil(root))

        return true;

    return false;

}

  
// Драйвер программы

int main()

{

    struct Node* root = NULL;

    root = newNode(10);

    root->left = newNode(9);

    root->right = newNode(8);

    root->left->left = newNode(7);

    root->left->right = newNode(6);

    root->right->left = newNode(5);

    root->right->right = newNode(4);

    root->left->left->left = newNode(3);

    root->left->left->right = newNode(2);

    root->left->right->left = newNode(1);

  

    if (isHeap(root))

        printf("Given binary tree is a Heap\n");

    else

        printf("Given binary tree is not a Heap\n");

  

    return 0;

}

Джава

/ * Java-программа для проверки, является ли двоичное дерево максимальной кучей или нет * /

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

class Node

{

    int key;

    Node left, right;

  

    Node(int k)

    {

        key = k;

        left = right = null;

    }

}

  

class Is_BinaryTree_MaxHeap

{

    / * Эта функция подсчитывает количество узлов в двоичном дереве * /

    int countNodes(Node root)

    {

        if(root==null)

            return 0;

        return(1 + countNodes(root.left) + countNodes(root.right));

    }

      

    / * Эта функция проверяет, является ли двоичное дерево полным или нет * /

    boolean isCompleteUtil(Node root, int index, int number_nodes)

    {

        // Пустое дерево завершено

        if(root == null)

            return true;

          

        // Если индекс, присвоенный текущему узлу, больше

        // количество узлов в дереве, то дерево не завершено

        if(index >= number_nodes)

            return false;

          

        // Повтор для левого и правого поддеревьев

        return isCompleteUtil(root.left, 2*index+1, number_nodes) && 

               isCompleteUtil(root.right, 2*index+2, number_nodes);

          

    }

      

    // Эта функция проверяет свойство кучи в дереве.

    boolean isHeapUtil(Node root)

    {

        // Базовый случай: один узел удовлетворяет свойству

        if(root.left == null && root.right==null)

            return true;

          

        // узел будет на втором последнем уровне

        if(root.right == null)

        {

            // проверяем свойство кучи на узле

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

            return root.key >= root.left.key;

        }

        else

        {

            // Проверка свойства кучи на узле и

            // Рекурсивная проверка свойства кучи на левом и правом поддереве

            if(root.key >= root.left.key && root.key >= root.right.key)

                return isHeapUtil(root.left) && isHeapUtil(root.right);

            else

                return false;

        }

    }

      

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

    boolean isHeap(Node root)

    {

        if(root == null)

            return true;

          

        // Эти два используются в isCompleteUtil ()

        int node_count = countNodes(root);

          

        if(isCompleteUtil(root, 0 , node_count)==true && isHeapUtil(root)==true)

            return true;

        return false;

    }

      

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

    public static void main(String args[])

    {

        Is_BinaryTree_MaxHeap bt = new Is_BinaryTree_MaxHeap();

          

        Node root = new Node(10);

        root.left = new Node(9);

        root.right = new Node(8);

        root.left.left = new Node(7);

        root.left.right = new Node(6);

        root.right.left = new Node(5);

        root.right.right = new Node(4);

        root.left.left.left = new Node(3);

        root.left.left.right = new Node(2);

        root.left.right.left = new Node(1);

  

        if(bt.isHeap(root) == true)

            System.out.println("Given binary tree is a Heap");

        else 

            System.out.println("Given binary tree is not a Heap");

    }

}

  
// Этот код предоставлен Амитом Хандельвалом

питон

# Проверить, является ли двоичное дерево
# МАКС Куча или нет

class GFG:

    def __init__(self, value):

        self.key = value

        self.left = None

        self.right = None

      

    def count_nodes(self, root):

        if root is None:

            return 0

        else:

            return (1 + self.count_nodes(root.left) + 

                        self.count_nodes(root.right))

      

    def heap_propert_util(self, root):

      

        if (root.left is None and 

            root.right is None):

            return True

      

        if root.right is None:

            return root.key >= root.left.key

        else:

            if (root.key >= root.left.key and 

                root.key >= root.right.key):

                return (self.heap_propert_util(root.left) and 

                        self.heap_propert_util(root.right))

            else:

                return False

      

    def complete_tree_util(self, root, 

                           index, node_count):

        if root is None:

            return True

        if index >= node_count:

            return False

        return (self.complete_tree_util(root.left, 2 * 

                                       index + 1, node_count) and 

               self.complete_tree_util(root.right, 2 * 

                                       index + 2, node_count))

      

    def check_if_heap(self):

        node_count = self.count_nodes(self)

        if (self.complete_tree_util(self, 0, node_count) and 

            self.heap_propert_util(self)):

            return True

        else:

            return False

  
Код водителя

root = GFG(5)

root.left = GFG(2)

root.right = GFG(3)

root.left.left = GFG(1)

  

if root.check_if_heap():

    print("Given binary tree is a heap")

else:

    print("Given binary tree is not a Heap")

  
# Этот код был
# предоставлено Яшем Агравалом

C #

/ * C # программа для проверки, является ли двоичное дерево максимальной кучей или нет * /

using System;

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

public class Node 

    public int key; 

    public Node left, right; 

  

    public Node(int k) 

    

        key = k; 

        left = right = null

    

  

class Is_BinaryTree_MaxHeap 

    / * Эта функция считает число

    узлов в двоичном дереве * /

    int countNodes(Node root) 

    

        if(root == null

            return 0; 

        return(1 + countNodes(root.left) + countNodes(root.right)); 

    

      

    / * Эта функция проверяет,

    двоичное дерево завершено или нет * /

    Boolean isCompleteUtil(Node root, int index, int number_nodes) 

    

        // Пустое дерево завершено

        if(root == null

            return true

          

        // Если индекс, присвоенный текущему узлу, больше

        // количество узлов в дереве, то дерево не завершено

        if(index >= number_nodes) 

            return false

          

        // Повтор для левого и правого поддеревьев

        return isCompleteUtil(root.left, 2*index+1, number_nodes) && 

            isCompleteUtil(root.right, 2*index+2, number_nodes); 

          

    

      

    // Эта функция проверяет свойство кучи в дереве.

    Boolean isHeapUtil(Node root) 

    

        // Базовый случай: один узел удовлетворяет свойству

        if(root.left == null && root.right==null

            return true

          

        // узел будет на втором последнем уровне

        if(root.right == null

        

            // проверяем свойство кучи на узле

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

            return root.key >= root.left.key; 

        

        else

        

            // Проверка свойства кучи на узле и

            // Рекурсивная проверка свойства кучи на левом и правом поддереве

            if(root.key >= root.left.key && root.key >= root.right.key) 

                return isHeapUtil(root.left) && isHeapUtil(root.right); 

            else

                return false

        

    

      

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

    Boolean isHeap(Node root) 

    

        if(root == null

            return true

          

        // Эти два используются в isCompleteUtil ()

        int node_count = countNodes(root); 

          

        if(isCompleteUtil(root, 0 , node_count)==true && isHeapUtil(root)==true

            return true

        return false

    

      

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

    public static void Main(String []args) 

    

        Is_BinaryTree_MaxHeap bt = new Is_BinaryTree_MaxHeap(); 

          

        Node root = new Node(10); 

        root.left = new Node(9); 

        root.right = new Node(8); 

        root.left.left = new Node(7); 

        root.left.right = new Node(6); 

        root.right.left = new Node(5); 

        root.right.right = new Node(4); 

        root.left.left.left = new Node(3); 

        root.left.left.right = new Node(2); 

        root.left.right.left = new Node(1); 

  

        if(bt.isHeap(root) == true

            Console.WriteLine("Given binary tree is a Heap"); 

        else

            Console.WriteLine("Given binary tree is not a Heap"); 

    

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


Выход:

Given binary tree is a Heap

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

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

Проверьте, является ли данное двоичное дерево кучей

0.00 (0%) 0 votes