Рубрики

Построить специальное двоичное дерево из заданного обхода Inorder

Деревья

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

Примеры:

Input: inorder[] = {5, 10, 40, 30, 28}
Output: root of following tree
         40
       /   \
      10     30
     /         \
    5          28 

Input: inorder[] = {1, 5, 10, 40, 30, 
                    15, 28, 20}
Output: root of following tree
          40
        /   \
       10     30
      /         \
     5          28
    /          /  \
   1         15    20

Идея, использованная в Построении дерева из заданных обходов Inorder и Preorder, может быть использована здесь. Пусть заданный массив равен {1, 5, 10, 40, 30, 15, 28, 20}. Максимальный элемент в данном массиве должен быть корневым. Элементы с левой стороны от максимального элемента находятся в левом поддереве, а элементы с правой стороны — в правом поддереве.

         40
      /       \  
   {1,5,10}   {30,15,28,20}

Мы рекурсивно выполняем вышеприведенный шаг для левого и правого поддеревьев и, наконец, получаем следующее дерево.

          40
        /   \
       10     30
      /         \
     5          28
    /          /  \
   1         15    20

Алгоритм: buildTree ()
1) Найти индекс максимального элемента в массиве. Максимальный элемент должен быть корнем двоичного дерева.
2) Создайте новый узел дерева «корень» с данными в качестве максимального значения, найденного на шаге 1.
3) Вызовите buildTree для элементов до максимального элемента и сделайте построенное дерево левым поддеревом «root».
5) Вызовите buildTree для элементов после максимального элемента и сделайте построенное дерево правым поддеревом «root».
6) вернуть root.

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

C ++

/ * C ++ программа для построения дерева
от обхода по заказу * /
#include <bits/stdc++.h>

using namespace std;

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

class node 

{ 

    public:

    int data; 

    node* left; 

    node* right; 

}; 

  
/ * Прототипы служебной функции для получения максимума
значение в порядке [start..end] * /

int max(int inorder[], int strt, int end); 

  
/ * Утилита для выделения памяти для узла * /

node* newNode(int data); 

  
/ * Рекурсивная функция для построения двоичного файла размера len из
Inorder обход обхода []. Начальные значения начала и конца
должно быть 0 и лен -1. * /

node* buildTree (int inorder[], int start, int end) 

{ 

    if (start > end) 

        return NULL; 

  

    / * Найти индекс максимального элемента из двоичного дерева * /

    int i = max (inorder, start, end); 

  

    / * Выберите максимальное значение и сделайте его корневым * /

    node *root = newNode(inorder[i]); 

  

    / * Если это единственный элемент в порядке [start..end],

    затем верните его * /

    if (start == end) 

        return root; 

  

    / * Используя индекс в обходе Inorder, создайте left и

    правый субтресс * /

    root->left = buildTree (inorder, start, i - 1); 

    root->right = buildTree (inorder, i + 1, end); 

  

    return root; 

} 

  
/ * ПОЛЕЗНЫЕ ФУНКЦИИ * /
/ * Функция для поиска индекса максимального значения в arr [start ... end] * /

int max (int arr[], int strt, int end) 

{ 

    int i, max = arr[strt], maxind = strt; 

    for(i = strt + 1; i <= end; i++) 

    { 

        if(arr[i] > max) 

        { 

            max = arr[i]; 

            maxind = i; 

        } 

    } 

    return maxind; 

} 

  
/ * Вспомогательная функция, которая выделяет новый узел с
данные даны и NULL левый и правый указатели. * /

node* newNode (int data) 

{ 

    node* Node = new node();

    Node->data = data; 

    Node->left = NULL; 

    Node->right = NULL; 

  

    return Node; 

} 

  
/ * Этот функционал здесь только для проверки buildTree () * /

void printInorder (node* node) 

{ 

    if (node == NULL) 

        return; 

  

    / * первый рецидив на левом ребенке * /

    printInorder (node->left); 

  

    / * затем распечатать данные узла * /

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

  

    / * теперь возвращаемся на правильного ребенка * /

    printInorder (node->right); 

} 

  
/ * Код водителя * /

int main() 

{ 

    / * Предположим, что задан обход следующего дерева

        40

        / /

        10 30

        / /

        5 28 * /

  

    int inorder[] = {5, 10, 40, 30, 28}; 

    int len = sizeof(inorder)/sizeof(inorder[0]); 

    node *root = buildTree(inorder, 0, len - 1); 

  

    / * Давайте проверим построенное дерево, напечатав обход Insorder * /

    cout << "Inorder traversal of the constructed tree is \n"; 

    printInorder(root); 

    return 0; 

} 

  
// Это код, предоставленный rathbhupendra

С

/ * программа для построения дерева из обхода по порядку * /
#include<stdio.h>
#include<stdlib.h>

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

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

struct node

{

    int data;

    struct node* left;

    struct node* right;

};

  
/ * Прототипы служебной функции для получения максимума

   значение в порядке [start..end] * /

int max(int inorder[], int strt, int end);

  
/ * Утилита для выделения памяти для узла * /

struct node* newNode(int data);

  
/ * Рекурсивная функция для построения двоичного файла размера len из

   Inorder обход обхода []. Начальные значения начала и конца

   должно быть 0 и лен -1. * /

struct node* buildTree (int inorder[], int start, int end)

{

    if (start > end)

        return NULL;

  

    / * Найти индекс максимального элемента из двоичного дерева * /

    int i = max (inorder, start, end);

  

    / * Выберите максимальное значение и сделайте его корневым * /

    struct node *root = newNode(inorder[i]);

  

    / * Если это единственный элемент в порядке [start..end],

       затем верните его * /

    if (start == end)

        return root;

  

    / * Используя индекс в обходе Inorder, создайте left и

       правый субтресс * /

    root->left  = buildTree (inorder, start, i-1);

    root->right = buildTree (inorder, i+1, end);

  

    return root;

}

  
/ * ПОЛЕЗНЫЕ ФУНКЦИИ * /
/ * Функция для поиска индекса максимального значения в arr [start ... end] * /

int max (int arr[], int strt, int end)

{

    int i, max = arr[strt], maxind = strt;

    for(i = strt+1; i <= end; i++)

    {

        if(arr[i] > max)

        {

            max = arr[i];

            maxind = i;

        }

    }

    return maxind;

}

  
/ * Вспомогательная функция, которая выделяет новый узел с

   данные даны и NULL левый и правый указатели. * /

struct node* newNode (int data)

{

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

    node->data = data;

    node->left = NULL;

    node->right = NULL;

  

    return node;

}

  
/ * Этот функционал здесь только для проверки buildTree () * /

void printInorder (struct node* node)

{

    if (node == NULL)

        return;

  

    / * первый рецидив на левом ребенке * /

    printInorder (node->left);

  

    / * затем распечатать данные узла * /

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

  

    / * теперь возвращаемся на правильного ребенка * /

    printInorder (node->right);

}

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

int main()

{

   / * Предположим, что задан обход следующего дерева

         40

       / /

      10 30

     / /

    5 28 * /

  

    int inorder[] = {5, 10, 40, 30, 28};

    int len = sizeof(inorder)/sizeof(inorder[0]);

    struct node *root = buildTree(inorder, 0, len - 1);

  

    / * Давайте проверим построенное дерево, напечатав обход Insorder * /

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

    printInorder(root);

    return 0;

}

Джава

// Java-программа для построения дерева из обхода inorder

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

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

class Node 

{

    int data;

    Node left, right;

   

    Node(int item) 

    {

        data = item;

        left = right = null;

    }

}

   

class BinaryTree 

{

    Node root;

   

    / * Рекурсивная функция для построения двоичного файла размера len из

       Inorder обход обхода []. Начальные значения начала и конца

       должно быть 0 и лен -1. * /

    Node buildTree(int inorder[], int start, int end, Node node) 

    {

        if (start > end)

            return null;

   

        / * Найти индекс максимального элемента из двоичного дерева * /

        int i = max(inorder, start, end);

   

        / * Выберите максимальное значение и сделайте его корневым * /

        node = new Node(inorder[i]);

   

        / * Если это единственный элемент в порядке [start..end],

         затем верните его * /

        if (start == end)

            return node;

   

        / * Используя индекс в обходе Inorder, создайте left и

         правый субтресс * /

        node.left = buildTree(inorder, start, i - 1, node.left);

        node.right = buildTree(inorder, i + 1, end, node.right);

   

        return node;

    }

   

    / * ПОЛЕЗНЫЕ ФУНКЦИИ * /

      

    / * Функция для поиска индекса максимального значения в arr [start ... end] * /

    int max(int arr[], int strt, int end) 

    {

        int i, max = arr[strt], maxind = strt;

        for (i = strt + 1; i <= end; i++) 

        {

            if (arr[i] > max) 

            {

                max = arr[i];

                maxind = i;

            }

        }

        return maxind;

    }

   

    / * Этот функционал здесь только для проверки buildTree () * /

    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();

          

        / * Предположим, что задан обход следующего дерева

             40

            / /

          10 30

         / /

        5 28 * /

        int inorder[] = new int[]{5, 10, 40, 30, 28};

        int len = inorder.length;

        Node mynode = tree.buildTree(inorder, 0, len - 1, tree.root);

   

        / * Давайте проверим построенное дерево, напечатав обход Inorder * /

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

        tree.printInorder(mynode);

    }

}

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

python3

# Python3 программа для построения дерева из
# обход заказа

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

class newNode:

    def __init__(self, data):

        self.data = data 

        self.left = None

        self.right = None

  
# Прототипы служебной функции для получения
# максимальное значение в порядке [start..end]

  
# Рекурсивная функция для построения двоичного файла
# размер len из Inorder обхода inorder [].
# Начальные значения начала и конца должны быть
# 0 и лен -1.

def buildTree (inorder, start, end):

    if start > end:

        return None

  

    # Найти индекс максимального элемента

    # из двоичного дерева

    i = Max (inorder, start, end) 

  

    # Выберите максимальное значение и сделайте его корневым

    root = newNode(inorder[i]) 

  

    # Если это единственный элемент в

    # inorder [start..end], затем верните его

    if start == end: 

        return root 

  

    # Использование индекса в обходе Inorder,

    # построить левый и правый субтресс

    root.left = buildTree (inorder, start, i - 1) 

    root.right = buildTree (inorder, i + 1, end) 

  

    return root

  
# ПОЛЕЗНЫЕ ФУНКЦИИ

  
# Функция поиска индекса максимума
# значение в обр [начало ... конец]

def Max(arr, strt, end):

    i, Max = 0, arr[strt]

    maxind = strt

    for i in range(strt + 1, end + 1):

        if arr[i] > Max:

            Max = arr[i] 

            maxind = i

    return maxind

  
# Эта функция здесь только для проверки buildTree ()

def printInorder (node):

    if node == None: 

        return

  

    # первый рецидив на левом ребенке

    printInorder (node.left) 

  

    # затем распечатать данные узла

    print(node.data, end = " ")

  

    # теперь возвращаемся на нужного ребенка

    printInorder (node.right)

  
Код водителя

if __name__ == '__main__':

      

    # Предположим, что обход по порядку

    # дается следующее дерево

    № 40

    # / /

    # 10 30

    # / /

    # 5 28

  

    inorder = [5, 10, 40, 30, 28]

    Len = len(inorder) 

    root = buildTree(inorder, 0, Len - 1) 

  

    # Давайте проверим построенное дерево

    # печать Insorder обхода

    print("Inorder traversal of the", 

              "constructed tree is ") 

    printInorder(root)

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

C #

// C # программа для построения дерева
// из обхода заказа

using System;

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

public class Node

{

    public int data;

    public Node left, right;

  

    public Node(int item)

    {

        data = item;

        left = right = null;

    }

}

  

class GFG

{

public Node root;

  
/ * Рекурсивная функция для построения двоичного
размера len из Inorder обхода inorder [].
Начальные значения начала и конца должны быть 0
и лен -1. * /

public virtual Node buildTree(int[] inorder, int start,

                              int end, Node node)

{

    if (start > end)

    {

        return null;

    }

  

    / * Найти индекс максимума

    элемент из двоичного дерева * /

    int i = max(inorder, start, end);

  

    / * Выберите максимальное значение и

    сделать его рутом * /

    node = new Node(inorder[i]);

  

    / * Если это единственный элемент в

    inorder [start..end], затем верните его * /

    if (start == end)

    {

        return node;

    }

  

    / * Использование индекса в обходе Inorder,

    построить левый и правый субтресс * /

    node.left = buildTree(inorder, start,

                          i - 1, node.left);

    node.right = buildTree(inorder, i + 1, 

                           end, node.right);

  

    return node;

}

  
/ * ПОЛЕЗНЫЕ ФУНКЦИИ * /

  
/ * Функция для поиска индекса
максимальное значение в arr [start ... end] * /

public virtual int max(int[] arr, 

                       int strt, int end)

{

    int i, max = arr[strt], maxind = strt;

    for (i = strt + 1; i <= end; i++)

    {

        if (arr[i] > max)

        {

            max = arr[i];

            maxind = i;

        }

    }

    return maxind;

}

  
/ * Этот функционал здесь просто

   проверить buildTree () * /

public virtual void printInorder(Node node)

{

    if (node == null)

    {

        return;

    }

  

    / * первый рецидив на левом ребенке * /

    printInorder(node.left);

  

    / * затем распечатать данные узла * /

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

  

    / * теперь возвращаемся на правильного ребенка * /

    printInorder(node.right);

}

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

public static void Main(string[] args)

{

    GFG tree = new GFG();

  

    / * Предположим, что обход inorder

       следующего дерева

        40

        / /

    10 30

    / /

    5 28 * /

    int[] inorder = new int[]{5, 10, 40, 30, 28};

    int len = inorder.Length;

    Node mynode = tree.buildTree(inorder, 0, 

                                 len - 1, tree.root);

  

    / * Давайте проверим построенное дерево

       печать Inorder обхода * /

    Console.WriteLine("Inorder traversal of " + 

                   "the constructed tree is ");

    tree.printInorder(mynode);

}
}

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


Выход:

 Inorder traversal of the constructed tree is
 5 10 40 30 28

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

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

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

Построить специальное двоичное дерево из заданного обхода Inorder

0.00 (0%) 0 votes