Dado un árbol binario, escriba una función para verificar si el árbol binario dado es un árbol binario perfecto o no.
Un árbol binario es un árbol binario perfecto en el que todos los Nodes internos tienen dos hijos y todas las hojas están al mismo nivel.
Ejemplos:
C++
// C++ program to check whether a given
// Binary Tree is Perfect or not
#include<bits/stdc++.h>
/* Tree node structure */
struct Node
{
int key;
struct Node *left, *right;
};
// Returns depth of leftmost leaf.
int findADepth(Node *node)
{
int d = 0;
while (node != NULL)
{
d++;
node = node->left;
}
return d;
}
/* This function tests if a binary tree is perfect
or not. It basically checks for two things :
1) All leaves are at same level
2) All internal nodes have two children */
bool isPerfectRec(struct Node* root, int d, int level = 0)
{
// An empty tree is perfect
if (root == NULL)
return true;
// If leaf node, then its depth must be same as
// depth of all other leaves.
if (root->left == NULL && root->right == NULL)
return (d == level+1);
// If internal node and one child is empty
if (root->left == NULL || root->right == NULL)
return false;
// Left and right subtrees must be perfect.
return isPerfectRec(root->left, d, level+1) &&
isPerfectRec(root->right, d, level+1);
}
// Wrapper over isPerfectRec()
bool isPerfect(Node *root)
{
int d = findADepth(root);
return isPerfectRec(root, d);
}
/* Helper function that allocates a new node with the
given key and NULL left and right pointer. */
struct Node *newNode(int k)
{
struct Node *node = new Node;
node->key = k;
node->right = node->left = NULL;
return node;
}
// Driver Program
int main()
{
struct Node* root = NULL;
root = newNode(10);
root->left = newNode(20);
root->right = newNode(30);
root->left->left = newNode(40);
root->left->right = newNode(50);
root->right->left = newNode(60);
root->right->right = newNode(70);
if (isPerfect(root))
printf("Yes\n");
else
printf("No\n");
return(0);
}
Java
// Java program to check whether a given
// Binary Tree is Perfect or not
class GfG {
/* Tree node structure */
static class Node
{
int key;
Node left, right;
}
// Returns depth of leftmost leaf.
static int findADepth(Node node)
{
int d = 0;
while (node != null)
{
d++;
node = node.left;
}
return d;
}
/* This function tests if a binary tree is perfect
or not. It basically checks for two things :
1) All leaves are at same level
2) All internal nodes have two children */
static boolean isPerfectRec(Node root, int d, int level)
{
// An empty tree is perfect
if (root == null)
return true;
// If leaf node, then its depth must be same as
// depth of all other leaves.
if (root.left == null && root.right == null)
return (d == level+1);
// If internal node and one child is empty
if (root.left == null || root.right == null)
return false;
// Left and right subtrees must be perfect.
return isPerfectRec(root.left, d, level+1) && isPerfectRec(root.right, d, level+1);
}
// Wrapper over isPerfectRec()
static boolean isPerfect(Node root)
{
int d = findADepth(root);
return isPerfectRec(root, d, 0);
}
/* Helper function that allocates a new node with the
given key and NULL left and right pointer. */
static Node newNode(int k)
{
Node node = new Node();
node.key = k;
node.right = null;
node.left = null;
return node;
}
// Driver Program
public static void main(String args[])
{
Node root = null;
root = newNode(10);
root.left = newNode(20);
root.right = newNode(30);
root.left.left = newNode(40);
root.left.right = newNode(50);
root.right.left = newNode(60);
root.right.right = newNode(70);
if (isPerfect(root) == true)
System.out.println("Yes");
else
System.out.println("No");
}
}
Python3
# Python3 program to check whether a
# given Binary Tree is Perfect or not
# Helper class that allocates a new
# node with the given key and None
# left and right pointer.
class newNode:
def __init__(self, k):
self.key = k
self.right = self.left = None
# Returns depth of leftmost leaf.
def findADepth(node):
d = 0
while (node != None):
d += 1
node = node.left
return d
# This function tests if a binary tree
# is perfect or not. It basically checks
# for two things :
# 1) All leaves are at same level
# 2) All internal nodes have two children
def isPerfectRec(root, d, level = 0):
# An empty tree is perfect
if (root == None):
return True
# If leaf node, then its depth must
# be same as depth of all other leaves.
if (root.left == None and root.right == None):
return (d == level + 1)
# If internal node and one child is empty
if (root.left == None or root.right == None):
return False
# Left and right subtrees must be perfect.
return (isPerfectRec(root.left, d, level + 1) and
isPerfectRec(root.right, d, level + 1))
# Wrapper over isPerfectRec()
def isPerfect(root):
d = findADepth(root)
return isPerfectRec(root, d)
# Driver Code
if __name__ == '__main__':
root = None
root = newNode(10)
root.left = newNode(20)
root.right = newNode(30)
root.left.left = newNode(40)
root.left.right = newNode(50)
root.right.left = newNode(60)
root.right.right = newNode(70)
if (isPerfect(root)):
print("Yes")
else:
print("No")
# This code is contributed by pranchalK
C#
// C# program to check whether a given
// Binary Tree is Perfect or not
using System;
class GfG
{
/* Tree node structure */
class Node
{
public int key;
public Node left, right;
}
// Returns depth of leftmost leaf.
static int findADepth(Node node)
{
int d = 0;
while (node != null)
{
d++;
node = node.left;
}
return d;
}
/* This function tests if a binary tree is perfect
or not. It basically checks for two things :
1) All leaves are at same level
2) All internal nodes have two children */
static bool isPerfectRec(Node root,
int d, int level)
{
// An empty tree is perfect
if (root == null)
return true;
// If leaf node, then its depth must be same as
// depth of all other leaves.
if (root.left == null && root.right == null)
return (d == level+1);
// If internal node and one child is empty
if (root.left == null || root.right == null)
return false;
// Left and right subtrees must be perfect.
return isPerfectRec(root.left, d, level+1) &&
isPerfectRec(root.right, d, level+1);
}
// Wrapper over isPerfectRec()
static bool isPerfect(Node root)
{
int d = findADepth(root);
return isPerfectRec(root, d, 0);
}
/* Helper function that allocates a new node with the
given key and NULL left and right pointer. */
static Node newNode(int k)
{
Node node = new Node();
node.key = k;
node.right = null;
node.left = null;
return node;
}
// Driver code
public static void Main()
{
Node root = null;
root = newNode(10);
root.left = newNode(20);
root.right = newNode(30);
root.left.left = newNode(40);
root.left.right = newNode(50);
root.right.left = newNode(60);
root.right.right = newNode(70);
if (isPerfect(root) == true)
Console.WriteLine("Yes");
else
Console.WriteLine("No");
}
}
/* This code is contributed by Rajput-Ji*/
Javascript
<script>
// Javascript program to check whether a given
// Binary Tree is Perfect or not
/* Tree node structure */
class Node
{
constructor()
{
this.key = 0;
this.left = null;
this.right = null;
}
}
// Returns depth of leftmost leaf.
function findADepth(node)
{
var d = 0;
while (node != null)
{
d++;
node = node.left;
}
return d;
}
/* This function tests if a binary tree is perfect
or not. It basically checks for two things :
1) All leaves are at same level
2) All internal nodes have two children */
function isPerfectRec(root, d, level)
{
// An empty tree is perfect
if (root == null)
return true;
// If leaf node, then its depth must be same as
// depth of all other leaves.
if (root.left == null && root.right == null)
return (d == level + 1);
// If internal node and one child is empty
if (root.left == null || root.right == null)
return false;
// Left and right subtrees must be perfect.
return isPerfectRec(root.left, d, level + 1) &&
isPerfectRec(root.right, d, level + 1);
}
// Wrapper over isPerfectRec()
function isPerfect(root)
{
var d = findADepth(root);
return isPerfectRec(root, d, 0);
}
/* Helper function that allocates a new node with the
given key and NULL left and right pointer. */
function newNode(k)
{
var node = new Node();
node.key = k;
node.right = null;
node.left = null;
return node;
}
// Driver code
var root = null;
root = newNode(10);
root.left = newNode(20);
root.right = newNode(30);
root.left.left = newNode(40);
root.left.right = newNode(50);
root.right.left = newNode(60);
root.right.right = newNode(70);
if (isPerfect(root) == true)
document.write("Yes");
else
document.write("No");
// This code is contributed by noob2000
</script>
C++
// C++ program to check whether a
// given Binary Tree is Perfect or not
#include <bits/stdc++.h>
using namespace std;
// Helper class that allocates a new
// node with the given key and None
// left and right pointer.
class newNode{
public:
int key;
newNode*right,*left;
newNode(int k){
this->key = k;
this->right = this->left = NULL;
}
};
// This functions gets the size of binary tree
// Basically, the number of nodes this binary tree has
int getLength(newNode* root){
if(root == NULL)
return 0;
return 1 + getLength(root->left) + getLength(root->right);
}
// Returns True if length of binary tree is a power of 2 else False
bool isPerfect(newNode* root){
int length = getLength(root);
return length & (length+1) == 0;
}
int main()
{
newNode* root = new newNode(10);
root->left = new newNode(20);
root->right = new newNode(30);
root->left->left = new newNode(40);
root->left->right = new newNode(50);
root->right->left = new newNode(60);
root->right->right = new newNode(70);
if (isPerfect(root))
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
}
// This code is contributed by shinjanpatra
Java
/*package whatever //do not write package name here */
import java.io.*;
class GFG
{
// Java program to check whether a
// given Binary Tree is Perfect or not
// Helper class that allocates a new
// node with the given key and None
// left and right pointer.
static class newNode{
public int key;
public newNode right,left;
public newNode(int k){
this.key = k;
this.right = this.left = null;
}
};
// This functions gets the size of binary tree
// Basically, the number of nodes this binary tree has
static int getLength(newNode root){
if(root == null)
return 0;
return 1 + getLength(root.left) + getLength(root.right);
}
// Returns True if length of binary tree is a power of 2 else False
static boolean isPerfect(newNode root){
int length = getLength(root);
return (length & (length+1))== 0;
}
/* Driver program to test above function*/
public static void main(String args[])
{
newNode root = new newNode(10);
root.left = new newNode(20);
root.right = new newNode(30);
root.left.left = new newNode(40);
root.left.right = new newNode(50);
root.right.left = new newNode(60);
root.right.right = new newNode(70);
if (isPerfect(root))
System.out.println("Yes");
else
System.out.println("No");
}
}
// This code is contributed by shinjanpatra
Python3
# Python3 program to check whether a
# given Binary Tree is Perfect or not
# Helper class that allocates a new
# node with the given key and None
# left and right pointer.
class newNode:
def __init__(self, k):
self.key = k
self.right = self.left = None
#This functions gets the size of binary tree
#Basically, the number of nodes this binary tree has
def getLength(root):
if root == None:
return 0
return 1 + getLength(root.left) + getLength(root.right)
#Returns True if length of binary tree is a power of 2 else False
def isPerfect(root):
length = getLength(root)
return length & (length+1) == 0
# Driver Code
if __name__ == '__main__':
root = None
root = newNode(10)
root.left = newNode(20)
root.right = newNode(30)
root.left.left = newNode(40)
root.left.right = newNode(50)
root.right.left = newNode(60)
root.right.right = newNode(70)
if (isPerfect(root)):
print("Yes")
else:
print("No")
# This code is contributed by beardedowl
Javascript
<script>
// JavaScript program to check whether a
// given Binary Tree is Perfect or not
// Helper class that allocates a new
// node with the given key and None
// left and right pointer.
class newNode{
constructor(k){
this.key = k
this.right = this.left = null
}
}
// This functions gets the size of binary tree
// Basically, the number of nodes this binary tree has
function getLength(root){
if(root == null)
return 0
return 1 + getLength(root.left) + getLength(root.right)
}
// Returns True if length of binary tree is a power of 2 else False
function isPerfect(root){
let length = getLength(root)
return length & (length+1) == 0
}
// Driver Code
let root = null
root = new newNode(10)
root.left = new newNode(20)
root.right = new newNode(30)
root.left.left = new newNode(40)
root.left.right = new newNode(50)
root.right.left = new newNode(60)
root.right.right = new newNode(70)
if (isPerfect(root))
document.write("Yes")
else
document.write("No")
// This code is contributed by shinjanpatra
</script>
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