Итерационный подход к проверке совершенства двоичного дерева

Опубликовано: 23 Января, 2022

Учитывая двоичное дерево , задача состоит в том, чтобы проверить, является ли данное двоичное дерево идеальным двоичным деревом или нет.

Двоичное дерево - это идеальное двоичное дерево, в котором все внутренние узлы имеют двух дочерних элементов, а все листья находятся на одном уровне.

Примеры:

Вход : 
          1
         / 
        2 3
       /  / 
      4 5 6 7
Выход: Да

Вход :
           20
         / 
        8 22
       /  / 
      5 3 4 25
     /  /  
    1 10 2 14 6
Выход: Нет 
Один листовой узел со значением 4 отсутствует в 
последний уровень и узел со значением 25 имеет 
только один ребенок.

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Мы уже обсуждали рекурсивный подход. В этом посте обсуждается итеративный подход.

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

  1. Если текущий узел имеет двух дочерних узлов, мы проверим значение flag . Если значение flag равно нулю, тогда нажмите левый и правый дочерние элементы в очереди, но если значение flag равно единице, тогда верните false, потому что тогда это означает, что листовой узел уже найден, а в идеальном двоичном дереве все листовые узлы должен присутствовать на последнем уровне, никакой листовой узел не должен присутствовать на любом другом уровне.
  2. Если текущий узел не имеет дочернего узла, это означает, что это листовой узел, отметьте флаг как единицу.
  3. Если текущий узел имеет только один дочерний элемент, верните false, так как в идеальном двоичном дереве все узлы имеют двух дочерних узлов, за исключением конечных узлов, которые должны присутствовать на последнем уровне дерева.

Below is the implementation of the above approach:

C++

// C++ program to check if the
// given binary tree is perfect
#include <bits/stdc++.h>
using namespace std;
  
// A binary tree node
struct Node {
    int data;
    Node *left, *right;
};
  
// Utility function to allocate memory for a new node
Node* newNode(int data)
{
    Node* node = new (Node);
    node->data = data;
    node->left = node->right = NULL;
    return (node);
}
  
// Function to check if the given tree is perfect
bool CheckPerfectTree(Node* root)
{
    queue<Node*> q;
  
    // Push the root node
    q.push(root);
  
    // Flag to check if leaf nodes have been found
    int flag = 0;
  
    while (!q.empty()) {
        Node* temp = q.front();
        q.pop();
  
        // If current node has both left and right child
        if (temp->left && temp->right) {
            // If a leaf node has already been found
            // then return false
            if (flag == 1)
                return false;
  
            // If a leaf node has not been discovered yet
            // push the left and right child in the queue
            else {
                q.push(temp->left);
                q.push(temp->right);
            }
        }
  
        // If a leaf node is found mark flag as one
        else if (!temp->left && !temp->right) {
            flag = 1;
        }
  
        // If the current node has only one child
        // then return false
        else if (!temp->left || !temp->right)
            return false;
    }
  
    // If the given tree is perfect return true
    return true;
}
  
// Driver code
int main()
{
    Node* root = newNode(7);
    root->left = newNode(5);
    root->right = newNode(6);
    root->left->left = newNode(8);
    root->left->right = newNode(1);
    root->right->left = newNode(3);
    root->right->right = newNode(9);
    root->right->right->right = newNode(13);
    root->right->right->left = newNode(10);
  
    if (CheckPerfectTree(root))
        printf("Yes");
    else
        printf("No");
  
    return 0;
}

Java

// Java program to check if the 
// given binary tree is perfect 
import java.util.*;
  
class GFG
{
      
// A binary tree node 
static class Node 
{ 
    int data; 
    Node left, right; 
}; 
  
// Utility function to allocate memory for a new node 
static Node newNode(int data) 
{ 
    Node node = new Node(); 
    node.data = data; 
    node.left = node.right = null; 
    return (node); 
} 
  
// Function to check if the given tree is perfect 
static boolean CheckPerfectTree(Node root) 
{ 
    Queue<Node> q = new LinkedList<Node>(); 
  
    // add the root node 
    q.add(root); 
  
    // Flag to check if leaf nodes have been found 
    int flag = 0; 
  
    while (q.size() > 0)
    { 
        Node temp = q.peek(); 
        q.remove(); 
  
        // If current node has both left and right child 
        if (temp.left != null && temp.right != null) 
        { 
            // If a leaf node has already been found 
            // then return false 
            if (flag == 1) 
                return false; 
  
            // If a leaf node has not been discovered yet 
            // add the left and right child in the queue 
            else
            { 
                q.add(temp.left); 
                q.add(temp.right); 
            } 
        } 
  
        // If a leaf node is found mark flag as one 
        else if (temp.left == null && temp.right == null) 
        { 
            flag = 1; 
        } 
  
        // If the current node has only one child 
        // then return false 
        else if (temp.left == null || temp.right == null) 
            return false; 
    } 
  
    // If the given tree is perfect return true 
    return true; 
} 
  
// Driver code 
public static void main(String args[])
{ 
    Node root = newNode(7); 
    root.left = newNode(5); 
    root.right = newNode(6); 
    root.left.left = newNode(8); 
    root.left.right = newNode(1); 
    root.right.left = newNode(3); 
    root.right.right = newNode(9); 
    root.right.right.right = newNode(13); 
    root.right.right.left = newNode(10); 
  
    if (CheckPerfectTree(root)) 
        System.out.printf("Yes"); 
    else
        System.out.printf("No"); 
} 
}
  
// This code is contributed by Arnab Kundu

Python3

# Python3 program to check if the 
# given binary tree is perfect 
import sys
import math
  
# A binary tree node
class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
  
# Utility function to allocate 
# memory for a new node 
def newNode(data):
    return Node(data)
  
# Function to check if the 
# given tree is perfect
def CheckPerfectTree(root):
    q = []
  
    # Push the root node
    q.append(root)
  
    # Flag to check if leaf nodes 
    # have been found 
    flag = 0
      
    while(q):
        temp = q[0]
        q.pop(0)
  
        # If current node has both 
        # left and right child
        if (temp.left and temp.right):
              
            # If a leaf node has already been found 
            # then return false 
            if (flag == 1):
                return False
  
            # If a leaf node has not been discovered yet 
            # push the left and right child in the queue 
            else:
                q.append(temp.left)
                q.append(temp.right)
  
        # If a leaf node is found 
        # mark flag as one     
        elif(not temp.left and 
             not temp.right):
            flag = 1
  
        # If the current node has only one child 
        # then return false 
        elif(not temp.left or 
             not temp.right):
            return False
              
    # If the given tree is perfect
    # return true
    return True
  
# Driver Code
if __name__=="__main__":
    root = newNode(7)
    root.left = newNode(5)
    root.left.left = newNode(8)
    root.left.right = newNode(1)
    root.right = newNode(6)
    root.right.left = newNode(3)
    root.right.right = newNode(9)
    root.right.right.left = newNode(10)
    root.right.right.right = newNode(13)
  
    if CheckPerfectTree(root):
        print("Yes")
    else:
        print("No")
  
# This code is contributed
# by Vikash Kumar 37

C#

// C# program to check if the 
// given binary tree is perfect
using System;
using System.Collections.Generic; 
      
class GFG
{
      
// A binary tree node 
public class Node 
{ 
    public int data; 
    public Node left, right; 
}; 
  
// Utility function to allocate
// memory for a new node 
static Node newNode(int data) 
{ 
    Node node = new Node(); 
    node.data = data; 
    node.left = node.right = null; 
    return (node); 
} 
  
// Function to check if the given tree is perfect 
static Boolean CheckPerfectTree(Node root) 
{ 
    Queue<Node > q = new Queue<Node>(); 
  
    // add the root node 
    q.Enqueue(root); 
  
    // Flag to check if leaf nodes
    // have been found 
    int flag = 0; 
  
    while (q.Count > 0)
    { 
        Node temp = q.Peek(); 
        q.Dequeue(); 
  
        // If current node has both 
        // left and right child 
        if (temp.left != null && 
            temp.right != null) 
        { 
            // If a leaf node has already been found 
            // then return false 
            if (flag == 1) 
                return false; 
  
            // If a leaf node has not been discovered yet 
            // add the left and right child in the queue 
            else
            { 
                q.Enqueue(temp.left); 
                q.Enqueue(temp.right); 
            } 
        } 
  
        // If a leaf node is found mark flag as one 
        else if (temp.left == null &&
                 temp.right == null) 
        { 
            flag = 1; 
        } 
  
        // If the current node has only one child 
        // then return false 
        else if (temp.left == null ||
                 temp.right == null) 
            return false; 
    } 
  
    // If the given tree is perfect return true 
    return true; 
} 
  
// Driver code 
public static void Main(String []args)
{ 
    Node root = newNode(7); 
    root.left = newNode(5); 
    root.right = newNode(6); 
    root.left.left = newNode(8); 
    root.left.right = newNode(1); 
    root.right.left = newNode(3); 
    root.right.right = newNode(9); 
    root.right.right.right = newNode(13); 
    root.right.right.left = newNode(10); 
  
    if (CheckPerfectTree(root)) 
        Console.WriteLine("Yes"); 
    else
        Console.WriteLine("No"); 
} 
}
  
// This code is contributed by Rajput-Ji
Output:
No

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.

Структуры данных

РЕКОМЕНДУЕМЫЕ СТАТЬИ

Различия между структурой данных массива и словаря
21 Января, 2023
TCS SDE Sheet: Вопросы и ответы для интервью
12 Января, 2023
Множественные сравнения в очереди приоритетов С++?
6 Января, 2023
Когда использовать Queue over ArrayList в Java?
6 Января, 2023
Введение в связанный список — учебные пособия по структуре данных и алгоритмам
12 Декабря, 2022
Лист Google SDE: вопросы и ответы на собеседовании
12 Декабря, 2022
Введение в массивы — учебные пособия по структуре данных и алгоритмам
12 Декабря, 2022
Как подготовиться к ICFP или Международной конференции по функциональному программированию?
12 Декабря, 2022