Recorrido de izquierda a derecha de todos los niveles del árbol binario

Dado un árbol binario enraizado en el Node 1, la tarea es imprimir los elementos en el siguiente orden definido. 

  1. Primero, imprima todos los elementos del último nivel de una manera alternativa, por ejemplo, primero imprime el elemento más a la izquierda y luego el elemento más a la derecha y continúa así hasta que todos los elementos se atraviesen en el último nivel.
  2. Ahora haz lo mismo con el resto de los niveles.

Ejemplos: 

Input:
            1
          /   \
        2      3
      /   \   /
     4     5 6
Output: 4 6 5 2 3 1
Explanation:
First print all elements of the last 
level which will be printed as follows: 4 6 5
Now tree becomes
       1
     /   \
    2     3
    
Now print elements as 2 3
Now the tree becomes: 1

Input:
        1
      /   \
     2     3
Output: 2 3 1

Enfoque

  • Realice una llamada bfs y almacene todos los Nodes presentes en el nivel i en una array vectorial.
  • También realice un seguimiento del nivel máximo alcanzado en una llamada bfs.
  • Ahora imprima el patrón deseado comenzando desde el nivel máximo hasta 0

A continuación se muestra la implementación del enfoque anterior: 

C++

// C++ implementation
// for the above approach
#include <bits/stdc++.h>
using namespace std;
 
const int sz = 1e5;
int maxLevel = 0;
 
// Adjacency list
// representation of the tree
vector<int> tree[sz + 1];
 
// Boolean array to mark all the
// vertices which are visited
bool vis[sz + 1];
 
// Integer array to store
// the level of each node
int level[sz + 1];
 
// Array of vector where ith index
// stores all the nodes at level i
vector<int> nodes[sz + 1];
 
// Utility function to create an
// edge between two vertices
void addEdge(int a, int b)
{
    // Add a to b's list
    tree[a].push_back(b);
 
    // Add b to a's list
    tree[b].push_back(a);
}
 
// Modified Breadth-First Function
void bfs(int node)
{
  // Create a queue of {child, parent}
  queue<pair<int, int> > qu;
 
  // Push root node in the front of
  // the queue and mark as visited
  qu.push({ node, 0 });
  nodes[0].push_back(node);
  vis[node] = true;
  level[1] = 0;
 
  while (!qu.empty()) {
 
    pair<int, int> p = qu.front();
    // Dequeue a vertex from queue
    qu.pop();
    vis[p.first] = true;
 
    // Get all adjacent vertices of the dequeued
    // vertex s. If any adjacent has not
    // been visited then enqueue it
    for (int child : tree[p.first]) {
        if (!vis[child]) {
            qu.push({ child, p.first });
            level[child] = level[p.first] + 1;
            maxLevel = max(maxLevel, level[child]);
            nodes[level[child]].push_back(child);
        }
    }
  }
}
 
// Function to display
// the pattern
void display()
{
  for (int i = maxLevel; i >= 0; i--) {
    int len = nodes[i].size();
    // Printing all nodes
    // at given level
    for (int j = 0; j < len / 2; j++) {
        cout << nodes[i][j] << " " << nodes[i][len - 1 - j] << " ";
    }
    // If count of nodes
    // at level i is odd
    // print remaining node
    if (len % 2 == 1) {
        cout << nodes[i][len / 2] << " ";
    }
  }
}
 
// Driver code
int main()
{
  // Number of vertices
  int n = 6;
 
  addEdge(1, 2);
  addEdge(1, 3);
  addEdge(2, 4);
  addEdge(2, 5);
  addEdge(3, 6);
 
  // Calling modified bfs function
  bfs(1);
 
  display();
 
  return 0;
}

Java

// Java implementation
// for the above approach
import java.util.*;
 
@SuppressWarnings("unchecked")
 
class GFG{
  
static int sz = 100000;
static int maxLevel = 0;
   
// Adjacency list
// representation of the tree
static ArrayList []tree = new ArrayList[sz + 1];
   
// boolean array to mark all the
// vertices which are visited
static boolean []vis = new boolean[sz + 1];
   
// Integer array to store
// the level of each node
static int []level = new int[sz + 1];
   
// Array of vector where ith index
// stores all the nodes at level i
static ArrayList []nodes = new ArrayList[sz + 1];
   
// Utility function to create an
// edge between two vertices
static void addEdge(int a, int b)
{
     
    // Add a to b's list
    tree[a].add(b);
   
    // Add b to a's list
    tree[b].add(a);
}
 
static class Pair
{
    int Key, Value;
    Pair(int Key, int Value)
    {
        this.Key = Key;
        this.Value = Value;
    }
}
   
// Modified Breadth-Key Function
static void bfs(int node)
{
     
    // Create a queue of {child, parent}
    Queue<Pair> qu = new LinkedList<>();
     
    // Push root node in the front of
    // the queue and mark as visited
    qu.add(new Pair(node, 0));
    nodes[0].add(node);
    vis[node] = true;
    level[1] = 0;
      
    while (qu.size() != 0)
    {
        Pair p = qu.poll();
                                              
        // Dequeue a vertex from queue
        vis[p.Key] = true;
          
        // Get all adjacent vertices of the dequeued
        // vertex s. If any adjacent has not
        // been visited then put it
        for(int child : (ArrayList<Integer>)tree[p.Key])
        {
            if (!vis[child])
            {
                qu.add(new Pair(child, p.Key));
                level[child] = level[p.Key] + 1;
                maxLevel = Math.max(maxLevel,
                                    level[child]);
                nodes[level[child]].add(child);
            }
        }
    }
}
   
// Function to display
// the pattern
static void display()
{
    for(int i = maxLevel; i >= 0; i--)
    {
        int len = nodes[i].size();
         
        // Printing all nodes
        // at given level
        for(int j = 0; j < len / 2; j++)
        {
            System.out.print((int)nodes[i].get(j) + " " +
                             (int)nodes[i].get(len - 1 - j) +
                             " ");
        }
          
        // If count of nodes
        // at level i is odd
        // print remaining node
        if (len % 2 == 1)
        {
            System.out.print(
                (int)nodes[i].get(len / 2) + " ");
        }
    }
}
  
// Driver code
public static void main(String[] args)
{
    for(int i = 0; i < sz + 1; i++)
    {
        tree[i] = new ArrayList();
        nodes[i] = new ArrayList();
        vis[i] = false;
        level[i] = 0;
    }
      
    addEdge(1, 2);
    addEdge(1, 3);
    addEdge(2, 4);
    addEdge(2, 5);
    addEdge(3, 6);
      
    // Calling modified bfs function
    bfs(1);
      
    display();
}
}
 
// This code is contributed by pratham76

Python3

# Python3 implementation
# for the above approach
from collections import deque
 
sz = 10 ** 5
maxLevel = 0
 
# Adjacency list
# representation of the tree
tree = [[] for i in range(sz + 1)]
 
# Boolean array to mark all the
# vertices which are visited
vis = [False] * (sz + 1)
 
# Integer array to store
# the level of each node
level = [0] * (sz + 1)
 
# Array of vector where ith index
# stores all the nodes at level i
nodes = [[] for i in range(sz + 1)]
 
# Utility function to create an
# edge between two vertices
def addEdge(a, b):
     
    global tree
     
    # Add a to b's list
    tree[a].append(b)
 
    # Add b to a's list
    tree[b].append(a)
 
# Modified Breadth-First Function
def bfs(node):
     
    global maxLevel
     
    # Create a queue of {child, parent}
    qu =  deque()
     
    # Push root node in the front of
    # the queue and mark as visited
    qu.append([node, 0 ])
 
    nodes[0].append(node)
    vis[node] = True
    level[1] = 0
 
    while (len(qu) > 0):
 
        p = qu.popleft()
         
        # Dequeue a vertex from queue
        # qu.pop()
        vis[p[0]] = True
 
        # Get all adjacent vertices of the dequeued
        # vertex s. If any adjacent has not
        # been visited then enqueue it
        for child in tree[p[0]]:
            if (not vis[child]):
                qu.append([child, p[0]])
                level[child] = level[p[0]] + 1
                maxLevel = max(maxLevel, level[child])
                nodes[level[child]].append(child)
 
# Function to display
# the pattern
def display():
 
    for i in range(maxLevel, -1, -1):
        lenn = len(nodes[i])
         
        # Printing all nodes
        # at given level
        for j in range(lenn // 2):
            print(nodes[i][j],
                  nodes[i][lenn - 1 - j], end = " ")
             
        # If count of nodes
        # at level i is odd
        # print remaining node
        if (lenn % 2 == 1):
            print(nodes[i][lenn // 2], end = " ")
 
# Driver code
if __name__ == '__main__':
 
    # Number of vertices
    n = 6
 
    addEdge(1, 2)
    addEdge(1, 3)
    addEdge(2, 4)
    addEdge(2, 5)
    addEdge(3, 6)
     
    # Calling modified bfs function
    bfs(1)
 
    display()
 
# This code is contributed by mohit kumar 29

C#

// C# implementation
// for the above approach
using System;
using System.Collections.Generic;
using System.Collections;
 
class GFG{
 
static int sz = 100000;
static int maxLevel = 0;
  
// Adjacency list
// representation of the tree
static ArrayList []tree = new ArrayList[sz + 1];
  
// Boolean array to mark all the
// vertices which are visited
static bool []vis = new bool[sz + 1];
  
// Integer array to store
// the level of each node
static int []level = new int[sz + 1];
  
// Array of vector where ith index
// stores all the nodes at level i
static ArrayList []nodes = new ArrayList[sz + 1];
  
// Utility function to create an
// edge between two vertices
static void addEdge(int a, int b)
{
     
    // Add a to b's list
    tree[a].Add(b);
  
    // Add b to a's list
    tree[b].Add(a);
}
  
// Modified Breadth-First Function
static void bfs(int node)
{
     
    // Create a queue of {child, parent}
    Queue qu = new Queue();
     
    // Push root node in the front of
    // the queue and mark as visited
    qu.Enqueue(new KeyValuePair<int, int>(node, 0));
    nodes[0].Add(node);
    vis[node] = true;
    level[1] = 0;
     
    while(qu.Count != 0)
    {
     
        KeyValuePair<int,
                     int> p = (KeyValuePair<int,
                                            int>)qu.Peek();
                                             
        // Dequeue a vertex from queue
        qu.Dequeue();
        vis[p.Key] = true;
         
        // Get all adjacent vertices of the dequeued
        // vertex s. If any adjacent has not
        // been visited then enqueue it
        foreach(int child in tree[p.Key])
        {
            if (!vis[child])
            {
                qu.Enqueue(new KeyValuePair<int, int>(
                           child, p.Key));
                level[child] = level[p.Key] + 1;
                maxLevel = Math.Max(maxLevel, level[child]);
                nodes[level[child]].Add(child);
            }
        }
    }
}
  
// Function to display
// the pattern
static void display()
{
     
    for(int i = maxLevel; i >= 0; i--)
    {
        int len = nodes[i].Count;
         
        // Printing all nodes
        // at given level
        for(int j = 0; j < len / 2; j++)
        {
            Console.Write((int)nodes[i][j] + " " +
                          (int)nodes[i][len - 1 - j] +
                           " ");
        }
         
        // If count of nodes
        // at level i is odd
        // print remaining node
        if (len % 2 == 1)
        {
            Console.Write((int)nodes[i][len / 2] + " ");
        }
    }
}
 
// Driver code
public static void Main(string[] args)
{
    for(int i = 0; i < sz + 1; i++)
    {
        tree[i] = new ArrayList();
        nodes[i] = new ArrayList();
        vis[i] = false;
        level[i] = 0;
    }
     
    addEdge(1, 2);
    addEdge(1, 3);
    addEdge(2, 4);
    addEdge(2, 5);
    addEdge(3, 6);
     
    // Calling modified bfs function
    bfs(1);
     
    display();
}
}
 
// This code is contributed by rutvik_56

Javascript

<script>
 
// JavaScript implementation
// for the above approach
 
let sz = 100000;
let maxLevel = 0;
 
// Adjacency list
// representation of the tree
let tree = new Array(sz + 1);
 
// boolean array to mark all the
// vertices which are visited
let vis = new Array(sz + 1);
 
// Integer array to store
// the level of each node
let level = new Array(sz + 1);
 
// Array of vector where ith index
// stores all the nodes at level i
let nodes = new Array(sz + 1);
 
// Utility function to create an
// edge between two vertices
function addEdge(a,b)
{
    // Add a to b's list
    tree[a].push(b);
    
    // Add b to a's list
    tree[b].push(a);
}
 
// Modified Breadth-Key Function
function bfs(node)
{
    let qu=[];
    // Push root node in the front of
    // the queue and mark as visited
    qu.push([node, 0]);
    nodes[0].push(node);
    vis[node] = true;
    level[1] = 0;
       
    while (qu.length != 0)
    {
        let p = qu.shift();
                                               
        // Dequeue a vertex from queue
        vis[p[0]] = true;
           
        // Get all adjacent vertices of the dequeued
        // vertex s. If any adjacent has not
        // been visited then put it
        for(let child=0;child<tree[p[0]].length;child++)
        {
            if (!vis[tree[p[0]][child]])
            {
                 
                qu.push([tree[p[0]][child], p[0]]);
                level[tree[p[0]][child]] = level[p[0]] + 1;
                maxLevel = Math.max(maxLevel,
                                    level[tree[p[0]][child]]);
                                     
                 
                nodes[level[tree[p[0]][child]]].
                push(tree[p[0]][child]);
                 
            }
        }
    }
}
 
// Function to display
// the pattern
function display()
{
     
    for(let i = maxLevel; i >= 0; i--)
    {
        let len = nodes[i].length;  
        // Printing all nodes
        // at given level
        for(let j = 0; j < Math.floor(len / 2); j++)
        {
            document.write(nodes[i][j] + " " +
                             nodes[i][len - 1 - j] +
                             " ");
        }
           
        // If count of nodes
        // at level i is odd
        // print remaining node
        if (len % 2 == 1)
        {
            document.write(
                nodes[i][Math.floor(len / 2)] + " ");
        }
    }
}
 
// Driver code
for(let i = 0; i < sz + 1; i++)
    {
        tree[i] = [];
        nodes[i] = [];
        vis[i] = false;
        level[i] = 0;
    }
       
    addEdge(1, 2);
    addEdge(1, 3);
    addEdge(2, 4);
    addEdge(2, 5);
    addEdge(3, 6);
       
    // Calling modified bfs function
    bfs(1);
       
    display();
 
 
// This code is contributed by patel2127
 
</script>
Producción: 

4 6 5 2 3 1

 

Complejidad temporal : O(V + E), donde V es el número total de vértices y E es el número total de aristas.  
Espacio Auxiliar : O(V).  

Publicación traducida automáticamente

Artículo escrito por chsadik99 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *