Рубрики

Построить бинарное дерево поиска по заданному порядку

По заданному обходу бинарного дерева поиска постройте конструкцию BST.

Например, если заданный обход равен {1, 7, 5, 50, 40, 10}, то следует построить следующее дерево и вернуть корень дерева.

     10
   /   \
  5     40
 /  \      \
1    7      50

Способ 1 (O (n ^ 2) сложность времени)
Последний элемент обхода почтового заказа всегда является корневым. Сначала мы строим корень. Затем мы находим индекс последнего элемента, который меньше, чем корень. Пусть индекс будет «я». Значения между 0 и «i» являются частью левого поддерева, а значения между «i + 1» и «n-2» являются частью правого поддерева. Разделите данный пост [] по индексу «i» и повторите для левого и правого поддеревьев.
Например, в {1, 7, 5, 40, 50, 10} 10 является последним элементом, поэтому мы делаем его корневым. Теперь мы ищем последний элемент меньше 10, находим 5. Итак, мы знаем, что структура BST следующая.

             10
           /    \
          /      \
  {1, 7, 5}       {50, 40}

Мы рекурсивно выполняем описанные выше шаги для подмассивов {1, 7, 5} и {40, 50} и получаем полное дерево.

Способ 2 (O (n) сложность времени)
Хитрость заключается в том, чтобы установить диапазон {min .. max} для каждого узла. Инициализируйте диапазон как {INT_MIN .. INT_MAX}. Последний узел определенно будет в диапазоне, поэтому создайте корневой узел. Чтобы создать левое поддерево, установите диапазон как {INT_MIN… root-> data}. Если значения находятся в диапазоне {INT_MIN .. root-> data}, значения являются частью левого поддерева. Чтобы создать правильное поддерево, установите диапазон как {root-> data .. INT_MAX}.

Следующий код используется для генерации точного бинарного дерева поиска для данного обхода почтового заказа.

C ++

/ * AO (n) программа для построения
BST от прохождения заказа * /
#include <bits/stdc++.h>

using namespace std;

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

struct node

{

    int data;

    struct node *left, *right;

};

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

struct node* newNode (int data)

{

    struct node* temp =

(struct node *) malloc(sizeof(struct node));

  

    temp->data = data;

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

  

    return temp;

}

  
// Рекурсивная функция для построения
// BST из поста []. postIndex используется
// для отслеживания индекса в post [].

struct node* constructTreeUtil(int post[], int* postIndex,

                               int key, int min, int max, 

                               int size)

{

    // Базовый вариант

    if (*postIndex < 0)

        return NULL;

  

    struct node* root = NULL;

  

    // Если текущий элемент post []

    // в диапазоне, тогда только это часть

    // текущего поддерева

    if (key > min && key < max)

    {

        // Выделим память для корня этого

        // поддерево и декремент * postIndex

        root = newNode(key);

        *postIndex = *postIndex - 1;

  

        if (*postIndex >= 0)

        {

  

        // Все узлы, которые находятся в диапазоне {key..max}

        // перейдем в правильное поддерево, и первое такое

        // узел будет корнем правого поддерева.

        root->right = constructTreeUtil(post, postIndex, 

                                        post[*postIndex],

                                        key, max, size );

  

        // Построить поддерево под корнем

        // Все узлы, которые находятся в диапазоне {min .. key}

        // перейдем в левое поддерево, и первое такое

        // узел будет корнем левого поддерева.

        root->left = constructTreeUtil(post, postIndex,

                                       post[*postIndex],

                                       min, key, size );

        }

    }

    return root;

}

  
// Основная функция для построения BST
// из заданного обхода заказа.
// Эта функция в основном использует constructTreeUtil ()

struct node *constructTree (int post[], 

                            int size)

{

    int postIndex = size-1;

    return constructTreeUtil(post, &postIndex, 

                             post[postIndex],

                             INT_MIN, INT_MAX, size);

}

  
// Утилита для печати
// обход порядка двоичного дерева

void printInorder (struct node* node)

{

    if (node == NULL)

        return;

    printInorder(node->left);

    cout << node->data << " ";

    printInorder(node->right);

}

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

int main ()

{

    int post[] = {1, 7, 5, 50, 40, 10};

    int size = sizeof(post) / sizeof(post[0]);

  

    struct node *root = constructTree(post, size);

  

    cout << "Inorder traversal of "

        << "the constructed tree: \n";

    printInorder(root);

  

    return 0;

}

  
// Этот код добавлен
// Аканкша Рай

С

/ * AO (n) программа для строительства BST из

   прохождение заказа * /

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

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

   и указатель на правого ребенка * /

struct node

{

    int data;

    struct node *left, *right;

};

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

struct node* newNode (int data)

{

    struct node* temp =

        (struct node *) malloc( sizeof(struct node));

  

    temp->data = data;

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

  

    return temp;

}

  
// Рекурсивная функция для построения BST из post [].
// postIndex используется для отслеживания индекса в post [].

struct node* constructTreeUtil(int post[], int* postIndex,

                         int key, int min, int max, int size)

{

    // Базовый вариант

    if (*postIndex < 0)

        return NULL;

  

    struct node* root = NULL;

  

    // Если текущий элемент post [] находится в диапазоне, то

    // только это часть текущего поддерева

    if (key > min && key < max)

    {

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

        // * postIndex

        root = newNode(key);

        *postIndex = *postIndex - 1;

  

        if (*postIndex >= 0)

        {

  

          // Все узлы, которые находятся в диапазоне {key..max}, будут идти вправо

          // поддерево, и первый такой узел будет корнем правого поддерева.

          root->right = constructTreeUtil(post, postIndex, post[*postIndex],

                                          key, max, size );

  

          // Построить поддерево под корнем

          // Все узлы, находящиеся в диапазоне {min .. key}, будут идти влево

          // поддерево, и первый такой узел будет корнем левого поддерева.

          root->left = constructTreeUtil(post, postIndex, post[*postIndex],

                                         min, key, size );

        }

    }

    return root;

}

  
// Основная функция для построения BST по заданному порядку
// обход. Эта функция в основном использует constructTreeUtil ()

struct node *constructTree (int post[], int size)

{

    int postIndex = size-1;

    return constructTreeUtil(post, &postIndex, post[postIndex],

                             INT_MIN, INT_MAX, size);

}

  
// Полезная функция для печати обхода по порядку двоичного дерева

void printInorder (struct node* node)

{

    if (node == NULL)

        return;

    printInorder(node->left);

    printf("%d ", node->data);

    printInorder(node->right);

}

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

int main ()

{

    int post[] = {1, 7, 5, 50, 40, 10};

    int size = sizeof(post) / sizeof(post[0]);

  

    struct node *root = constructTree(post, size);

  

    printf("Inorder traversal of the constructed tree: \n");

    printInorder(root);

  

    return 0;

}

Джава

/ * AO (n) программа для строительства BST из

   прохождение заказа * /

  

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

   и указатель на правого ребенка * /

class Node 

{

    int data;

    Node left, right;

  

    Node(int data) 

    {

        this.data = data;

        left = right = null;

    }

}

  
// Класс, содержащий переменную, которая отслеживает общее
// вычисляем индекс

class Index 

{

    int postindex = 0;

}

  

class BinaryTree 

{

    // Рекурсивная функция для построения BST из post [].

    // postIndex используется для отслеживания индекса в post [].

    Node constructTreeUtil(int post[], Index postIndex,

            int key, int min, int max, int size) 

    {

        // Базовый вариант

        if (postIndex.postindex < 0)

            return null;

  

        Node root = null;

  

        // Если текущий элемент post [] находится в диапазоне, то

        // только это часть текущего поддерева

        if (key > min && key < max) 

        {

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

            // * postIndex

            root = new Node(key);

            postIndex.postindex = postIndex.postindex - 1;

  

            if (postIndex.postindex > 0

            {

                // Все узлы, которые находятся в диапазоне {key..max}, войдут в

                // правое поддерево, и первый такой узел будет корнем правого

                // поддерево

                root.right = constructTreeUtil(post, postIndex, 

                        post[postIndex.postindex],key, max, size);

  

                // Построить поддерево под корнем

                // Все узлы, находящиеся в диапазоне {min .. key}, будут идти влево

                // поддерево, и первый такой узел будет корнем левого поддерева.

                root.left = constructTreeUtil(post, postIndex, 

                        post[postIndex.postindex],min, key, size);

            }

        }

        return root;

    }

  

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

    // обход. Эта функция в основном использует constructTreeUtil ()

    Node constructTree(int post[], int size) 

    {

        Index index = new Index();

        index.postindex = size - 1;

        return constructTreeUtil(post, index, post[index.postindex],

                Integer.MIN_VALUE, Integer.MAX_VALUE, size);

    }

  

    // Полезная функция для печати обхода по порядку двоичного дерева

    void printInorder(Node node) 

    {

        if (node == null)

            return;

        printInorder(node.left);

        System.out.print(node.data + " ");

        printInorder(node.right);

    }

  

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

    public static void main(String[] args) 

    {

        BinaryTree tree = new BinaryTree();

        int post[] = new int[]{1, 7, 5, 50, 40, 10};

        int size = post.length;

  

        Node root = tree.constructTree(post, size);

  

        System.out.println("Inorder traversal of the constructed tree:");

        tree.printInorder(root);

    }

}

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

python3

# AO (n) программа для строительства BST
# от прохождения заказа

INT_MIN = -2**31

INT_MAX = 2**31

  
# Узел двоичного дерева содержит данные, указатель на
# левый ребенок и указатель на правый ребенок
# Сервисная функция для создания узла

class newNode: 

    def __init__(self, data): 

        self.data = data 

        self.left = self.right = None

          
# Рекурсивная функция для построения
# BST из поста []. postIndex используется
# отслеживать индекс в post [].

def constructTreeUtil(post, postIndex, 

                      key, min, max, size): 

  

    # Базовый вариант

    if (postIndex[0] < 0):

        return None

  

    root = None

  

    # Если текущий элемент сообщения []

    # в диапазоне, тогда только это часть

    # текущего поддерева

    if (key > min and key < max) :

      

        # Выделить память для корня этого

        # поддерево и декремент * postIndex

        root = newNode(key) 

        postIndex[0] = postIndex[0] - 1

  

        if (postIndex[0] >= 0) :

          

            # Все узлы, которые находятся в ключе диапазона ..

            # max перейдет в правильное поддерево и

            # первый такой узел будет корнем

            # правильное поддерево.

            root.right = constructTreeUtil(post, postIndex,

                                           post[postIndex[0]], 

                                           key, max, size ) 

  

            # Построить поддерево под root

            # Все узлы, которые находятся в диапазоне мин ..

            клавиша # перейдет в левое поддерево и

            # первый такой узел будет корнем

            # левое поддерево.

            root.left = constructTreeUtil(post, postIndex,

                                          post[postIndex[0]], 

                                          min, key, size ) 

          

    return root 

  
# Основная функция для построения BST
# из заданного обхода заказа. Эта
# функция в основном использует constructTreeUtil ()

def constructTree (post, size) :

  

    postIndex = [size-1]

    return constructTreeUtil(post, postIndex, 

                             post[postIndex[0]],

                             INT_MIN, INT_MAX, size) 

  
# Полезная функция для принтера
# обход двоичного дерева

def printInorder (node) :

  

    if (node == None) :

        return

    printInorder(node.left) 

    print(node.data, end = " "

    printInorder(node.right) 

  
Код водителя

if __name__ == '__main__':

    post = [1, 7, 5, 50, 40, 10]

    size = len(post) 

  

    root = constructTree(post, size) 

  

    print("Inorder traversal of the"

                "constructed tree: "

    printInorder(root)

  
# Этот код добавлен
# от SHUBHAMSINGH10

C #

using System;

/ * AO (n) программа для
строительство BST от
прохождение заказа * /

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

 указатель на правого ребенка * /

class Node 

    public int data; 

    public Node left, right; 

  

    public Node(int data) 

    

        this.data = data; 

        left = right = null

    

  
// Класс, содержащий переменную
// который отслеживает общее
// вычисляем индекс

class Index 

    public int postindex = 0; 

  

public class BinaryTree 

    // Рекурсивная функция для

    // построить BST из post [].

    // postIndex используется для

    // отслеживаем индекс в post [].

    Node constructTreeUtil(int []post, Index postIndex, 

                    int key, int min, int max, int size) 

    

        // Базовый вариант

        if (postIndex.postindex < 0) 

            return null

  

        Node root = null

  

        // Если текущий элемент post [] находится в диапазоне, то

        // только это часть текущего поддерева

        if (key > min && key < max) 

        

            // Выделим память для корня

            // это поддерево и декремент * postIndex

            root = new Node(key); 

            postIndex.postindex = postIndex.postindex - 1; 

  

            if (postIndex.postindex > 0) 

            

                // Все узлы которые находятся в диапазоне

                // {key..max} перейдет в правильное поддерево,

                // и первый такой узел будет корнем

                // правое поддерево

                root.right = constructTreeUtil(post, postIndex, 

                        post[postIndex.postindex], key, max, size); 

  

                // Построить поддерево под корнем

                // Все узлы которые находятся в диапазоне

                // {min .. key} будет слева

                // поддерево и первый такой узел

                // будет корнем левого поддерева.

                root.left = constructTreeUtil(post, postIndex, 

                        post[postIndex.postindex],min, key, size); 

            

        

        return root; 

    

  

    // Основная функция для построения

    // BST от заданного обхода пост-заказа.

    // Эта функция в основном использует constructTreeUtil ()

    Node constructTree(int []post, int size) 

    

        Index index = new Index(); 

        index.postindex = size - 1; 

        return constructTreeUtil(post, index,

                        post[index.postindex], 

                        int.MinValue, int.MaxValue, size); 

    

  

    // Утилита для печати

    // обход порядка двоичного дерева

    void printInorder(Node node) 

    

        if (node == null

            return

        printInorder(node.left); 

        Console.Write(node.data + " "); 

        printInorder(node.right); 

    

  

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

    public static void Main(String[] args) 

    

        BinaryTree tree = new BinaryTree(); 

        int []post = new int[]{1, 7, 5, 50, 40, 10}; 

        int size = post.Length; 

  

        Node root = tree.constructTree(post, size); 

  

        Console.WriteLine("Inorder traversal of" +

                            "the constructed tree:"); 

        tree.printInorder(root); 

    

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


Выход:

Inorder traversal of the constructed tree: 
1 5 7 10 40 50 

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

Эта статья предоставлена Aditya Goel . Если вам нравится GeeksforGeeks и вы хотите внести свой вклад, вы также можете написать статью и отправить ее по почте на contrib@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

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

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

Построить бинарное дерево поиска по заданному порядку

0.00 (0%) 0 votes