Рубрики

Проверьте, является ли данное Двоичное Дерево Полным или нет | Набор 1 (итеративное решение)

Деревья, Очередь

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

Полное двоичное дерево — это двоичное дерево, в котором каждый уровень, за исключением, возможно, последнего, полностью заполнен, а все узлы расположены как можно левее. Смотрите следующие примеры.

The following trees are examples of Complete Binary Trees
    1
  /   \
 2     3
  
       1
    /    \
   2       3
  /
 4

       1
    /    \
   2      3
  /  \    /
 4    5  6

The following trees are examples of Non-Complete Binary Trees
    1
      \
       3
  
       1
    /    \
   2       3
    \     /  \   
     4   5    6

       1
    /    \
   2      3
         /  \
        4    5

Метод 2 поста прохождения порядка уровней может быть легко изменен, чтобы проверить, является ли дерево Завершенным или нет. Чтобы понять подход, давайте сначала определим термин «полный узел». Узел является «полным узлом», если левые и правые дочерние элементы не пусты (или не равны NULL).
Подход заключается в том, чтобы сделать обход уровня порядка, начиная с корня. В обходе, когда найден узел, который НЕ является полным узлом, все последующие узлы должны быть конечными узлами.
Кроме того, еще одна вещь должна быть проверена для обработки следующего случая: если у узла есть пустой левый дочерний элемент, то правый дочерний элемент должен быть пустым.

    1
  /   \
 2     3
  \
   4

Спасибо Гудду Шарме за то, что он предложил этот простой и эффективный подход.

C ++

// C ++ программа для проверки, если данный
// двоичное дерево завершено или нет
#include <bits/stdc++.h>

using namespace std;

  
#define MAX_Q_SIZE 500 

  
/ * Узел двоичного дерева содержит данные,
указатель на левого ребенка и
указатель на правого ребенка * /

class node 

{ 

    public:

    int data; 

    node* left; 

    node* right; 

}; 

  
/ * прототипы функций для функций
необходим для структуры данных очереди.
Очередь необходима для уровня заказа tarversal * /

node** createQueue(int *, int *); 

void enQueue(node **, int *, node *); 

node *deQueue(node **, int *); 

bool isQueueEmpty(int *front, int *rear); 

  
/ * Учитывая бинарное дерево, вернуть
истина, если дерево завершено
иначе ложь * /

bool isCompleteBT(node* root) 

{ 

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

    // Бинарное дерево завершено

    if (root == NULL) 

        return true; 

      

    // Создать пустую очередь

    int rear, front; 

    node **queue = createQueue(&front, &rear); 

      

    // Создать переменную флага, которая будет установлена в true

    // когда виден не полный узел

    bool flag = false; 

      

    // Выполнить прохождение уровня по очереди, используя очередь.

    enQueue(queue, &rear, root); 

    while(!isQueueEmpty(&front, &rear)) 

    { 

        node *temp_node = deQueue(queue, &front); 

      

        / * Проверьте, присутствует ли оставленный ребенок * /

        if(temp_node->left) 

        { 

        // Если мы видели не полный узел,

        // и мы видим узел с непустым

        // левый ребенок, тогда данное дерево не

        // полное двоичное дерево

        if (flag == true) 

            return false; 

      

        enQueue(queue, &rear, temp_node->left); // ставим в очередь левого ребенка

        } 

        else // Если это не полный узел, установить флаг как истинный

        flag = true; 

      

        / * Проверить наличие правильного ребенка * /

        if(temp_node->right) 

        { 

        // Если мы видели не полный узел,

        // и мы видим узел с непустым

        // правильный ребенок, тогда данное дерево не

        // полное двоичное дерево

        if(flag == true) 

            return false; 

      

        enQueue(queue, &rear, temp_node->right); // ставим в очередь правого ребенка

        } 

        else // Если это не полный узел, установить флаг как истинный

        flag = true; 

    } 

      

    // Если мы достигнем здесь, то

    // дерево завершено Двоичное дерево

    return true; 

} 

  

  
/ * ПОЛЕЗНЫЕ ФУНКЦИИ * /

node** createQueue(int *front, int *rear) 

{ 

    node **queue = new node*();

      

    *front = *rear = 0; 

    return queue; 

} 

  

void enQueue(node **queue, int *rear, node *new_node) 

{ 

    queue[*rear] = new_node; 

    (*rear)++; 

} 

  

node *deQueue(node **queue, int *front) 

{ 

    (*front)++; 

    return queue[*front - 1]; 

} 

  

bool isQueueEmpty(int *front, int *rear) 

{ 

    return (*rear == *front); 

} 

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

node* newNode(int data) 

{ 

    node* Node = new node();

    Node->data = data; 

    Node->left = NULL; 

    Node->right = NULL; 

      

    return(Node); 

} 

  
/ * Код водителя * /

int main() 

{ 

    / * Давайте построим следующее двоичное дерево, которое

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

                1

            / /

            2 3

            ///

        4 5 6

        * /

      

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

      

    if ( isCompleteBT(root) == true ) 

        cout << "Complete Binary Tree"; 

    else

        cout << "NOT Complete Binary Tree"; 

      

    return 0; 

} 

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

С

// Программа для проверки, является ли данное двоичное дерево завершенным или нет
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX_Q_SIZE 500

  
/ * Узел двоичного дерева содержит данные, указатель на левый дочерний элемент

   и указатель на правого ребенка * /

struct node

{

    int data;

    struct node* left;

    struct node* right;

};

  
/ * прототипы функций для функций, необходимых для данных очереди

   структура. Очередь необходима для прохождения уровня заказа * /

struct node** createQueue(int *, int *);

void enQueue(struct node **, int *, struct node *);

struct node *deQueue(struct node **, int *);

bool isQueueEmpty(int *front, int *rear);

  
/ * Если задано бинарное дерево, вернуть true, если дерево завершено

   иначе ложь * /

bool isCompleteBT(struct node* root)

{

  // Базовый случай: пустое дерево завершено. Двоичное дерево

  if (root == NULL)

    return true;

  

  // Создать пустую очередь

  int rear, front;

  struct node **queue = createQueue(&front, &rear);

  

  // Создать переменную флага, которая будет установлена в true

  // когда виден не полный узел

  bool flag = false;

  

  // Выполнить прохождение уровня по очереди, используя очередь.

  enQueue(queue, &rear, root);

  while(!isQueueEmpty(&front, &rear))

  {

    struct node *temp_node = deQueue(queue, &front);

  

    / * Проверьте, присутствует ли оставленный ребенок * /

    if(temp_node->left)

    {

       // Если мы видели не полный узел, и мы видим узел

       // с непустым левым потомком, тогда данное дерево не

       // полное двоичное дерево

       if (flag == true)

         return false;

  

       enQueue(queue, &rear, temp_node->left);  // ставим в очередь левого ребенка

    }

    else // Если это не полный узел, установить флаг как истинный

       flag = true;

  

    / * Проверить наличие правильного ребенка * /

    if(temp_node->right)

    {

       // Если мы видели не полный узел, и мы видим узел

       // с непустым правым потомком, тогда данное дерево не

       // полное двоичное дерево

       if(flag == true)

         return false;

  

       enQueue(queue, &rear, temp_node->right);  // ставим в очередь правого ребенка

    }

    else // Если это не полный узел, установить флаг как истинный

       flag = true;

  }

  

  // Если мы доберемся сюда, то дерево завершено. Двоичное дерево

  return true;

}

  

  
/ * ПОЛЕЗНЫЕ ФУНКЦИИ * /

struct node** createQueue(int *front, int *rear)

{

  struct node **queue =

   (struct node **)malloc(sizeof(struct node*)*MAX_Q_SIZE);

  

  *front = *rear = 0;

  return queue;

}

  

void enQueue(struct node **queue, int *rear, struct node *new_node)

{

  queue[*rear] = new_node;

  (*rear)++;

}

  

struct node *deQueue(struct node **queue, int *front)

{

  (*front)++;

  return queue[*front - 1];

}

  

bool isQueueEmpty(int *front, int *rear)

{

   return (*rear == *front);

}

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

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

struct node* newNode(int data)

{

  struct node* node = (struct node*)

                       malloc(sizeof(struct node));

  node->data = data;

  node->left = NULL;

  node->right = NULL;

  

  return(node);

}

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

int main()

{

   / * Давайте построим следующее двоичное дерево, которое

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

            1

          / /

         2 3

        ///

       4 5 6

    * /

  

  struct node *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);

  

  if ( isCompleteBT(root) == true )

      printf ("Complete Binary Tree");

  else

      printf ("NOT Complete Binary Tree");

  

  return 0;

}

Джава

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

  

import java.util.LinkedList;

import java.util.Queue;

  

public class CompleteBTree 

{

    / * Узел двоичного дерева содержит данные, указатель на левый дочерний элемент

       и указатель на правого ребенка * /

    static class Node

    {

        int data;

        Node left;

        Node right;

          

        // Конструктор

        Node(int d)

        {

            data = d;

            left = null;

            right = null;

        }

    }

      

    / * Если задано бинарное дерево, вернуть true, если дерево завершено

       иначе ложь * /

    static boolean isCompleteBT(Node root)

    {

        // Базовый случай: пустое дерево завершено. Двоичное дерево

        if(root == null)

            return true;

          

        // Создать пустую очередь

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

          

        // Создать переменную флага, которая будет установлена в true

        // когда виден не полный узел

        boolean flag = false;

          

        // Выполнить прохождение уровня по очереди, используя очередь.

        queue.add(root);

        while(!queue.isEmpty())

        {

            Node temp_node = queue.remove();

              

            / * Проверьте, присутствует ли оставленный ребенок * /

            if(temp_node.left != null)

            {

                 // Если мы видели не полный узел, и мы видим узел

                 // с непустым левым потомком, тогда данное дерево не

                 // полное двоичное дерево

                if(flag == true)

                    return false;

                  

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

                queue.add(temp_node.left);

            }

            // Если это не полный узел, установить флаг как истинный

            else

                flag = true;

              

            / * Проверить наличие правильного ребенка * /

            if(temp_node.right != null)

            {

                // Если мы видели не полный узел, и мы видим узел

                // с непустым правым потомком, тогда данное дерево не

                // полное двоичное дерево

                if(flag == true)

                    return false;

                  

                // ставим в очередь правого ребенка

                queue.add(temp_node.right);

                  

            }

            // Если это не полный узел, установить флаг как истинный

            else 

                flag = true;

        }

         // Если мы доберемся сюда, то дерево завершено. Двоичное дерево

        return true;

    }

      

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

    public static void main(String[] args) 

    {

          

        / * Давайте построим следующее двоичное дерево, которое

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

                1

              / /

             2 3

            ///

           4 5 6

        * /

       

        Node root = new Node(1);

        root.left = new Node(2);

        root.right = new Node(3);

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

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

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

          

        if(isCompleteBT(root) == true)

            System.out.println("Complete Binary Tree");

        else

            System.out.println("NOT Complete Binary Tree");

     }

  
}
// Этот код предоставлен Sumit Ghosh

питон

# Проверьте, завершено ли двоичное дерево или нет

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

class Node:

  

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

    def __init__(self, data):

        self.data = data 

        self.left = None

        self.right = None

  
# Если задано двоичное дерево, вернуть true, если дерево завершено
# еще вернуть false

def isCompleteBT(root):

      

    # Базовый случай: пустое дерево заполнено Двоичное дерево

    if root is None:

        return True

  

    # Создать пустую очередь

    queue = []

  

    # Создайте переменную флага, которая будет установлена в True

    # когда виден не полный узел

    flag = False

  

    # Выполнить прохождение порядка уровней, используя очередь

    queue.append(root)

    while(len(queue) > 0):

        tempNode = queue.pop(0) # Dequeue

  

        # Проверьте, присутствует ли оставленный ребенок

        if (tempNode.left):

              

            # Если мы видели не полный узел, и мы видим

            # узел с непустым левым потомком, затем

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

            if flag == True :

                return False

  

            # Поставить в очередь левого ребенка

            queue.append(tempNode.left)

  

            # Если это не полный узел, установите флаг как true

        else:

            flag = True

  

        # Проверьте, присутствует ли правильный cild

        if(tempNode.right):

                  

            # Если мы видели не полный узел, и мы

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

            # данное дерево не является конкурентом BT

            if flag == True:

                return False

  

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

            queue.append(tempNode.right)

              

        # Если это не полный узел, установите флажок True

        else:

            flag = True

          

    # Если мы доберемся сюда, то дерево завершится BT

    return True

  

  
# Программа драйвера для проверки вышеуказанной функции

  
"" "Давайте построим следующее двоичное дерево, которое

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

            1

          / /

         2 3

        ///

       4 5 6

    «»»

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)

  

if (isCompleteBT(root)):

    print "Complete Binary Tree"

else:

    print "NOT Complete Binary Tree"

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

C #

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

using System;

using System.Collections.Generic;

  

public class CompleteBTree 

{

    / * Узел двоичного дерева содержит данные,

    указатель на левого ребенка и

     указатель на правого ребенка * /

    public class Node

    {

        public int data;

        public Node left;

        public Node right;

          

        // Конструктор

        public Node(int d)

        {

            data = d;

            left = null;

            right = null;

        }

    }

      

    / * Учитывая бинарное дерево, вернуть

    истина, если дерево завершено

    иначе ложь * /

    static bool isCompleteBT(Node root)

    {

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

        // Бинарное дерево завершено

        if(root == null)

            return true;

          

        // Создать пустую очередь

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

          

        // Создать переменную флага, которая будет установлена в true

        // когда виден не полный узел

        bool flag = false;

          

        // Выполнить прохождение уровня по очереди, используя очередь.

        queue.Enqueue(root);

        while(queue.Count != 0)

        {

            Node temp_node = queue.Dequeue();

              

            / * Проверьте, присутствует ли оставленный ребенок * /

            if(temp_node.left != null)

            {

                // Если мы видели не полный узел,

                // и мы видим узел с непустым

                // левый ребенок, тогда данное дерево не

                // полное двоичное дерево

                if(flag == true)

                    return false;

                  

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

                queue.Enqueue(temp_node.left);

            }

              

            // Если это не полный узел, установить флаг как истинный

            else

                flag = true;

              

            / * Проверить наличие правильного ребенка * /

            if(temp_node.right != null)

            {

                // Если мы видели не полный узел,

                // и мы видим узел с непустым

                // правый потомок, тогда данное дерево

                // не является полным двоичным деревом

                if(flag == true)

                    return false;

                  

                // ставим в очередь правого ребенка

                queue.Enqueue(temp_node.right);

                  

            }

              

            // Если это не полный узел,

            // установить флаг как истинный

            else

                flag = true;

        }

          

        // Если мы достигнем здесь, то

        // дерево завершено Двоичное дерево

        return true;

    }

      

    / * Код водителя * /

    public static void Main() 

    {

          

        / * Давайте построим следующее двоичное дерево, которое

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

                1

            / /

            2 3

            ///

        4 5 6

        * /

      

        Node root = new Node(1);

        root.left = new Node(2);

        root.right = new Node(3);

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

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

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

          

        if(isCompleteBT(root) == true)

            Console.WriteLine("Complete Binary Tree");

        else

            Console.WriteLine("NOT Complete Binary Tree");

    }

}

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


Выход:

NOT Complete Binary Tree

Сложность времени: O (n), где n — количество узлов в данном двоичном дереве

Вспомогательное пространство: O (n) для очереди.

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

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

Проверьте, является ли данное Двоичное Дерево Полным или нет | Набор 1 (итеративное решение)

0.00 (0%) 0 votes