Dado un árbol n-ario, la tarea es verificar si el árbol dado es binario o no.
Ejemplos:
Input: A / \ B C / \ \ D E F Output: Yes Input: A / | \ B C D \ F Output: No
Enfoque: cada Node en un árbol binario puede tener como máximo 2 hijos. Entonces, para cada Node del árbol dado, cuente la cantidad de hijos y si para algún Node el conteo excede 2, imprima No else, imprima Sí .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; // Structure of a node // of an n-ary tree struct Node { char key; vector<Node*> child; }; // Utility function to create // a new tree node Node* newNode(int key) { Node* temp = new Node; temp->key = key; return temp; } // Function that returns true // if the given tree is binary bool isBinaryTree(struct Node* root) { // Base case if (!root) return true; // Count will store the number of // children of the current node int count = 0; for (int i = 0; i < root->child.size(); i++) { // If any child of the current node doesn't // satisfy the condition of being // a binary tree node if (!isBinaryTree(root->child[i])) return false; // Increment the count of children count++; // If current node has more // than 2 children if (count > 2) return false; } return true; } // Driver code int main() { Node* root = newNode('A'); (root->child).push_back(newNode('B')); (root->child).push_back(newNode('C')); (root->child[0]->child).push_back(newNode('D')); (root->child[0]->child).push_back(newNode('E')); (root->child[1]->child).push_back(newNode('F')); if (isBinaryTree(root)) cout << "Yes"; else cout << "No"; return 0; }
Java
// Java implementation of the approach import java.util.*; class GFG { // Structure of a node // of an n-ary tree static class Node { int key; Vector<Node> child = new Vector<Node>(); }; // Utility function to create // a new tree node static Node newNode(int key) { Node temp = new Node(); temp.key = key; return temp; } // Function that returns true // if the given tree is binary static boolean isBinaryTree(Node root) { // Base case if (root == null) return true; // Count will store the number of // children of the current node int count = 0; for (int i = 0; i < root.child.size(); i++) { // If any child of the current node doesn't // satisfy the condition of being // a binary tree node if (!isBinaryTree(root.child.get(i))) return false; // Increment the count of children count++; // If current node has more // than 2 children if (count > 2) return false; } return true; } // Driver code public static void main(String[] args) { Node root = newNode('A'); (root.child).add(newNode('B')); (root.child).add(newNode('C')); (root.child.get(0).child).add(newNode('D')); (root.child.get(0).child).add(newNode('E')); (root.child.get(1).child).add(newNode('F')); if (isBinaryTree(root)) System.out.println("Yes"); else System.out.println("No"); } } // This code is contributed by PrinciRaj1992
Python3
# Python implementation of the approach # Structure of a node of an n-ary tree class Node: def __init__(self,key): self.key = key self.child = [] # Utility function to create # a new tree node def newNode(key): temp = Node(key) return temp # Function that returns true # if the given tree is binary def isBinaryTree(root): # Base case if (root == None): return True # Count will store the number of # children of the current node count = 0 for i in range(len(root.child)): # If any child of the current node doesn't # satisfy the condition of being # a binary tree node if (isBinaryTree(root.child[i]) == False): return False # Increment the count of children count += 1 # If current node has more # than 2 children if (count > 2): return False return True # Driver code root = newNode('A') (root.child).append(newNode('B')) (root.child).append(newNode('C')) (root.child[0].child).append(newNode('D')) (root.child[0].child).append(newNode('E')) (root.child[1].child).append(newNode('F')) if (isBinaryTree(root)): print("Yes") else: print("No") # This code is contributed by shinjanpatra
C#
// C# implementation of the above approach using System; using System.Collections.Generic; class GFG { // Structure of a node // of an n-ary tree public class Node { public int key; public List<Node> child = new List<Node>(); }; // Utility function to create // a new tree node static Node newNode(int key) { Node temp = new Node(); temp.key = key; return temp; } // Function that returns true // if the given tree is binary static bool isBinaryTree(Node root) { // Base case if (root == null) return true; // Count will store the number of // children of the current node int count = 0; for (int i = 0; i < root.child.Count; i++) { // If any child of the current node doesn't // satisfy the condition of being // a binary tree node if (!isBinaryTree(root.child[i])) return false; // Increment the count of children count++; // If current node has more // than 2 children if (count > 2) return false; } return true; } // Driver code public static void Main(String[] args) { Node root = newNode('A'); (root.child).Add(newNode('B')); (root.child).Add(newNode('C')); (root.child[0].child).Add(newNode('D')); (root.child[0].child).Add(newNode('E')); (root.child[1].child).Add(newNode('F')); if (isBinaryTree(root)) Console.WriteLine("Yes"); else Console.WriteLine("No"); } } // This code is contributed by 29AjayKumar
Javascript
<script> // Javascript implementation of the approach // Structure of a node of an n-ary tree class Node { constructor(key) { this.key = key; this.child = []; } } // Utility function to create // a new tree node function newNode(key) { let temp = new Node(key); return temp; } // Function that returns true // if the given tree is binary function isBinaryTree(root) { // Base case if (root == null) return true; // Count will store the number of // children of the current node let count = 0; for(let i = 0; i < root.child.length; i++) { // If any child of the current node doesn't // satisfy the condition of being // a binary tree node if (!isBinaryTree(root.child[i])) return false; // Increment the count of children count++; // If current node has more // than 2 children if (count > 2) return false; } return true; } // Driver code let root = newNode('A'); (root.child).push(newNode('B')); (root.child).push(newNode('C')); (root.child[0].child).push(newNode('D')); (root.child[0].child).push(newNode('E')); (root.child[1].child).push(newNode('F')); if (isBinaryTree(root)) document.write("Yes"); else document.write("No"); // This code is contributed by divyeshrabadiya07 </script>
Producción:
Yes