Рубрики

Построить BST из заданного обхода предзаказа | Комплект 1

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

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

     10
   /   \
  5     40
 /  \      \
1    7      50

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

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

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

C ++

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

using namespace std;

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

class node 

    public:

    int data; 

    node *left; 

    node *right; 

}; 

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

node* newNode (int data) 

    node* temp = new node();

  

    temp->data = data; 

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

  

    return temp; 

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

node* constructTreeUtil (int pre[], int* preIndex, 

                                int low, int high, int size) 

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

    if (*preIndex >= size || low > high) 

        return NULL; 

  

    // Первый узел в обходе предзаказа - root. Итак, возьмите узел в

    // preIndex из pre [] и делаем его корневым, и увеличиваем preIndex

    node* root = newNode ( pre[*preIndex] ); 

    *preIndex = *preIndex + 1; 

  

    // Если текущий подарри имеет только один элемент, повторять не нужно

    if (low == high) 

        return root; 

  

    // Поиск первого элемента больше корня

    int i; 

    for ( i = low; i <= high; ++i ) 

        if ( pre[ i ] > root->data ) 

            break

  

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

        // предзаказ массива из двух частей. Левое поддерево и правое поддерево

    root->left = constructTreeUtil ( pre, preIndex, *preIndex, 

                                         i - 1, size ); 

    root->right = constructTreeUtil ( pre, preIndex, i, high, size ); 

  

    return root; 

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

node *constructTree (int pre[], int size) 

    int preIndex = 0; 

    return constructTreeUtil (pre, &preIndex, 0, size - 1, size); 

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

void printInorder (node* node) 

    if (node == NULL) 

        return

    printInorder(node->left); 

    cout<<node->data<<" "

    printInorder(node->right); 

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

int main () 

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

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

  

    node *root = constructTree(pre, size); 

  

    cout<<"Inorder traversal of the constructed tree: \n"

    printInorder(root); 

  

    return 0; 

  

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

С

/ * AO (n ^ 2) программа для построения BST из обхода предзаказа * /
#include <stdio.h>
#include <stdlib.h>

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

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

struct node

{

    int data;

    struct node *left;

    struct node *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;

}

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

struct node* constructTreeUtil (int pre[], int* preIndex,

                                int low, int high, int size)

{

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

    if (*preIndex >= size || low > high)

        return NULL;

  

    // Первый узел в обходе предзаказа - root. Итак, возьмите узел в

    // preIndex из pre [] и делаем его корневым, и увеличиваем preIndex

    struct node* root = newNode ( pre[*preIndex] );

    *preIndex = *preIndex + 1;

  

    // Если текущий подарри имеет только один элемент, повторять не нужно

    if (low == high)

        return root;

  

    // Поиск первого элемента больше корня

    int i;

    for ( i = low; i <= high; ++i )

        if ( pre[ i ] > root->data )

            break;

  

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

    // две части. Левое поддерево и правое поддерево

    root->left = constructTreeUtil ( pre, preIndex, *preIndex, i - 1, size );

    root->right = constructTreeUtil ( pre, preIndex, i, high, size );

  

    return root;

}

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

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

{

    int preIndex = 0;

    return constructTreeUtil (pre, &preIndex, 0, size - 1, size);

}

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

void printInorder (struct node* node)

{

    if (node == NULL)

        return;

    printInorder(node->left);

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

    printInorder(node->right);

}

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

int main ()

{

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

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

  

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

  

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

    printInorder(root);

  

    return 0;

}

Джава

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

  
// Узел двоичного дерева

class Node {

  

    int data;

    Node left, right;

  

    Node(int d) {

        data = d;

        left = right = null;

    }

}

  

class Index {

  

    int index = 0;

}

  

class BinaryTree {

  

    Index index = new Index();

      

    // Рекурсивная функция для создания Full из pre []. preIndex используется

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

    Node constructTreeUtil(int pre[], Index preIndex,

            int low, int high, int size) {

          

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

        if (preIndex.index >= size || low > high) {

            return null;

        }

  

        // Первый узел в обходе предзаказа - root. Итак, возьмите узел в

        // preIndex из pre [] и делаем его корневым, и увеличиваем preIndex

        Node root = new Node(pre[preIndex.index]);

        preIndex.index = preIndex.index + 1;

  

        // Если текущий подарри имеет только один элемент, повторять не нужно

        if (low == high) {

            return root;

        }

  

        // Поиск первого элемента больше корня

        int i;

        for (i = low; i <= high; ++i) {

            if (pre[i] > root.data) {

                break;

            }

        }

  

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

        // предзаказ массива из двух частей. Левое поддерево и правое поддерево

        root.left = constructTreeUtil(pre, preIndex, preIndex.index, 

                                      i - 1, size);

        root.right = constructTreeUtil(pre, preIndex, i, high, size);

  

        return root;

    }

  

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

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

    Node constructTree(int pre[], int size) {

        return constructTreeUtil(pre, index, 0, size - 1, 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 pre[] = new int[]{10, 5, 1, 7, 40, 50};

        int size = pre.length;

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

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

        tree.printInorder(root);

    }

}

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

питон

# AO (n ^ 2) Python3 программа для построения BST из обхода предзаказа

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

class Node():

      

    # Конструктор для создания нового узла

    def __init__(self, data):

        self.data = data 

        self.left = None

        self.right = None

  

  
# constructTreeUtil.preIndex является статической переменной
# function constructTreeUtil

  
# Функция для получения значения статической переменной
# constructTreeUtil.preIndex

def getPreIndex():

    return constructTreeUtil.preIndex

  
# Функция для увеличения значения статической переменной
# constructTreeUtil.preIndex

def incrementPreIndex():

    constructTreeUtil.preIndex += 1

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

def constructTreeUtil(pre, low, high, size):

      

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

    if( getPreIndex() >= size or low > high):

        return None

  

    # Первый узел в обходе предзаказа - root. Так возьми

    # узел в preIndex из pre [] и сделать его корневым,

    # и приращение preIndex

    root = Node(pre[getPreIndex()])

    incrementPreIndex()

  

    # Если текущий подмассив имеет только один элемент,

    # нет необходимости повторяться

    if low == high :

        return root 

  

    # Поиск первого элемента больше корня

    for i in range(low, high+1):

        if (pre[i] > root.data):

            break 

      

    # Используйте индекс элемента, найденного в предзаказе, чтобы разделить

    # предзаказ массива из двух частей. Левое поддерево и правое

    # поддерево

    root.left = constructTreeUtil(pre, getPreIndex(),  i-1 , size) 

  

    root.right = constructTreeUtil(pre, i, high, size) 

      

    return root

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

def constructTree(pre):

    size = len(pre) 

    constructTreeUtil.preIndex = 0 

    return constructTreeUtil(pre, 0, size-1, size)

  

  

def printInorder(root):

    if root is None:

        return 

    printInorder(root.left)

    print root.data,

    printInorder(root.right)

  

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

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

  

root = constructTree(pre)

print "Inorder traversal of the constructed tree:"

printInorder(root)

  
# Этот код предоставлен Nikhil Kumar Singh (nickzuck_007)

C #

using System;

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

  
// Узел двоичного дерева

public class Node

{

  

    public int data;

    public Node left, right;

  

    public Node(int d)

    {

        data = d;

        left = right = null;

    }

}

  

public class Index

{

  

    public int index = 0;

}

  

public class BinaryTree

{

  

    public Index index = new Index();

  

    // Рекурсивная функция для создания Full из pre []. preIndex используется

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

    public virtual Node constructTreeUtil(int[] pre, Index preIndex, 

                                          int low, int high, int size)

    {

  

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

        if (preIndex.index >= size || low > high)

        {

            return null;

        }

  

        // Первый узел в обходе предзаказа - root. Итак, возьмите узел

        // в preIndex из pre [] и делаем его корневым, и увеличиваем preIndex

        Node root = new Node(pre[preIndex.index]);

        preIndex.index = preIndex.index + 1;

  

        // Если текущий подарри имеет только один элемент, повторять не нужно

        if (low == high)

        {

            return root;

        }

  

        // Поиск первого элемента больше корня

        int i;

        for (i = low; i <= high; ++i)

        {

            if (pre[i] > root.data)

            {

                break;

            }

        }

  

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

        // предзаказ массива из двух частей. Левое поддерево и правое поддерево

        root.left = constructTreeUtil(pre, preIndex, preIndex.index, 

                                      i - 1, size);

        root.right = constructTreeUtil(pre, preIndex, i, high, size);

  

        return root;

    }

  

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

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

    public virtual Node constructTree(int[] pre, int size)

    {

        return constructTreeUtil(pre, index, 0, size - 1, size);

    }

  

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

    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)

    {

        BinaryTree tree = new BinaryTree();

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

        int size = pre.Length;

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

        Console.WriteLine("Inorder traversal of the constructed tree is ");

        tree.printInorder(root);

    }

}

  

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

Выход:

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

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

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

C ++

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

using namespace std;

  

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

class node 

    public:

    int data; 

    node *left; 

    node *right; 

}; 

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

node* newNode (int data) 

    node* temp = new node();

  

    temp->data = data; 

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

  

    return temp; 

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

node* constructTreeUtil( int pre[], int* preIndex, int key, 

                                int min, int max, int size ) 

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

    if( *preIndex >= size ) 

        return NULL; 

  

    node* root = NULL; 

  

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

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

    if( key > min && key < max ) 

    

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

        // поддерево и приращение * preIndex

        root = newNode ( key ); 

        *preIndex = *preIndex + 1; 

          

        if (*preIndex < size) 

        

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

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

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

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

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

            root->left = constructTreeUtil( pre, preIndex, pre[*preIndex], 

                                        min, key, size ); 

  

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

            // {key..max} будет справа

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

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

            root->right = constructTreeUtil( pre, preIndex, pre[*preIndex], 

                                        key, max, size ); 

        

    

  

    return root; 

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

node *constructTree (int pre[], int size) 

    int preIndex = 0; 

    return constructTreeUtil ( pre, &preIndex, pre[0], INT_MIN, 

                            INT_MAX, size ); 

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

void printInorder (node* node) 

    if (node == NULL) 

        return

    printInorder(node->left); 

    cout << node->data << " "

    printInorder(node->right); 

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

int main () 

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

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

  

    node *root = constructTree(pre, size); 

  

    cout << "Inorder traversal of the constructed tree: \n"

    printInorder(root); 

  

    return 0; 

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

С

/ * AO (n) программа для построения BST из обхода предзаказа * /
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

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

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

struct node

{

    int data;

    struct node *left;

    struct node *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 из pre []. preIndex используется
// для отслеживания индекса в pre [].

struct node* constructTreeUtil( int pre[], int* preIndex, int key,

                                int min, int max, int size )

{

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

    if( *preIndex >= size )

        return NULL;

   

    struct node* root = NULL;

   

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

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

    if( key > min && key < max )

    {

        // Распределяем память для корня этого поддерева и увеличиваем * preIndex

        root = newNode ( key );

        *preIndex = *preIndex + 1;

          

        if (*preIndex < size)

        {

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

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

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

            root->left = constructTreeUtil( pre, preIndex, pre[*preIndex],

                                        min, key, size );

   

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

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

            root->right = constructTreeUtil( pre, preIndex, pre[*preIndex],

                                         key, max, size );

        }

    }

   

    return root;

}

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

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

{

    int preIndex = 0;

    return constructTreeUtil ( pre, &preIndex, pre[0], 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 pre[] = {10, 5, 1, 7, 40, 50};

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

  

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

  

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

    printInorder(root);

  

    return 0;

}

Джава

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

  
// Узел двоичного дерева

class Node {

  

    int data;

    Node left, right;

  

    Node(int d) {

        data = d;

        left = right = null;

    }

}

  

class Index {

  

    int index = 0;

}

  

class BinaryTree {

  

    Index index = new Index();

  

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

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

    Node constructTreeUtil(int pre[], Index preIndex, int key,

            int min, int max, int size) {

  

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

        if (preIndex.index >= size) {

            return null;

        }

  

        Node root = null;

  

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

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

        if (key > min && key < max) {

  

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

            // поддерево и приращение * preIndex

            root = new Node(key);

            preIndex.index = preIndex.index + 1;

  

            if (preIndex.index < size) {

  

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

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

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

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

                root.left = constructTreeUtil(pre, preIndex, 

                            pre[preIndex.index], min, key, size);

  

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

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

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

                root.right = constructTreeUtil(pre, preIndex, 

                             pre[preIndex.index], key, max, size);

            }

        }

  

        return root;

    }

  

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

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

    Node constructTree(int pre[], int size) {

        int preIndex = 0;

        return constructTreeUtil(pre, index, pre[0], 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 pre[] = new int[]{10, 5, 1, 7, 40, 50};

        int size = pre.length;

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

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

        tree.printInorder(root);

    }

}

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

питон

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

  

INT_MIN = float("-infinity")

INT_MAX = float("infinity")

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

class Node:

  

    # Конструктор для создания нового узла

    def __init__(self, data):

        self.data = data

        self.left = None

        self.right = None

  
# Методы для получения и установки значения статической переменной
# constructTreeUtil.preIndex для функции construcTreeUtil ()

def getPreIndex():

    return constructTreeUtil.preIndex

  

def incrementPreIndex():

    constructTreeUtil.preIndex += 1 

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

def constructTreeUtil(pre, key, mini, maxi, size):

      

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

    if(getPreIndex() >= size):

        return None

  

    root = None

      

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

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

    if(key > mini and key < maxi):

  

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

        # и приращение constructTreeUtil.preIndex

        root = Node(key)

        incrementPreIndex()

  

        if(getPreIndex() < size):

             

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

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

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

            # быть корнем левого поддерева

            root.left = constructTreeUtil(pre,

                         pre[getPreIndex()], mini, key, size)

  

            # Все узлы в диапазоне {key..max} будут

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

            # быть корнем правильного поддерева

            root.right = constructTreeUtil(pre,

                     pre[getPreIndex()], key, maxi, size)

  

    return root

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

def constructTree(pre):

    constructTreeUtil.preIndex = 0 

    size = len(pre)

    return constructTreeUtil(pre, pre[0], INT_MIN, INT_MAX, size)

  

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

def printInorder(node):

      

    if node is None:

        return 

    printInorder(node.left)

    print node.data, 

    printInorder(node.right)

  

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

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

root = constructTree(pre)

  

print "Inorder traversal of the constructed tree: "

printInorder(root)

  
# Этот код предоставлен Nikhil Kumar Singh (nickzuck_007)

C #

using System;

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

  
// Узел двоичного дерева

public class Node

{

  

    public int data;

    public Node left, right;

  

    public Node(int d)

    {

        data = d;

        left = right = null;

    }

}

  

public class Index

{

  

    public int index = 0;

}

  

public class BinaryTree

{

  

    public Index index = new Index();

  

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

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

    public virtual Node constructTreeUtil(int[] pre, Index preIndex, 

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

    {

  

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

        if (preIndex.index >= size)

        {

            return null;

        }

  

        Node root = null;

  

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

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

        if (key > min && key < max)

        {

  

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

            // и увеличиваем * preIndex

            root = new Node(key);

            preIndex.index = preIndex.index + 1;

  

            if (preIndex.index < size)

            {

  

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

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

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

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

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

                root.left = constructTreeUtil(pre, preIndex, 

                            pre[preIndex.index], min, key, size);

  

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

                // {key..max} будет справа

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

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

                root.right = constructTreeUtil(pre, preIndex, 

                            pre[preIndex.index], key, max, size);

            }

        }

  

        return root;

    }

  

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

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

    public virtual Node constructTree(int[] pre, int size)

    {

          

        return constructTreeUtil(pre, index, pre[0], 

                    int.MinValue, int.MaxValue, size);

    }

  

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

    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)

    {

        BinaryTree tree = new BinaryTree();

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

        int size = pre.Length;

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

        Console.WriteLine("Inorder traversal of the constructed tree is ");

        tree.printInorder(root);

    }

}

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


Выход:

Inorder traversal of Binary Tree:
1 5 7 10 40 50

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

Вскоре мы опубликуем O (n) итеративное решение в виде отдельного поста.

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

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

Построить BST из заданного обхода предзаказа | Комплект 1

0.00 (0%) 0 votes