Рубрики

Максимальная высота двоичного дерева поиска, созданного из заданного массива

Учитывая массив arr [] из N целых чисел, задача состоит в том, чтобы создать два двоичных дерева поиска. Один при обходе с левой стороны массива, а другой при обходе справа и найдите, какое дерево имеет большую высоту.

Примеры:

Input: arr[] = {2, 1, 3, 4}
Output: 0
BST starting from first index           BST starting from last index 
    2                                             4
   / \                                           /
  1   3                                         3
       \                                       /
        4                                     1
                                               \
                                                2

Input: arr[] = {1, 2, 6, 3, 5}
Output: 1

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

Подходить:

  • Создайте двоичное дерево поиска, вставляя узлы, начиная с первого элемента массива до последнего, и найдите высоту этого созданного дерева, скажем, leftHeight .
  • Создайте другое двоичное дерево поиска, вставляя узлы, начиная с последнего элемента массива до первого, и найдите высоту этого созданного дерева, скажем, rightHeight .
  • Выведите максимум этих вычисленных высот, т.е. max (leftHeight, rightHeight)

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

C ++

// C ++ реализация подхода
#include <bits/stdc++.h>

using namespace std;

  

struct node {

    int key;

    struct node *left, *right;

};

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

struct node* newNode(int item)

{

    struct node* temp = (struct node*)malloc(sizeof(struct 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;

}

  
/ * Вычислить "maxDepth" дерева - количество

    узлы вдоль самого длинного пути от корневого узла

    вплоть до самого дальнего листового узла. * /

int maxDepth(node* node)

{

    if (node == NULL)

        return 0;

    else {

        / * вычислить глубину каждого поддерева * /

        int lDepth = maxDepth(node->left);

        int rDepth = maxDepth(node->right);

  

        / * использовать больший * /

        if (lDepth > rDepth)

            return (lDepth + 1);

        else

            return (rDepth + 1);

    }

}

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

int maxHeight(int a[], int n)

{

    // Создать BST начиная с

    // первый элемент

    struct node* rootA = NULL;

    rootA = insert(rootA, a[0]);

    for (int i = 1; i < n; i++)

        insert(rootA, a[i]);

  

    // Создать еще один BST-запуск

    // из последнего элемента

    struct node* rootB = NULL;

    rootB = insert(rootB, a[n - 1]);

    for (int i = n - 2; i >= 0; i--)

        insert(rootB, a[i]);

  

    // Находим высоту обоих деревьев

    int A = maxDepth(rootA) - 1;

    int B = maxDepth(rootB) - 1;

  

    return max(A, B);

}

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

int main()

{

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

    int n = sizeof(a) / sizeof(a[0]);

  

    cout << maxHeight(a, n);

  

    return 0;

}

Джава

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

class GFG

{

  

static class node

{

    int key;

    node left, right;

};

  
// Вспомогательная функция для создания нового узла 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;

}

  
/ * Вычислить "maxDepth" дерева -
количество узлов вдоль самого длинного пути
от корневого узла до самого дальнего конечного узла. * /

static int maxDepth(node node)

{

    if (node == null)

        return 0;

    else 

    {

          

        / * вычислить глубину каждого поддерева * /

        int lDepth = maxDepth(node.left);

        int rDepth = maxDepth(node.right);

  

        / * использовать больший * /

        if (lDepth > rDepth)

            return (lDepth + 1);

        else

            return (rDepth + 1);

    }

}

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

static int maxHeight(int a[], int n)

{

    // Создать BST начиная с

    // первый элемент

    node rootA = null;

    rootA = insert(rootA, a[0]);

    for (int i = 1; i < n; i++)

        rootA = insert(rootA, a[i]);

  

    // Создать еще один BST-запуск

    // из последнего элемента

    node rootB = null;

    rootB = insert(rootB, a[n - 1]);

    for (int i = n - 2; i >= 0; i--)

        rootB =insert(rootB, a[i]);

  

    // Находим высоту обоих деревьев

    int A = maxDepth(rootA) - 1;

    int B = maxDepth(rootB) - 1;

  

    return Math.max(A, B);

}

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

public static void main(String args[])

{

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

    int n = a.length;

  

    System.out.println(maxHeight(a, n));

}
}

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

C #

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

using System;

  

class GFG 

    public class node 

    

        public int key; 

        public node left, right; 

    }; 

      

    // Вспомогательная функция для создания нового узла 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; 

    

      

    / * Вычислить "maxDepth" дерева -

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

    от корневого узла до самого дальнего конечного узла. * /

    static int maxDepth(node node) 

    

        if (node == null

            return 0; 

        else

        

              

            / * вычислить глубину каждого поддерева * /

            int lDepth = maxDepth(node.left); 

            int rDepth = maxDepth(node.right); 

      

            / * использовать больший * /

            if (lDepth > rDepth) 

                return (lDepth + 1); 

            else

                return (rDepth + 1); 

        

    

      

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

    // высоты среди BST

    static int maxHeight(int []a, int n) 

    

        // Создать BST начиная с

        // первый элемент

        node rootA = null

        rootA = insert(rootA, a[0]); 

        for (int i = 1; i < n; i++) 

            rootA = insert(rootA, a[i]); 

      

        // Создать еще один BST-запуск

        // из последнего элемента

        node rootB = null

        rootB = insert(rootB, a[n - 1]); 

        for (int i = n - 2; i >= 0; i--) 

            rootB =insert(rootB, a[i]); 

      

        // Находим высоту обоих деревьев

        int A = maxDepth(rootA) - 1; 

        int B = maxDepth(rootB) - 1; 

      

        return Math.Max(A, B); 

    

      

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

    public static void Main() 

    

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

        int n = a.Length; 

      

        Console.WriteLine(maxHeight(a, n)); 

    

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

Выход:

3

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

Максимальная высота двоичного дерева поиска, созданного из заданного массива

0.00 (0%) 0 votes