Dado un árbol binario y una clave, escriba una función que devuelva el nivel de la clave.
Por ejemplo, considere el siguiente árbol. Si la clave de entrada es 3, entonces su función debería devolver 1. Si la clave de entrada es 4, entonces su función debería devolver 3. Y para la clave que no está presente en key, entonces su función debería devolver 0.
C++
// C++ program to Get Level of a node in a Binary Tree
#include <bits/stdc++.h>
using namespace std;
/* A tree node structure */
struct node {
int data;
struct node* left;
struct node* right;
};
// Helper function for getLevel(). It returns level of the
// data if data is present in tree, otherwise returns 0.
int getLevelUtil(struct node* node, int data, int level)
{
if (node == NULL)
return 0;
if (node->data == data)
return level;
int downlevel
= getLevelUtil(node->left, data, level + 1);
if (downlevel != 0)
return downlevel;
downlevel = getLevelUtil(node->right, data, level + 1);
return downlevel;
}
/* Returns level of given data value */
int getLevel(struct node* node, int data)
{
return getLevelUtil(node, data, 1);
}
// Utility function to create a new Binary Tree node
struct node* newNode(int data)
{
struct node* temp = new struct node;
temp->data = data;
temp->left = NULL;
temp->right = NULL;
return temp;
}
// Driver Code
int main()
{
struct node* root = new struct node;
int x;
// Constructing tree given in the above figure
root = newNode(3);
root->left = newNode(2);
root->right = newNode(5);
root->left->left = newNode(1);
root->left->right = newNode(4);
for (x = 1; x <= 5; x++) {
int level = getLevel(root, x);
if (level)
cout << "Level of " << x << " is " << level
<< endl;
else
cout << x << "is not present in tree" << endl;
}
getchar();
return 0;
}
// This code is contributed by Aditya Kumar (adityakumar129)
C
// C program to Get Level of a node in a Binary Tree
#include <stdio.h>
#include <stdlib.h>
/* A tree node structure */
typedef struct node {
int data;
struct node* left;
struct node* right;
} node;
// Helper function for getLevel(). It returns level of the
// data if data is present in tree, otherwise returns 0.
int getLevelUtil(node* node, int data, int level)
{
if (node == NULL)
return 0;
if (node->data == data)
return level;
int downlevel
= getLevelUtil(node->left, data, level + 1);
if (downlevel != 0)
return downlevel;
downlevel = getLevelUtil(node->right, data, level + 1);
return downlevel;
}
/* Returns level of given data value */
int getLevel(node* node, int data)
{
return getLevelUtil(node, data, 1);
}
// Utility function to create a new Binary Tree node
node* newNode(int data)
{
node* temp = (node*)malloc(sizeof(node));
temp->data = data;
temp->left = NULL;
temp->right = NULL;
return temp;
}
/* Driver code */
int main()
{
node* root;
int x;
// Constructing tree given in the above figure
root = newNode(3);
root->left = newNode(2);
root->right = newNode(5);
root->left->left = newNode(1);
root->left->right = newNode(4);
for (x = 1; x <= 5; x++) {
int level = getLevel(root, x);
if (level)
printf(" Level of %d is %d\n", x,
getLevel(root, x));
else
printf(" %d is not present in tree \n", x);
}
getchar();
return 0;
}
Java
// Java program to Get Level of a node in a Binary Tree
/* A tree node structure */
class Node {
int data;
Node left, right;
public Node(int d)
{
data = d;
left = right = null;
}
}
class BinaryTree {
Node root;
// Helper function for getLevel(). It returns level of
// the data if data is present in tree, otherwise
// returns 0.
int getLevelUtil(Node node, int data, int level)
{
if (node == null)
return 0;
if (node.data == data)
return level;
int downlevel
= getLevelUtil(node.left, data, level + 1);
if (downlevel != 0)
return downlevel;
downlevel
= getLevelUtil(node.right, data, level + 1);
return downlevel;
}
/* Returns level of given data value */
int getLevel(Node node, int data)
{
return getLevelUtil(node, data, 1);
}
/* Driver code */
public static void main(String[] args)
{
BinaryTree tree = new BinaryTree();
/* Constructing tree given in the above figure */
tree.root = new Node(3);
tree.root.left = new Node(2);
tree.root.right = new Node(5);
tree.root.left.left = new Node(1);
tree.root.left.right = new Node(4);
for (int x = 1; x <= 5; x++) {
int level = tree.getLevel(tree.root, x);
if (level != 0)
System.out.println(
"Level of " + x + " is "
+ tree.getLevel(tree.root, x));
else
System.out.println(
x + " is not present in tree");
}
}
}
// This code is contributed by Aditya Kumar (adityakumar129)
Python3
# Python3 program to Get Level of a
# node in a Binary Tree
# Helper function that allocates a
# new node with the given data and
# None left and right pairs.
class newNode:
# Constructor to create a new node
def __init__(self, data):
self.data = data
self.left = None
self.right = None
# Helper function for getLevel(). It
# returns level of the data if data is
# present in tree, otherwise returns 0
def getLevelUtil(node, data, level):
if (node == None):
return 0
if (node.data == data):
return level
downlevel = getLevelUtil(node.left,
data, level + 1)
if (downlevel != 0):
return downlevel
downlevel = getLevelUtil(node.right,
data, level + 1)
return downlevel
# Returns level of given data value
def getLevel(node, data):
return getLevelUtil(node, data, 1)
# Driver Code
if __name__ == '__main__':
# Let us construct the Tree shown
# in the above figure
root = newNode(3)
root.left = newNode(2)
root.right = newNode(5)
root.left.left = newNode(1)
root.left.right = newNode(4)
for x in range(1, 6):
level = getLevel(root, x)
if (level):
print("Level of", x,
"is", getLevel(root, x))
else:
print(x, "is not present in tree")
# This code is contributed by
# Shubham Singh(SHUBHAMSINGH10)
C#
// C# program to Get Level of a node in a Binary Tree
using System;
/* A tree node structure */
public class Node {
public int data;
public Node left, right;
public Node(int d)
{
data = d;
left = right = null;
}
}
public class BinaryTree {
public Node root;
/* Helper function for getLevel().
It returns level of
the data if data is present in tree,
otherwise returns
0.*/
public virtual int getLevelUtil(Node node, int data,
int level)
{
if (node == null) {
return 0;
}
if (node.data == data) {
return level;
}
int downlevel
= getLevelUtil(node.left, data, level + 1);
if (downlevel != 0) {
return downlevel;
}
downlevel
= getLevelUtil(node.right, data, level + 1);
return downlevel;
}
/* Returns level of given data value */
public virtual int getLevel(Node node, int data)
{
return getLevelUtil(node, data, 1);
}
/* Driver code */
public static void Main(string[] args)
{
BinaryTree tree = new BinaryTree();
/* Constructing tree given in the above figure */
tree.root = new Node(3);
tree.root.left = new Node(2);
tree.root.right = new Node(5);
tree.root.left.left = new Node(1);
tree.root.left.right = new Node(4);
for (int x = 1; x <= 5; x++) {
int level = tree.getLevel(tree.root, x);
if (level != 0) {
Console.WriteLine(
"Level of " + x + " is "
+ tree.getLevel(tree.root, x));
}
else {
Console.WriteLine(
x + " is not present in tree");
}
}
}
}
// This code is contributed by Shrikant13
Javascript
<script>
// Javascript program to Get Level of
// a node in a Binary Tree
/* A tree node structure */
class Node
{
constructor(d) {
this.data = d;
this.left = null;
this.right = null;
}
}
let root;
/* Helper function for getLevel().
It returns level of
the data if data is present in tree,
otherwise returns
0.*/
function getLevelUtil(node, data, level)
{
if (node == null)
return 0;
if (node.data == data)
return level;
let downlevel
= getLevelUtil(node.left, data, level + 1);
if (downlevel != 0)
return downlevel;
downlevel
= getLevelUtil(node.right, data, level + 1);
return downlevel;
}
/* Returns level of given data value */
function getLevel(node, data)
{
return getLevelUtil(node, data, 1);
}
/* Constructing tree given in the above figure */
root = new Node(3);
root.left = new Node(2);
root.right = new Node(5);
root.left.left = new Node(1);
root.left.right = new Node(4);
for (let x = 1; x <= 5; x++)
{
let level = getLevel(root, x);
if (level != 0)
document.write(
"Level of " + x + " is "
+ getLevel(root, x) + "</br>");
else
document.write(
x + " is not present in tree");
}
</script>
C++
// C++ program to print level in which X is present in
// binary tree using STL
#include <bits/stdc++.h>
using namespace std;
// A Binary Tree Node
struct Node {
int data;
struct Node *left, *right;
};
int printLevel(Node* root, int X)
{
Node* node;
// Base Case
if (root == NULL)
return 0;
// Create an empty queue for level order traversal
queue<Node*> q;
// Create a var represent current level of tree
int currLevel = 1;
// Enqueue Root
q.push(root);
while (q.empty() == false) {
int size = q.size();
while (size--) {
node = q.front();
if (node->data == X)
return currLevel;
q.pop();
/* Enqueue left child */
if (node->left != NULL)
q.push(node->left);
/*Enqueue right child */
if (node->right != NULL)
q.push(node->right);
}
currLevel++;
}
return 0;
}
// Utility function to create a new tree node
Node* newNode(int data)
{
Node* temp = new Node;
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
// Driver program to test above functions
int main()
{
// Let us create binary tree shown in above diagram
Node* root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
root->right->left = newNode(7);
root->right->right = newNode(6);
cout << printLevel(root, 6);
return 0;
}
// This code is contributed by Aditya Kumar (adityakumar129)
Java
// Java program to print level in which X is present in
// binary tree
import java.util.LinkedList;
import java.util.Queue;
/* Class to represent Tree node */
class Node {
int data;
Node left, right;
public Node(int item)
{
data = item;
left = null;
right = null;
}
}
/* Class to print Level Order Traversal */
class BinaryTree {
Node root;
// Given a binary tree. Print its nodes in level order
// using array for implementing queue.
// Create a var represent current level of tree
public static int currLevel = 1;
int printLevelOrder(int X)
{
// Create an empty queue for level order traversal
Queue<Node> queue = new LinkedList<Node>();
queue.add(root);
while (!queue.isEmpty()) {
// poll() removes the present head. For more
// information on poll() visit
// https://www.geeksforgeeks.org/queue-poll-method-in-java/
int size = queue.size();
for (int i = 0; i < size; i++) {
Node tempNode = queue.poll();
if (tempNode.data == X)
return currLevel;
/*Enqueue left child */
if (tempNode.left != null)
queue.add(tempNode.left);
/*Enqueue right child */
if (tempNode.right != null)
queue.add(tempNode.right);
}
currLevel++;
}
return currLevel;
}
public static void main(String args[])
{
/* creating a binary tree and entering
the nodes */
BinaryTree tree_level = new BinaryTree();
tree_level.root = new Node(1);
tree_level.root.left = new Node(2);
tree_level.root.right = new Node(3);
tree_level.root.left.left = new Node(4);
tree_level.root.left.right = new Node(5);
tree_level.root.right.left = new Node(7);
tree_level.root.right.right = new Node(6);
System.out.println(
"Level order traversal of binary tree is - "
+ tree_level.printLevelOrder(6));
}
}
// This code is contributed by Aditya Kumar (adityakumar129)
Python3
# Python3 program to print level in which X is present in # binary tree # A node structure class Node: # A utility function to create a new node def __init__(self, key): self.data = key self.left = None self.right = None def printLevel(root, X): # Base Case if root is None: return 0 # Create an empty queue # for level order traversal q = [] #Create a var represent current level of tree currLevel = 1 # Enqueue Root q.append(root) while(len(q) > 0): size = len(q) for i in range(size): node = q.pop(0) if(node.data == X): return currLevel # Enqueue left child if node.left is not None: q.append(node.left) # Enqueue right child if node.right is not None: q.append(node.right) currLevel += 1 return 0 # Driver Program to test above function root = Node(1) root.left = Node(2) root.right = Node(3) root.left.left = Node(4) root.left.right = Node(5) root.right.left = Node(7) root.right.right = Node(6) print(printLevel(root, 6)) # This code is contributed by Abhijeet Kumar(abhijeet19403)
C#
// C# program to print level in which X is present in
// binary tree
using System;
using System.Collections.Generic;
/* Class to represent Tree node */
public class Node {
public int data;
public Node left, right;
public Node(int item)
{
data = item;
left = null;
right = null;
}
}
/* Class to print Level Order Traversal */
public class BinaryTree {
Node root;
/* Function to get the level of the node X*/
int printLevel(int X)
{
Node node;
// Base Case
if (root == null)
return 0;
// Create an empty queue for level order traversal
Queue<Node> q = new Queue<Node>();
// Create a var represent current level of tree
int currLevel = 1;
// Enqueue root
q.Enqueue(root);
while (q.Count != 0) {
int size = q.Count;
while (size-- != 0) {
node = q.Dequeue();
if (node.data == X)
return currLevel;
/*Enqueue left child */
if (node.left != null)
q.Enqueue(node.left);
/*Enqueue right child */
if (node.right != null)
q.Enqueue(node.right);
}
currLevel++;
}
return 0;
}
// Driver code
public static void Main()
{
/* creating a binary tree and entering
the nodes */
BinaryTree tree_level = new BinaryTree();
tree_level.root = new Node(1);
tree_level.root.left = new Node(2);
tree_level.root.right = new Node(3);
tree_level.root.left.left = new Node(4);
tree_level.root.left.right = new Node(5);
tree_level.root.right.left = new Node(7);
tree_level.root.right.right = new Node(6);
Console.WriteLine(tree_level.printLevel(6));
}
}
/* This code contributed by Abhijeet Kumar(abhijeet19403) */
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