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