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