Рубрики

Сортировка порядка сортировки данного массива, который представляет BST

Учитывая массив, который хранит полное дерево двоичного поиска, напишите функцию, которая эффективно печатает данный массив в порядке возрастания.

Например, учитывая массив [4, 2, 5, 1, 3], функция должна вывести 1, 2, 3, 4, 5

Решение:

Обход по порядку следования BST печатает его в порядке возрастания. Единственная хитрость — изменить условие завершения рекурсии в стандартном обходе дерева Inorder .

Реализация:

C ++

#include<bits/stdc++.h>

using namespace std;

  

void printSorted(int arr[], int start, int end)

{     

    if(start > end)

        return;

      

    // печать левого поддерева

    printSorted(arr, start*2 + 1, end);

      

    // печать корня

    cout << arr[start] << " ";

      

    // выводим правильное поддерево

    printSorted(arr, start*2 + 2, end); 

}

  

int main()

{

    int arr[] = {4, 2, 5, 1, 3};

    int arr_size = sizeof(arr)/sizeof(int);

    printSorted(arr, 0, arr_size-1);

    getchar();

    return 0;

}

  
// Этот код предоставлен Akanksha Rai

С

#include<stdio.h>

  

void printSorted(int arr[], int start, int end)

{     

  if(start > end)

    return;

  

  // печать левого поддерева

  printSorted(arr, start*2 + 1, end);

  

  // печать корня

  printf("%d  ", arr[start]);

  

  // выводим правильное поддерево

  printSorted(arr, start*2 + 2, end);  

}

  

int main()

{

  int arr[] = {4, 2, 5, 1, 3};

  int arr_size = sizeof(arr)/sizeof(int);

  printSorted(arr, 0, arr_size-1);

  getchar();

  return 0;

}

Джава

// JAVA-код для печати отсортированного заказа
// данный массив, который представляет BST

class GFG{

      

private static void printSorted(int[] arr, int start,

                                        int end) {

        if(start > end)

            return;

              

        // печать левого поддерева

        printSorted(arr, start*2 + 1, end);

              

        // печать корня

        System.out.print(arr[start] + " ");

              

        // выводим правильное поддерево

        printSorted(arr, start*2 + 2, end); 

        }

          

    // программа драйвера для проверки вышеуказанной функции

    public static void main(String[] args) {

        int arr[] = {4, 2, 5, 1, 3};

              

        printSorted(arr, 0, arr.length-1);

    }

}

      
// Этот код предоставлен Арнавом Кр. Мандал.

python3

# Python3 Код для сортировки порядка печати
# данный массив, который представляет BST

def printSorted(arr, start, end):

    if start > end: 

        return

      

    # печать левого поддерева

    printSorted(arr, start * 2 + 1, end)

      

    # печать корня

    print(arr[start], end = " "

      

    # печать правильного поддерева

    printSorted(arr, start * 2 + 2, end)

  
Код водителя

if __name__ == '__main__':

    arr = [4, 2, 5, 1, 3

    arr_size = len(arr) 

    printSorted(arr, 0, arr_size - 1)

  
# Этот код предоставлен PranchalK

C #

// C # код для печати отсортированного заказа
// данного массива, который представляет BST

using System;

  

class GFG

{

static private void printSorted(int []arr, 

                                int start,

                                int end) 

{

    if(start > end)

        return;

          

    // печать левого поддерева

    printSorted(arr, start * 2 + 1, end);

          

    // печать корня

    Console.Write(arr[start] + " ");

          

    // выводим правильное поддерево

    printSorted(arr, start * 2 + 2, end); 

    }

      
// Код драйвера

static public void Main(String []args) 

{

    int []arr= {4, 2, 5, 1, 3};

          

    printSorted(arr, 0, arr.Length - 1);

}
}

      
// Этот код предоставлен Арнабом Кунду

PHP

<?php
// PHP-код для печати отсортированного заказа
// данный массив, который представляет BST

  

function printSorted($arr, $start, $end

{

    if($start > $end)

        return;

          

    // печать левого поддерева

    printSorted($arr, $start * 2 + 1, $end);

          

    // печать корня

    echo($arr[$start] . " ");

          

    // выводим правильное поддерево

    printSorted($arr, $start * 2 + 2, $end); 

}

      
// Код драйвера

$arr = array(4, 2, 5, 1, 3);

      

printSorted($arr, 0, sizeof($arr) - 1);

  
// Этот код предоставлен Code_Mech.


Выход:

1 2 3 4 5 

Сложность времени: O (n)

Пожалуйста, напишите комментарии, если вы нашли вышеупомянутое решение неправильным, или найдите лучшие способы решить ту же проблему

Рекомендуемые посты:

Сортировка порядка сортировки данного массива, который представляет BST

0.00 (0%) 0 votes