Обход влево-вправо по всем уровням двоичного дерева

Опубликовано: 5 Января, 2022

Учитывая двоичное дерево с корнем в узле 1, задача состоит в том, чтобы распечатать элементы в следующем определенном порядке.

Во-первых, распечатайте все элементы последнего уровня альтернативным способом, например, сначала вы распечатаете крайний левый элемент, а затем крайний правый элемент и продолжайте так, пока все элементы не будут пройдены на последнем уровне.
Теперь проделайте то же самое с остальными уровнями.

Примеры:

 Вход:
            1
          / 
        2 3
      /  /
     4 5 6
Выход: 4 6 5 2 3 1
Объяснение:
Сначала распечатайте все элементы последнего 
уровень, который будет напечатан следующим образом: 4 6 5
Теперь дерево становится
       1
     / 
    2 3
    
Теперь напечатайте элементы как 2 3
Теперь дерево становится: 1

Вход:
        1
      / 
     2 3
Выход: 2 3 1

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Подход :

Выполните вызов bfs и сохраните все узлы, присутствующие на уровне i, в векторном массиве.
Также следите за максимальным уровнем, достигнутым при вызове bfs.
Теперь распечатайте желаемый узор, начиная с максимального уровня до 0.

Ниже представлена реализация описанного выше подхода:

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 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
        # prremaining 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 
                    
                                            Статьи
                                            C++
                                            Олимпиады по программированию
                                            Структуры данных
                                    
РЕКОМЕНДУЕМЫЕ СТАТЬИОнлайн-обменники: быстрый и удобный способ конвертации активов в современном мире
17 Апреля, 2024
Лучшие онлайн-курсы по WordPress: рейтинг 2024
29 Марта, 2024
Для кого буду полезны услуги SMS-центра
24 Марта, 2024
Что такое экспертиза исходного кода и как ее проводят?
3 Марта, 2024
Как добавить деньги на счет аккаунта Steam через криптовалюту
20 Февраля, 2024
Заказать докторскую диссертацию на заказ
30 Января, 2024
Купить лайки в ВК: зачем, сколько и где
19 Января, 2024
Как добавить деньги на свой аккаунт в Steam и начать покупать игры и контент
12 Января, 2024

    


        
                    < PROGLER >

                

                    Общее
Контакты
Политика конфиденциальности

                    Обучение
Блог

                

                © progler.ru 2024. Все права защищены.
            

    