Un árbol binario completo es un árbol binario cuyos niveles, excepto el último, están completamente llenos y todas las hojas del último nivel están todas a la izquierda. Puede encontrar más información sobre árboles binarios completos aquí .
Ejemplo:
debajo del árbol hay un árbol binario completo (todos los Nodes hasta el penúltimo Node están llenos y todas las hojas están en el lado izquierdo)
Una solución iterativa para este problema se discute en la publicación a continuación.
Comprobar si un árbol binario determinado está completo o no | Conjunto 1 (usando el recorrido de orden de nivel)
En esta publicación se analiza una solución recursiva.
En la representación de array de un árbol binario, si al Node padre se le asigna un índice de ‘i’ y al hijo izquierdo se le asigna un índice de ‘2*i + 1’ mientras que al hijo de la derecha se le asigna un índice de ‘2*i + 2’. Si representamos el árbol binario anterior como una array con los índices respectivos asignados a los diferentes Nodes del árbol anterior de arriba a abajo y de izquierda a derecha.
Por lo tanto, procedemos de la siguiente manera para verificar si el árbol binario es un árbol binario completo.
- Calcule el número de Nodes (recuento) en el árbol binario.
- Inicie la recursión del árbol binario desde el Node raíz del árbol binario con el índice (i) establecido en 0 y el número de Nodes en el binario (recuento).
- Si el Node actual bajo examen es NULL, entonces el árbol es un árbol binario completo. Devolver verdadero.
- Si el índice (i) del Node actual es mayor o igual que el número de Nodes en el árbol binario (recuento), es decir (i>= recuento), entonces el árbol no es un binario completo. Falso retorno.
- Verifique recursivamente los subárboles izquierdo y derecho del árbol binario para ver si tienen la misma condición. Para el subárbol izquierdo use el índice como (2*i + 1) mientras que para el subárbol derecho use el índice como (2*i + 2).
La complejidad temporal del algoritmo anterior es O(n). A continuación se muestra el código para comprobar si un árbol binario es un árbol binario completo.
Implementación:
C++
/* C++ program to checks if a binary tree complete ot not */
#include<bits/stdc++.h>
#include<stdbool.h>
using namespace std;
/* Tree node structure */
class Node
{
public:
int key;
Node *left, *right;
Node *newNode(char k)
{
Node *node = ( Node*)malloc(sizeof( Node));
node->key = k;
node->right = node->left = NULL;
return node;
}
};
/* Helper function that allocates a new node with the
given key and NULL left and right pointer. */
/* This function counts the number of nodes
in a binary tree */
unsigned int countNodes(Node* root)
{
if (root == NULL)
return (0);
return (1 + countNodes(root->left) +
countNodes(root->right));
}
/* This function checks if the binary tree
is complete or not */
bool isComplete ( Node* root, unsigned int index,
unsigned int number_nodes)
{
// An empty tree is complete
if (root == NULL)
return (true);
// If index assigned to current node is more than
// number of nodes in tree, then tree is not complete
if (index >= number_nodes)
return (false);
// Recur for left and right subtrees
return (isComplete(root->left, 2*index + 1, number_nodes) &&
isComplete(root->right, 2*index + 2, number_nodes));
}
// Driver code
int main()
{
Node n1;
// Let us create tree in the last diagram above
Node* root = NULL;
root = n1.newNode(1);
root->left = n1.newNode(2);
root->right = n1.newNode(3);
root->left->left = n1.newNode(4);
root->left->right = n1.newNode(5);
root->right->right = n1.newNode(6);
unsigned int node_count = countNodes(root);
unsigned int index = 0;
if (isComplete(root, index, node_count))
cout << "The Binary Tree is complete\n";
else
cout << "The Binary Tree is not complete\n";
return (0);
}
// This code is contributed by SoumikMondal
C
/* C program to checks if a binary tree complete ot not */
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
/* Tree node structure */
struct Node
{
int key;
struct Node *left, *right;
};
/* Helper function that allocates a new node with the
given key and NULL left and right pointer. */
struct Node *newNode(char k)
{
struct Node *node = (struct Node*)malloc(sizeof(struct Node));
node->key = k;
node->right = node->left = NULL;
return node;
}
/* This function counts the number of nodes in a binary tree */
unsigned int countNodes(struct Node* root)
{
if (root == NULL)
return (0);
return (1 + countNodes(root->left) + countNodes(root->right));
}
/* This function checks if the binary tree is complete or not */
bool isComplete (struct Node* root, unsigned int index,
unsigned int number_nodes)
{
// An empty tree is complete
if (root == NULL)
return (true);
// If index assigned to current node is more than
// number of nodes in tree, then tree is not complete
if (index >= number_nodes)
return (false);
// Recur for left and right subtrees
return (isComplete(root->left, 2*index + 1, number_nodes) &&
isComplete(root->right, 2*index + 2, number_nodes));
}
// Driver program
int main()
{
// Le us create tree in the last diagram above
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
// Java program to check if binary tree is complete or not
/* Tree node structure */
class Node
{
int data;
Node left, right;
Node(int item) {
data = item;
left = right = null;
}
}
class BinaryTree
{
Node root;
/* This function counts the number of nodes in a binary tree */
int countNodes(Node root)
{
if (root == null)
return (0);
return (1 + countNodes(root.left) + countNodes(root.right));
}
/* This function checks if the binary tree is complete or not */
boolean isComplete(Node root, int index, int number_nodes)
{
// An empty tree is complete
if (root == null)
return true;
// If index assigned to current node is more than
// number of nodes in tree, then tree is not complete
if (index >= number_nodes)
return false;
// Recur for left and right subtrees
return (isComplete(root.left, 2 * index + 1, number_nodes)
&& isComplete(root.right, 2 * index + 2, number_nodes));
}
// Driver program
public static void main(String args[])
{
BinaryTree tree = new BinaryTree();
// Le us create tree in the last diagram above
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");
}
}
// This code is contributed by Mayank Jaiswal
Python3
# Python program to check if a binary tree complete or not
# Tree node structure
class Node:
# Constructor to create a new node
def __init__(self, key):
self.key = key
self.left = None
self.right = None
# This function counts the number of nodes in a binary tree
def countNodes(root):
if root is None:
return 0
return (1+ countNodes(root.left) + countNodes(root.right))
# This function checks if binary tree is complete or not
def isComplete(root, index, number_nodes):
# An empty is complete
if root is None:
return True
# If index assigned to current nodes is more than
# number of nodes in tree, then tree is not complete
if index >= number_nodes :
return False
# Recur for left and right subtrees
return (isComplete(root.left , 2*index+1 , number_nodes)
and isComplete(root.right, 2*index+2, number_nodes)
)
# Driver Program
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")
# This code is contributed by Nikhil Kumar Singh(nickzuck_007)
C#
// C# program to check if binary
// tree is complete or not
using System;
/* Tree node structure */
class Node
{
public int data;
public Node left, right;
public Node(int item)
{
data = item;
left = right = null;
}
}
public class BinaryTree
{
Node root;
/* This function counts the number
of nodes in a binary tree */
int countNodes(Node root)
{
if (root == null)
return (0);
return (1 + countNodes(root.left) +
countNodes(root.right));
}
/* This function checks if the
binary tree is complete or not */
bool isComplete(Node root, int index,
int number_nodes)
{
// An empty tree is complete
if (root == null)
return true;
// If index assigned to current node is more than
// number of nodes in tree, then tree is not complete
if (index >= number_nodes)
return false;
// Recur for left and right subtrees
return (isComplete(root.left, 2 * index + 1, number_nodes)
&& isComplete(root.right, 2 * index + 2, number_nodes));
}
// Driver code
public static void Main()
{
BinaryTree tree = new BinaryTree();
// Let us create tree in the last diagram above
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");
}
}
/* This code is contributed by Rajput-Ji*/
Javascript
<script>
// JavaScript program to check if
// binary tree is complete or not
/* Tree node structure */
class Node {
constructor(val) {
this.data = val;
this.left = null;
this.right = null;
}
}
var root;
/* This function counts the number of
nodes in a binary tree */
function countNodes(root) {
if (root == null)
return (0);
return (1 + countNodes(root.left) + countNodes(root.right));
}
/* This function checks if the binary tree is complete or not */
function isComplete(root , index , number_nodes) {
// An empty tree is complete
if (root == null)
return true;
// If index assigned to current node is more than
// number of nodes in tree, then tree is not complete
if (index >= number_nodes)
return false;
// Recur for left and right subtrees
return (isComplete(root.left, 2 * index + 1, number_nodes)
&& isComplete(root.right, 2 * index + 2, number_nodes));
}
// Driver program
// Le us create tree in the last diagram above
var NewRoot = null;
root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.right = new Node(5);
root.left.left = new Node(4);
root.right.right = new Node(6);
var node_count = countNodes(root);
var index = 0;
if (isComplete(root, index, node_count))
document.write("The binary tree is complete");
else
document.write("The binary tree is not complete");
// This code contributed by umadevi9616
</script>
Producción
The Binary Tree is not complete
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA