Рубрики

Распечатать бинарное дерево поиска в Min Max Fashion

Бинарное дерево поиска, Деревья, Рекурсия

При заданном бинарном дереве поиска (BST) задача состоит в том, чтобы напечатать BST в режиме минимума-максимума.

Что такое миним-макс мода?
Мода min-max означает, что вы должны напечатать максимальный узел сначала, затем минимум, затем второй максимум, затем второй минимум и так далее.

Примеры:

Input:                
         100                            
        /   \    
      20     500     
     /  \                      
    10   30 
          \   
           40
Output: 10 500 20 100 30 40

Input:
         40                            
        /   \    
      20     50     
     /  \      \               
    10   35     60
        /      /   
      25      55
Output: 10 60 20 55 25 50 35 40

Подходить:

  1. Создайте массив inorder [] и сохраните обход inorder дерева двоичного поиска givrn.
  2. Поскольку обход по порядку дерева двоичного поиска сортируется по возрастанию, инициализируйте i = 0 и j = n — 1 .
  3. Напечатайте inorder [i] и обновите i = i + 1 .
  4. Напечатайте порядок [j] и обновите j = j — 1 .
  5. Повторите шаги 3 и 4, пока все элементы не будут напечатаны.

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

C ++

// C ++ реализация подхода
#include <iostream>

using namespace std;

  
// Структура каждого узла BST

struct node {

    int key;

    struct node *left, *right;

};

  
// Вспомогательная функция для создания нового узла BST

node* newNode(int item)

{

    node* temp = new node();

    temp->key = item;

    temp->left = temp->right = NULL;

    return temp;

}

  
/ * Утилита для вставки нового
узел с данным ключом в BST * /

struct node* insert(struct node* node, int key)

{

    / * Если дерево пустое, вернуть новый узел * /

    if (node == NULL)

        return newNode(key);

  

    / * В противном случае вернемся вниз по дереву * /

    if (key < node->key)

        node->left = insert(node->left, key);

    else if (key > node->key)

        node->right = insert(node->right, key);

  

    / * вернуть (неизмененный) указатель узла * /

    return node;

}

  
// Функция для возврата размера дерева

int sizeOfTree(node* root)

{

    if (root == NULL) {

        return 0;

    }

  

    // Рекурсивно вычисляем левый размер

    int left = sizeOfTree(root->left);

  

    // Вычислить правильный размер рекурсивно

    int right = sizeOfTree(root->right);

  

    // Возвращаем общий размер рекурсивно

    return (left + right + 1);

}

  
// Утилита для печати
// Минимальный максимальный заказ BST

void printMinMaxOrderUtil(node* root, int inOrder[],

                          int& index)

{

  

    // Базовое условие

    if (root == NULL) {

        return;

    }

  

    // Левый рекурсивный вызов

    printMinMaxOrderUtil(root->left, inOrder, index);

  

    // Сохраняем элементы в массиве inorder

    inOrder[index++] = root->key;

  

    // Правильный рекурсивный вызов

    printMinMaxOrderUtil(root->right, inOrder, index);

}

  
// Функция для печати
// Минимальный максимальный заказ BST

void printMinMaxOrder(node* root)

{

    // Сохраняем размер BST

    int numNode = sizeOfTree(root);

  

    // Взять вспомогательный массив для хранения

    // Обход по порядку следования BST

    int inOrder[numNode + 1];

    int index = 0;

  

    // вызов функции для печати

    // элемент в минимальном максимальном порядке

    printMinMaxOrderUtil(root, inOrder, index);

    int i = 0;

    index--;

  

    // цикл while для печати элементов

    // перед последним заказом

    while (i < index) {

        cout << inOrder[i++] << " "

             << inOrder[index--] << " ";

    }

    if (i == index) {

        cout << inOrder[i] << endl;

    }

}

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

int main()

{

    struct node* root = NULL;

    root = insert(root, 50);

    insert(root, 30);

    insert(root, 20);

    insert(root, 40);

    insert(root, 70);

    insert(root, 60);

    insert(root, 80);

  

    printMinMaxOrder(root);

  

    return 0;

}

Джава

// Java реализация подхода

class GFG

{

  
// Структура каждого узла BST

static class node 

{

    int key;

    node left, right;

};

static int index;

  
// Вспомогательная функция для создания нового узла BST

static node newNode(int item)

{

    node temp = new node();

    temp.key = item;

    temp.left = temp.right = null;

    return temp;

}

  
/ * Утилита для вставки нового
узел с данным ключом в BST * /

static node insert(node node, int key)

{

    / * Если дерево пусто,

    вернуть новый узел * /

    if (node == null)

        return newNode(key);

  

    / * В противном случае вернемся вниз по дереву * /

    if (key < node.key)

        node.left = insert(node.left, key);

    else if (key > node.key)

        node.right = insert(node.right, key);

  

    / * вернуть (неизмененный) указатель узла * /

    return node;

}

  
// Функция для возврата размера дерева

static int sizeOfTree(node root)

{

    if (root == null) 

    {

        return 0;

    }

  

    // Рекурсивно вычисляем левый размер

    int left = sizeOfTree(root.left);

  

    // Вычислить правильный размер рекурсивно

    int right = sizeOfTree(root.right);

  

    // Возвращаем общий размер рекурсивно

    return (left + right + 1);

}

  
// Утилита для печати
// Минимальный максимальный заказ BST

static void printMinMaxOrderUtil(node root, 

                                 int inOrder[])

{

  

    // Базовое условие

    if (root == null)

    {

        return;

    }

  

    // Левый рекурсивный вызов

    printMinMaxOrderUtil(root.left, inOrder);

  

    // Сохраняем элементы в массиве inorder

    inOrder[index++] = root.key;

  

    // Правильный рекурсивный вызов

    printMinMaxOrderUtil(root.right, inOrder);

}

  
// Функция для печати
// Минимальный максимальный заказ BST

static void printMinMaxOrder(node root)

{

    // Сохраняем размер BST

    int numNode = sizeOfTree(root);

  

    // Взять вспомогательный массив для хранения

    // Обход по порядку следования BST

    int []inOrder = new int[numNode + 1];

  

    // вызов функции для печати

    // элемент в минимальном максимальном порядке

    printMinMaxOrderUtil(root, inOrder);

    int i = 0;

    index--;

  

    // цикл while для печати элементов

    // перед последним заказом

    while (i < index) 

    {

        System.out.print(inOrder[i++] + " " + 

                         inOrder[index--] + " ");

    }

    if (i == index)

    {

        System.out.println(inOrder[i]);

    }

}

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

public static void main(String[] args) 

{

    node root = null;

    root = insert(root, 50);

    insert(root, 30);

    insert(root, 20);

    insert(root, 40);

    insert(root, 70);

    insert(root, 60);

    insert(root, 80);

  

    printMinMaxOrder(root);

}
}

  
// Этот код предоставлен 29AjayKumar

python3

# Python3 реализация подхода

  
# Структура каждого узла BST

class Node: 

    def __init__(self,key): 

        self.left = None

        self.right = None

        self.val = key

          

def insert(root,node): 

    if root is None: 

        root = Node(node) 

    else: 

        if root.val < node: 

            if root.right is None: 

                root.right = Node(node) 

            else: 

                insert(root.right, node) 

        else: 

            if root.left is None: 

                root.left = Node(node) 

            else: 

                insert(root.left, node) 

                  
# Функция для возврата размера дерева

def sizeOfTree(root): 

  

    if root == None:

        return 0

      

    # Расчет левого размера рекурсивно

    left = sizeOfTree(root.left)

  

    # Расчет правильного размера рекурсивно

    right = sizeOfTree(root.right); 

  

    # Возвращаем общий размер рекурсивно

    return (left + right + 1) 

  
# Утилита для печати
# Минимальный максимальный заказ BST

def printMinMaxOrderUtil(root, inOrder, index): 

  

    # Базовое состояние

    if root == None: 

        return

  

    # Левый рекурсивный вызов

    printMinMaxOrderUtil(root.left, inOrder, index) 

  

    # Хранить элементы в массиве inorder

    inOrder[index[0]] = root.val

    index[0] += 1

  

    # Правильный рекурсивный вызов

    printMinMaxOrderUtil(root.right, inOrder, index) 

  
# Функция для печати
# Минимальный максимальный заказ BST

def printMinMaxOrder(root): 

      

    # Хранить размер BST

    numNode = sizeOfTree(root); 

  

    # Взять вспомогательный массив для хранения

    # Порядок обхода BST

    inOrder = [0] * (numNode + 1) 

    index = 0

  

    # Вызов функции для печати

    # элемент в минимальном максимальном порядке

    ref = [index]

    printMinMaxOrderUtil(root, inOrder, ref) 

    index = ref[0]

    i = 0; 

    index -= 1

  

    # Пока цикл для печати элементов

    # Перед последним заказом

    while (i < index):

          

        print (inOrder[i], inOrder[index], end = ' ') 

        i += 1

        index -= 1

      

    if i == index: 

        print(inOrder[i]) 

      
Код водителя

root = Node(50) 

insert(root, 30) 

insert(root, 20)

insert(root, 40) 

insert(root, 70) 

insert(root, 60) 

insert(root, 80)

  
printMinMaxOrder(root)

      
# Этот код предоставлен Садиком Али

C #

// C # реализация подхода

using System;

  

class GFG

{

  
// Структура каждого узла BST

class node 

{

    public int key;

    public node left, right;

};

static int index;

  
// Вспомогательная функция для создания нового узла BST

static node newNode(int item)

{

    node temp = new node();

    temp.key = item;

    temp.left = temp.right = null;

    return temp;

}

  
/ * Утилита для вставки нового
узел с данным ключом в BST * /

static node insert(node node, int key)

{

    / * Если дерево пусто,

    вернуть новый узел * /

    if (node == null)

        return newNode(key);

  

    / * В противном случае вернемся вниз по дереву * /

    if (key < node.key)

        node.left = insert(node.left, key);

    else if (key > node.key)

        node.right = insert(node.right, key);

  

    / * вернуть (неизмененный) указатель узла * /

    return node;

}

  
// Функция для возврата размера дерева

static int sizeOfTree(node root)

{

    if (root == null) 

    {

        return 0;

    }

  

    // Рекурсивно вычисляем левый размер

    int left = sizeOfTree(root.left);

  

    // Вычислить правильный размер рекурсивно

    int right = sizeOfTree(root.right);

  

    // Возвращаем общий размер рекурсивно

    return (left + right + 1);

}

  
// Утилита для печати
// Минимальный максимальный заказ BST

static void printMinMaxOrderUtil(node root, 

                                  int []inOrder)

{

  

    // Базовое условие

    if (root == null)

    {

        return;

    }

  

    // Левый рекурсивный вызов

    printMinMaxOrderUtil(root.left, inOrder);

  

    // Сохраняем элементы в массиве inorder

    inOrder[index++] = root.key;

  

    // Правильный рекурсивный вызов

    printMinMaxOrderUtil(root.right, inOrder);

}

  
// Функция для печати
// Минимальный максимальный заказ BST

static void printMinMaxOrder(node root)

{

    // Сохраняем размер BST

    int numNode = sizeOfTree(root);

  

    // Взять вспомогательный массив для хранения

    // Обход по порядку следования BST

    int []inOrder = new int[numNode + 1];

  

    // вызов функции для печати

    // элемент в минимальном максимальном порядке

    printMinMaxOrderUtil(root, inOrder);

    int i = 0;

    index--;

  

    // цикл while для печати элементов

    // перед последним заказом

    while (i < index) 

    {

        Console.Write(inOrder[i++] + " " + 

                      inOrder[index--] + " ");

    }

    if (i == index)

    {

        Console.WriteLine(inOrder[i]);

    }

}

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

public static void Main(String[] args) 

{

    node root = null;

    root = insert(root, 50);

    insert(root, 30);

    insert(root, 20);

    insert(root, 40);

    insert(root, 70);

    insert(root, 60);

    insert(root, 80);

  

    printMinMaxOrder(root);

}
}

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

Выход:

20 80 30 70 40 60 50

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

Распечатать бинарное дерево поиска в Min Max Fashion

0.00 (0%) 0 votes