Рубрики

Проверьте, является ли двоичное дерево полным двоичным деревом или нет

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

Например :

Чтобы проверить, является ли двоичное дерево полным двоичным деревом, нам нужно проверить следующие случаи:

1) Если узел двоичного дерева равен NULL, то это полное двоичное дерево.
2) Если узел двоичного дерева имеет пустое левое и правое поддеревья, то по определению это полное двоичное дерево.
3) Если узел двоичного дерева имеет левое и правое поддеревья, то он по определению является частью полного двоичного дерева. В этом случае рекурсивно проверяют, являются ли левые и правые поддеревья самими двоичными деревьями.
4) Во всех других комбинациях правого и левого поддеревьев двоичное дерево не является полным двоичным деревом.

Ниже приведена реализация для проверки, является ли двоичное дерево полным двоичным деревом.

С

// Программа на 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;

}

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

bool isFullTree (struct Node* root)

{

    // Если дерево пустое

    if (root == NULL)

        return true;

  

    // Если конечный узел

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

        return true;

  

    // Если левые и правые не равны NULL, а левые и правые поддеревья

    // полны

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

        return (isFullTree(root->left) && isFullTree(root->right));

  

    // Мы достигаем здесь, когда ничего из перечисленного не работает

    return false;

}

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

int main()

{

    struct Node* root = NULL;

    root = newNode(10);

    root->left = newNode(20);

    root->right = newNode(30);

  

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

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

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

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

  

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

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

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

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

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

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

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

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

  

    if (isFullTree(root))

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

    else

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

  

    return(0);

}

Джава

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

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

class Node 

{

    int data;

    Node left, right;

   

    Node(int item) 

    {

        data = item;

        left = right = null;

    }

}

   

class BinaryTree 

{

    Node root;

       

    / * эта функция проверяет, заполнено ли двоичное дерево * /

    boolean isFullTree(Node node)

    {

        // если дерево пустое

        if(node == null)

        return true;

           

        // если листовой узел

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

            return true;

           

        // если левые и правые поддеревья не равны нулю

        // заполнены

        if((node.left!=null) && (node.right!=null))

            return (isFullTree(node.left) && isFullTree(node.right));

           

        // если ничего не работает

        return false;

    }

   

       

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

    public static void main(String args[]) 

    {

        BinaryTree tree = new BinaryTree();

        tree.root = new Node(10);

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

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

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

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

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

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

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

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

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

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

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

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

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

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

           

        if(tree.isFullTree(tree.root))

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

        else

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

    }

}

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

питон

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

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

class Node:

  

    # Конструктор класса узла для создания узла

    def __init__(self , key):

        self.key = key

        self.left = None

        self.right = None

  
# Проверяет, заполнено ли двоичное дерево или нет

def isFullTree(root):

  

    # Если дерево пустое

    if root is None:    

        return True

      

    # Если конечный узел

    if root.left is None and root.right is None:

        return True

  

    # Если левый и правый субтресс не равны None и

    # левый и правый субтресс заполнены

    if root.left is not None and root.right is not None:

        return (isFullTree(root.left) and isFullTree(root.right))

      

    # Мы достигаем здесь, когда ничего из вышеперечисленного, если условия работают

    return False

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

root = Node(10);

root.left = Node(20);

root.right = Node(30);

  

root.left.right = Node(40);

root.left.left = Node(50);

root.right.left = Node(60);

root.right.right = Node(70);

  

root.left.left.left = Node(80);

root.left.left.right = Node(90);

root.left.right.left = Node(80);

root.left.right.right = Node(90);

root.right.left.left = Node(80);

root.right.left.right = Node(90);

root.right.right.left = Node(80);

root.right.right.right = Node(90);

  

if isFullTree(root):

    print "The Binary tree is full"

else:

    print "Binary tree is not full"

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

C #

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

using System;

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

public class Node

{

    public int data;

    public Node left, right;

  

    public Node(int item)

    {

        data = item;

        left = right = null;

    }

}

  

class GFG

{

public Node root;

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

public virtual bool isFullTree(Node node)

{

    // если дерево пустое

    if (node == null)

    {

    return true;

    }

  

    // если листовой узел

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

    {

        return true;

    }

  

    // если и левое и правое поддеревья

    // не нулевые они полны

    if ((node.left != null) && (node.right != null))

    {

        return (isFullTree(node.left) && 

                isFullTree(node.right));

    }

  

    // если ничего не работает

    return false;

}

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

public static void Main(string[] args)

{

    GFG tree = new GFG();

    tree.root = new Node(10);

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  

    if (tree.isFullTree(tree.root))

    {

        Console.Write("The binary tree is full");

    }

    else

    {

        Console.Write("The binary tree is not full");

    }

}
}

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

Выход:

The Binary Tree is full

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

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

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

Проверьте, является ли двоичное дерево полным двоичным деревом или нет

0.00 (0%) 0 votes