Dado un Árbol Binario , la tarea es imprimir todos los niveles de este árbol en un orden transversal de Nivel Límite.
Recorrido de orden de nivel de límite: en este recorrido, el primer elemento del nivel (límite inicial) se imprime primero, seguido del último elemento (límite final). Luego se repite el proceso para el segundo y último segundo elemento, hasta que se haya impreso el nivel completo.
Ejemplos:
Input:
1
/ \
12 13
/ \ / \
11 6 4 11
/ / \ / \
23 7 9 2 4
Output:
1
12 13
11 11 6 4
23 4 7 2 9
Input:
7
/ \
22 19
/ \ \
3 6 13
/ \ \ / \
1 5 8 1 4
/
23
Output:
7
22 19
3 13 6
1 4 5 1 8
23
Acercarse:
- Para imprimir el nivel en el recorrido de orden de nivel de límite, primero debemos hacer el recorrido de orden de nivel del árbol binario para obtener los valores en cada nivel.
- Aquí se utiliza una estructura de datos de cola para almacenar los niveles del árbol mientras se realiza el recorrido de orden de nivel.
- Luego, para cada nivel, el primer elemento del nivel (límite inicial) se imprime primero, seguido del último elemento (límite final). Luego se repite el proceso para el segundo y último segundo elemento, hasta que se haya impreso el nivel completo.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for printing a
// Levels of Binary Tree in a
// start end fashion
#include <bits/stdc++.h>
using namespace std;
// A Tree node
struct Node {
int key;
struct Node *left, *right;
};
// Utility function to create a new node
Node* newNode(int key)
{
Node* temp = new Node;
temp->key = key;
temp->left = temp->right = NULL;
return (temp);
}
// Utility function to print level in
// start end fashion
void printLevelUtil(struct Node* queue[],
int index, int size)
{
while (index < size) {
cout << queue[index++]->key << " "
<< queue[size--]->key << " ";
}
if (index == size) {
cout << queue[index]->key << " ";
}
cout << endl;
}
// Utility function to print level in start
// end fashion in a given Binary tree
void printLevel(struct Node* node,
struct Node* queue[],
int index, int size)
{
// Print root node value
// as a single value in a
// binary tree
cout << queue[index]->key << endl;
// Level order traversal of Tree
while (index < size) {
int curr_size = size;
while (index < curr_size) {
struct Node* temp = queue[index];
if (temp->left != NULL) {
queue[size++] = temp->left;
}
if (temp->right != NULL) {
queue[size++] = temp->right;
}
index++;
}
// Print level in a desire fashion
printLevelUtil(queue, index, size - 1);
}
}
// Function to find total no of nodes
int findSize(struct Node* node)
{
if (node == NULL)
return 0;
return 1
+ findSize(node->left)
+ findSize(node->right);
}
// Function to print level in start end
// fashion in a given binary tree
void printLevelInStartEndFashion(
struct Node* node)
{
int t_size = findSize(node);
struct Node* queue[t_size];
queue[0] = node;
printLevel(node, queue, 0, 1);
}
// Driver Code
int main()
{
/* 10
/ \
13 13
/ \
14 15
/ \ / \
21 22 22 21
/
8 */
// Create Binary Tree as shown
Node* root = newNode(10);
root->left = newNode(13);
root->right = newNode(13);
root->right->left = newNode(14);
root->right->right = newNode(15);
root->right->left->left = newNode(21);
root->right->left->right = newNode(22);
root->right->right->left = newNode(22);
root->right->right->right = newNode(21);
root->right->right->right->left = newNode(8);
// Print Levels In Start End Fashion
printLevelInStartEndFashion(root);
return 0;
}
Java
// Java program for printing a
// Levels of Binary Tree in a
// start end fashion
class GFG{
// A Tree node
static class Node {
int key;
Node left, right;
};
// Utility function to create a new node
static Node newNode(int key)
{
Node temp = new Node();
temp.key = key;
temp.left = temp.right = null;
return (temp);
}
// Utility function to print level in
// start end fashion
static void printLevelUtil(Node queue[],
int index, int size)
{
while (index < size) {
System.out.print(queue[index++].key+ " "
+ queue[size--].key+ " ");
}
if (index == size) {
System.out.print(queue[index].key+ " ");
}
System.out.println();
}
// Utility function to print level in start
// end fashion in a given Binary tree
static void printLevel(Node node,
Node queue[],
int index, int size)
{
// Print root node value
// as a single value in a
// binary tree
System.out.print(queue[index].key +"\n");
// Level order traversal of Tree
while (index < size) {
int curr_size = size;
while (index < curr_size) {
Node temp = queue[index];
if (temp.left != null) {
queue[size++] = temp.left;
}
if (temp.right != null) {
queue[size++] = temp.right;
}
index++;
}
// Print level in a desire fashion
printLevelUtil(queue, index, size - 1);
}
}
// Function to find total no of nodes
static int findSize(Node node)
{
if (node == null)
return 0;
return 1
+ findSize(node.left)
+ findSize(node.right);
}
// Function to print level in start end
// fashion in a given binary tree
static void printLevelInStartEndFashion(
Node node)
{
int t_size = findSize(node);
Node []queue = new Node[t_size];
queue[0] = node;
printLevel(node, queue, 0, 1);
}
// Driver Code
public static void main(String[] args)
{
/* 10
/ \
13 13
/ \
14 15
/ \ / \
21 22 22 21
/
8 */
// Create Binary Tree as shown
Node root = newNode(10);
root.left = newNode(13);
root.right = newNode(13);
root.right.left = newNode(14);
root.right.right = newNode(15);
root.right.left.left = newNode(21);
root.right.left.right = newNode(22);
root.right.right.left = newNode(22);
root.right.right.right = newNode(21);
root.right.right.right.left = newNode(8);
// Print Levels In Start End Fashion
printLevelInStartEndFashion(root);
}
}
// This code is contributed by Princi Singh
Python3
# Python3 program for printing a # Levels of Binary Tree in a # start end fashion # A Tree node class Node: def __init__(self, key): self.key = key self.left = None self.right = None # function to create a # new node def newNode(key): temp = Node(key); return temp; # Utility function to print # level in start end fashion def printLevelUtil(queue, index, size): while (index < size): print(str(queue[index].key) + ' ' + str(queue[size].key), end = ' ') size -= 1 index += 1 if (index == size): print(queue[index].key, end = ' ') print() # Utility function to print # level in start end fashion # in a given Binary tree def printLevel(node, queue, index, size): # Print root node value # as a single value in a # binary tree print(queue[index].key) # Level order traversal # of Tree while (index < size): curr_size = size; while (index < curr_size): temp = queue[index]; if (temp.left != None): queue[size] = temp.left; size += 1 if (temp.right != None): queue[size] = temp.right; size += 1 index += 1 # Print level in a desire # fashion printLevelUtil(queue, index, size - 1); # Function to find total # no of nodes def findSize(node): if (node == None): return 0; return (1 + findSize(node.left) + findSize(node.right)); # Function to print level in start # end fashion in a given binary tree def printLevelInStartEndFashion(node): t_size = findSize(node); queue=[0 for i in range(t_size)]; queue[0] = node; printLevel(node, queue, 0, 1); # Driver code if __name__=="__main__": ''' 10 / \ 13 13 / \ 14 15 / \ / \ 21 22 22 21 / 8 ''' # Create Binary Tree as shown root = newNode(10); root.left = newNode(13); root.right = newNode(13); root.right.left = newNode(14); root.right.right = newNode(15); root.right.left.left = newNode(21); root.right.left.right = newNode(22); root.right.right.left = newNode(22); root.right.right.right = newNode(21); root.right.right.right.left = newNode(8); # Print Levels In Start End Fashion printLevelInStartEndFashion(root); # This code is contributed by Rutvik_56
C#
// C# program for printing a
// Levels of Binary Tree in a
// start end fashion
using System;
class GFG{
// A Tree node
class Node {
public int key;
public Node left, right;
};
// Utility function to create a new node
static Node newNode(int key)
{
Node temp = new Node();
temp.key = key;
temp.left = temp.right = null;
return (temp);
}
// Utility function to print level in
// start end fashion
static void printLevelUtil(Node []queue,
int index, int size)
{
while (index < size) {
Console.Write(queue[index++].key+ " "
+ queue[size--].key+ " ");
}
if (index == size) {
Console.Write(queue[index].key+ " ");
}
Console.WriteLine();
}
// Utility function to print level in start
// end fashion in a given Binary tree
static void printLevel(Node node,
Node []queue,
int index, int size)
{
// Print root node value
// as a single value in a
// binary tree
Console.Write(queue[index].key +"\n");
// Level order traversal of Tree
while (index < size) {
int curr_size = size;
while (index < curr_size) {
Node temp = queue[index];
if (temp.left != null) {
queue[size++] = temp.left;
}
if (temp.right != null) {
queue[size++] = temp.right;
}
index++;
}
// Print level in a desire fashion
printLevelUtil(queue, index, size - 1);
}
}
// Function to find total no of nodes
static int findSize(Node node)
{
if (node == null)
return 0;
return 1
+ findSize(node.left)
+ findSize(node.right);
}
// Function to print level in start end
// fashion in a given binary tree
static void printLevelInStartEndFashion(
Node node)
{
int t_size = findSize(node);
Node []queue = new Node[t_size];
queue[0] = node;
printLevel(node, queue, 0, 1);
}
// Driver Code
public static void Main(String[] args)
{
/* 10
/ \
13 13
/ \
14 15
/ \ / \
21 22 22 21
/
8 */
// Create Binary Tree as shown
Node root = newNode(10);
root.left = newNode(13);
root.right = newNode(13);
root.right.left = newNode(14);
root.right.right = newNode(15);
root.right.left.left = newNode(21);
root.right.left.right = newNode(22);
root.right.right.left = newNode(22);
root.right.right.right = newNode(21);
root.right.right.right.left = newNode(8);
// Print Levels In Start End Fashion
printLevelInStartEndFashion(root);
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// JavaScript program for printing a
// Levels of Binary Tree in a
// start end fashion
// A Tree node
class Node {
constructor()
{
this.key = 0;
this.left = null;
this.right = null;
}
};
// Utility function to create a new node
function newNode(key)
{
var temp = new Node();
temp.key = key;
temp.left = temp.right = null;
return (temp);
}
// Utility function to print level in
// start end fashion
function printLevelUtil(queue, index, size)
{
while (index < size) {
document.write(queue[index++].key+ " "
+ queue[size--].key+ " ");
}
if (index == size) {
document.write(queue[index].key+ " ");
}
document.write("<br>");
}
// Utility function to print level in start
// end fashion in a given Binary tree
function printLevel(node, queue, index, size)
{
// Print root node value
// as a single value in a
// binary tree
document.write(queue[index].key +"<br>");
// Level order traversal of Tree
while (index < size) {
var curr_size = size;
while (index < curr_size) {
var temp = queue[index];
if (temp.left != null) {
queue[size++] = temp.left;
}
if (temp.right != null) {
queue[size++] = temp.right;
}
index++;
}
// Print level in a desire fashion
printLevelUtil(queue, index, size - 1);
}
}
// Function to find total no of nodes
function findSize(node)
{
if (node == null)
return 0;
return 1
+ findSize(node.left)
+ findSize(node.right);
}
// Function to print level in start end
// fashion in a given binary tree
function printLevelInStartEndFashion( node)
{
var t_size = findSize(node);
var queue = Array(t_size);
queue[0] = node;
printLevel(node, queue, 0, 1);
}
// Driver Code
/* 10
/ \
13 13
/ \
14 15
/ \ / \
21 22 22 21
/
8 */
// Create Binary Tree as shown
var root = newNode(10);
root.left = newNode(13);
root.right = newNode(13);
root.right.left = newNode(14);
root.right.right = newNode(15);
root.right.left.left = newNode(21);
root.right.left.right = newNode(22);
root.right.right.left = newNode(22);
root.right.right.right = newNode(21);
root.right.right.right.left = newNode(8);
// Print Levels In Start End Fashion
printLevelInStartEndFashion(root);
</script>
Producción:
10 13 13 14 15 21 21 22 22 8
Publicación traducida automáticamente
Artículo escrito por MohammadMudassir y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA