Построить двоичное дерево из BST так, чтобы при обходе порядка уровней печатались отсортированные данные

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

Постройте двоичное дерево из заданного двоичного дерева поиска так, чтобы при обходе его уровня выводились отсортированные данные.

Примеры:

Input:

Output: 1 2 3
Input:

Output: 1 2 3 4 5

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

Подход:

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

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

C ++

 // C++ implementation of the approach
 #include <bits/stdc++.h>
 using namespace std;
 
// Structure to hold the contents
 // of the new node
 struct node {
    data; int
    node *left, *right;
 }* root1 = NULL;
 
// Helper function to add and
 // return the newly added node
 node* add( data) int
 {
    node* newnode = new node;
    newnode->data = data;
    newnode->left = newnode->right = NULL;
    return newnode;
 }
 
// Function to add a node to the
 // Binary Tree in the level order
 void addinBT( data) int
 {
 
    // If it is the first node
    // to be added then make
    // it the root node
    if (root1 == NULL)
        root1 = add(data);
    else {
        queue<node*> Q;
        Q.push(root1);
        while (!Q.empty()) {
 
            // Get and remove the front
            node* temp = Q.front();
            Q.pop();
 
            // If the left child of the current
            // node is null then create the new
            // node here and break
            if (temp->left == NULL) {
                temp->left = add(data);
                break ;
            }
            else
                Q.push(temp->left);
 
            // If the right child of the current
            // node is null then create the new
            // node here and break
            if (temp->right == NULL) {
                temp->right = add(data);
                break ;
            }
            else
                Q.push(temp->right);
        }
    }
 }
 
// Function to add a node to
 // the Binary Search tree
 node* addinBST(node* root, data) int
 {
 
    // If the current node is null
    // then create a new node here
    // with the given data
    if (root == NULL)
        root = add(data);
 
    // If the data is smaller than the
    // current node's data then recur
    // for the left sub-tree
    else if (data < root->data)
        root->left = addinBST(root->left, data);
 
    // Else recur for the right sub-tree
    else
        root->right = addinBST(root->right, data);
    return root;
 }
 
// Function to perform a level order
 // insertion in the Binary Tree from
 // the given Binary Search tree
 void addinorder(node* root)
 {
    if (root == NULL)
        return ;
    addinorder(root->left);
    addinBT(root->data);
    addinorder(root->right);
 }
 
// Function to print the level order
 // traversal of the binary tree
 void printlvl()
 {
    queue<node*> Q;
 
    // Push root to the queue
    Q.push(root1);
    while (!Q.empty()) {
 
        // Get the front
        node* temp = Q.front();
 
        // Remove the front
        Q.pop();
 
        // Print the data
        cout << temp->data << " " ;
 
        // Push the left child
        if (temp->left != NULL)
            Q.push(temp->left);
 
        // Push the right child
        if (temp->right != NULL)
            Q.push(temp->right);
    }
 }
 
// Driver code
 int main()
 {
    // Create the Binary Search Tree
    node* root = NULL;
    root = addinBST(root, 1);
    root = addinBST(root, 2);
    root = addinBST(root, 3);
    root = addinBST(root, 4);
    root = addinBST(root, 5);
 
    // Add nodes of the Binary Search
    // Tree to the Binary Tree
    addinorder(root);
 
    // Print the level order traversal
    // of the Binary Tree
    printlvl();
 
    return 0;
 }

Джава

 // Java implementation of the approach
 import java.util.*;
 
class GFG
 {
 
// Structure to hold the contents
 // of the new node
 node static class
 {
    data; int
    node left, right;
 }
 static node root1 = null ;
 
// Helper function to add and
 // return the newly added node
 static node add( data) int
 {
    node newnode = new node();
    newnode.data = data;
    newnode.left = newnode.right = null ;
    return newnode;
 }
 
// Function to add a node to the
 // Binary Tree in the level order
 static void addinBT( data) int
 {
 
    // If it is the first node
    // to be added then make
    // it the root node
    if (root1 == null )
        root1 = add(data);
    else
    {
        Queue<node> Q = new LinkedList<>();
        Q.add(root1);
        while (!Q.isEmpty())
        {
 
            // Get and remove the front
            node temp = Q.peek();
            Q.remove();
 
            // If the left child of the current
            // node is null then create the new
            // node here and break
            if (temp.left == null )
            {
                temp.left = add(data);
                break ;
            }
            else
                Q.add(temp.left);
 
            // If the right child of the current
            // node is null then create the new
            // node here and break
            if (temp.right == null )
            {
                temp.right = add(data);
                break ;
            }
            else
                Q.add(temp.right);
        }
    }
 }
 
// Function to add a node to
 // the Binary Search tree
 static node addinBST(node root, data) int
 {
 
    // If the current node is null
    // then create a new node here
    // with the given data
    if (root == null )
        root = add(data);
 
    // If the data is smaller than the
    // current node's data then recur
    // for the left sub-tree
    else if (data < root.data)
        root.left = addinBST(root.left, data);
 
    // Else recur for the right sub-tree
    else
        root.right = addinBST(root.right,
                                   data);
    return root;
 }
 
// Function to perform a level order
 // insertion in the Binary Tree from
 // the given Binary Search tree
 static void addinorder(node root)
 {
    if (root == null )
        return ;
    addinorder(root.left);
    addinBT(root.data);
    addinorder(root.right);
 }
 
// Function to print the level order
 // traversal of the binary tree
 static void printlvl()
 {
    Queue<node> Q = new LinkedList<>();
 
    // Push root to the queue
    Q.add(root1);
    while (!Q.isEmpty())
    {
 
        // Get the front
        node temp = Q.peek();
 
        // Remove the front
        Q.remove();
 
        // Print the data
        System.out.print(temp.data + " " );
 
        // Push the left child
        if (temp.left != null )
            Q.add(temp.left);
 
        // Push the right child
        if (temp.right != null )
            Q.add(temp.right);
    }
 }
 
// Driver code
 public static void main(String[] args)
 {
    // Create the Binary Search Tree
    node root = null ;
    root = addinBST(root, 1 );
    root = addinBST(root, 2 );
    root = addinBST(root, 3 );
    root = addinBST(root, 4 );
    root = addinBST(root, 5 );
 
    // Add nodes of the Binary Search
    // Tree to the Binary Tree
    addinorder(root);
 
    // Print the level order traversal
    // of the Binary Tree
    printlvl();
 }
 }
 
// This code is contributed by Rajput-Ji

Python3

 # Python3 implementation of the approach
 
# Structure to hold the contents
 # of the new node
 add: class
     
    # Constructor to create a new node
    def __init__( self , data):
        self .data = data
        self .left = self .right = None
 
root1 = None
 
# Function to add a node to the
 # Binary Tree in the level order
 def addinBT(data):
    global root1
     
    # If it is the first node
    # to be added then make
    # it the root node
    if (root1 = = None ):
        root1 = add(data)
    else :
        Q = [root1]
        while ( len (Q)):
             
            # Get and remove the front
            temp = Q[ 0 ]
            Q.pop( 0 )
             
            # If the left child of the current
            # node is None then create the new
            # node here and break
            if (temp.left = = None ):
                temp.left = add(data)
                break
            else :
                Q.append(temp.left)
                 
            # If the right child of the current
            # node is None then create the new
            # node here and break
            if (temp.right = = None ):
                temp.right = add(data)
                break
            else :
                Q.append(temp.right)
                 
# Function to add a node to
 # the Binary Search tree
 def addinBST( root, data):
     
    # If the current node is None
    # then create a new node here
    # with the given data
    if (root = = None ):
        root = add(data)
         
    # If the data is smaller than the
    # current node's data then recur
    # for the left sub-tree
    elif (data < root.data):
        root.left = addinBST(root.left, data)
         
    # Else recur for the right sub-tree
    else :
        root.right = addinBST(root.right, data)
    return root
     
# Function to perform a level order
 # insertion in the Binary Tree from
 # the given Binary Search tree
 def addinorder( root):
    if (root = = None ):
        return
    addinorder(root.left)
    addinBT(root.data)
    addinorder(root.right)
     
# Function to print the level order
 # traversal of the binary tree
 def printlvl():
 
    Q = []
     
    # Push root to the
    Q.append(root1)
    while ( len (Q)):
         
        # Get the front
        temp = Q[ 0 ]
         
        # Remove the front
        Q.pop( 0 )
         
        # Print the data
        print (temp.data ,end = " " )
         
        # Push the left child
        if (temp.left ! = None ):
            Q.append(temp.left)
         
        # Push the right child
        if (temp.right ! = None ):
            Q.append(temp.right)
 
# Driver code
 
# Create the Binary Search Tree
 root = add( 1 )
 root = addinBST(root, 2 )
 root = addinBST(root, 3 )
 root = addinBST(root, 4 )
 root = addinBST(root, 5 )
 
# Add nodes of the Binary Search
 # Tree to the Binary Tree
 addinorder(root)
 
# Print the level order traversal
 # of the Binary Tree
 printlvl()
 
# This code is contributed by SHUBHAMSINGH10

C #

 // C# implementation of the approach
 using System;
 using System.Collections.Generic;
 
class GFG
 {
 
// Structure to hold the contents
 // of the new node
 node public class
 {
    public data; int
    public node left, right;
 }
 static node root1 = null ;
 
// Helper function to add and
 // return the newly added node
 static node add( data) int
 {
    node newnode = new node();
    newnode.data = data;
    newnode.left = newnode.right = null ;
    return newnode;
 }
 
// Function to add a node to the
 // Binary Tree in the level order
 static void addinBT( data) int
 {
 
    // If it is the first node
    // to be added then make
    // it the root node
    if (root1 == null )
        root1 = add(data);
    else
    {
        Queue<node> Q = new Queue<node>();
        Q.Enqueue(root1);
        while (Q.Count != 0)
        {
 
            // Get and remove the front

                    
                                            Technical Scripter
                                            Структуры данных
                                    
РЕКОМЕНДУЕМЫЕ СТАТЬИКоличество чисел между L и R, взаимно простых с P
27 Февраля, 2023
Постройте матрицу, каждая строка и столбец которой содержат N и M единиц соответственно.
27 Февраля, 2023
Максимизируйте сумму трех чисел, выполнив побитовое XOR
27 Февраля, 2023
Проверьте, совпадает ли набор первых элементов X одного массива с набором первых элементов Y другого
27 Февраля, 2023
Подсчитать подстроки нечетной длины с медианой, такой же, как K-й символ строки
27 Февраля, 2023
Найти лексикографически первый идентификатор каждого домена из заданного массива идентификаторов электронной почты
27 Февраля, 2023
Найдите общее количество фигур 'X'
26 Февраля, 2023
Максимальное значение узла, которое может быть достигнуто с использованием данных соединений
26 Февраля, 2023