Рубрики

Проверьте, является ли двоичное дерево полным деревом | Набор 2 (Рекурсивное решение)

Полное двоичное дерево — это двоичное дерево, у которого все уровни, кроме последнего, полностью заполнены, а все листья на последнем уровне находятся слева. Более подробную информацию о полных бинарных деревьях можно найти здесь .

Например:-

Под деревом находится полное двоичное дерево (все узлы до последних последних узлов заполнены и все листья находятся слева)

Итеративное решение этой проблемы обсуждается в посте ниже.
Проверьте, является ли данное Двоичное Дерево Полным или нет | Установите 1 (используя уровень обхода порядка)

В этом посте обсуждается рекурсивное решение.

В представлении массива двоичного дерева, если родительскому узлу присваивается индекс «i», а левому дочернему элементу присваивается индекс «2 * i + 1», в то время как правому дочернему элементу присваивается индекс «2 * i +». 2' . Если мы представим вышеупомянутое двоичное дерево в виде массива с соответствующими индексами, назначенными различным узлам дерева сверху вниз сверху вниз и слева направо.

Следовательно, мы действуем следующим образом, чтобы проверить, является ли двоичное дерево полным двоичным деревом.

  1. Рассчитать количество узлов (кол) в двоичном дереве.
  2. Начать рекурсию двоичного дерева из корневого узла двоичного дерева с индексом (i), установленным в 0, и количеством узлов в двоичном файле (количество).
  3. Если текущий рассматриваемый узел имеет значение NULL, то дерево является полным двоичным деревом. Верните истину.
  4. Если индекс (i) текущего узла больше или равен количеству узлов в двоичном дереве (число), т.е. (i> = число), то дерево не является полным двоичным файлом. Вернуть ложь.
  5. Рекурсивно проверяют левое и правое поддеревья двоичного дерева на одно и то же условие. Для левого поддерева используйте индекс как (2 * i + 1), а для правого поддерева используйте индекс как (2 * i + 2).

Временная сложность приведенного выше алгоритма составляет O (n). Ниже приведен код для проверки, является ли двоичное дерево полным двоичным деревом.

С

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

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

struct Node

{

    int key;

    struct Node *left, *right;

};

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

   данный ключ и NULL левый и правый указатель. * /

struct Node *newNode(char 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 isComplete (struct Node* root, unsigned int index,

                 unsigned int number_nodes)

{

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

    if (root == NULL)

        return (true);

  

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

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

    if (index >= number_nodes)

        return (false);

  

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

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

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

}

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

int main()

{

    // оставим нам дерево в последней диаграмме выше

    struct Node* root = NULL;

    root = newNode(1);

    root->left = newNode(2);

    root->right = newNode(3);

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

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

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

  

    unsigned int node_count = countNodes(root);

    unsigned int index = 0;

  

    if (isComplete(root, index, node_count))

        printf("The Binary Tree is complete\n");

    else

        printf("The Binary Tree is not complete\n");

    return (0);

}

Джава

// Java-программа для проверки, завершено ли бинарное дерево

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

class Node 

{

    int data;

    Node left, right;

   

    Node(int item) {

        data = item;

        left = right = null;

    }

}

   

class BinaryTree 

{

    Node root;

   

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

    int countNodes(Node root) 

    {

        if (root == null)

            return (0);

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

    }

   

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

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

    {

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

        if (root == null)        

           return true;

   

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

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

        if (index >= number_nodes)

           return false;

   

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

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

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

   

    }

   

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

    public static void main(String args[]) 

    {

        BinaryTree tree = new BinaryTree();

          

        // оставим нам дерево в последней диаграмме выше

        Node NewRoot = null;

        tree.root = new Node(1);

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

        tree.root.right = new Node(3);

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

        tree.root.left.left = new Node(4);

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

           

        int node_count = tree.countNodes(tree.root);

        int index = 0;

           

        if (tree.isComplete(tree.root, index, node_count))

            System.out.print("The binary tree is complete");

        else

            System.out.print("The binary tree is not complete"); 

    }

}

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

питон

# Программа Python для проверки, завершено ли двоичное дерево или нет

  
# Структура дерева

class Node:

  

    # Contructor для создания нового узла

    def __init__(self, key):

        self.key = key

        self.left = None 

        self.right = None 

  

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

def countNodes(root):

    if root is None:

        return 0 

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

  
# Эта функция проверяет, завершено ли двоичное дерево или нет

def isComplete(root, index, number_nodes):

      

    # Пусто заполнено

    if root is None:

        return True

      

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

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

    if index >= number_nodes :

        return False

      

    # Повторить для левого и правого субтресса

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

        and isComplete(root.right, 2*index+2, number_nodes)

          )

  
# Драйверная программа

  

root = Node(1)

root.left = Node(2)

root.right = Node(3)

root.left.left = Node(4)

root.left.right = Node(5)

root.right.right = Node(6)

  

node_count = countNodes(root)

index = 0 

  

if isComplete(root, index, node_count):

    print "The Binary Tree is complete"

else:

    print "The Binary Tree is not complete"

  
# Этот код предоставлен Nikhil Kumar Singh (nickzuck_007)

C #

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

using System;

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

class Node 

    public int data; 

    public Node left, right; 

  

    public Node(int item)

    

        data = item; 

        left = right = null

    

  

public class BinaryTree 

    Node root; 

  

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

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

    int countNodes(Node root) 

    

        if (root == null

            return (0); 

        return (1 + countNodes(root.left) + 

                    countNodes(root.right)); 

    

  

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

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

    bool isComplete(Node root, int index,

                    int number_nodes) 

    

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

        if (root == null)     

        return true

  

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

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

        if (index >= number_nodes) 

        return false

  

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

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

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

  

    

  

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

    public static void Main() 

    

        BinaryTree tree = new BinaryTree(); 

          

        // Давайте создадим дерево на последней диаграмме выше

        tree.root = new Node(1); 

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

        tree.root.right = new Node(3); 

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

        tree.root.left.left = new Node(4); 

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

          

        int node_count = tree.countNodes(tree.root); 

        int index = 0; 

          

        if (tree.isComplete(tree.root, index, node_count)) 

            Console.WriteLine("The binary tree is complete"); 

        else

            Console.WriteLine("The binary tree is not complete"); 

    

  
/ * Этот код предоставлен Rajput-Ji * /


Выход:

The Binary Tree is not complete 

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

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

Проверьте, является ли двоичное дерево полным деревом | Набор 2 (Рекурсивное решение)

0.00 (0%) 0 votes