Рубрики

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

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

Input: Two arrays that represent Inorder
       and level order traversals of a 
       Binary Tree
in[]    = {4, 8, 10, 12, 14, 20, 22};
level[] = {20, 8, 22, 4, 12, 10, 14};

Output: Construct the tree represented 
        by the two arrays.
        For the above two arrays, the 
        constructed tree is shown in 
        the diagram on right side

Следующий пост можно считать обязательным условием для этого.

Построить дерево из заданных обходов Inorder и Preorder

Давайте рассмотрим приведенный выше пример.

в [] = {4, 8, 10, 12, 14, 20, 22};
уровень [] = {20, 8, 22, 4, 12, 10, 14};

В последовательности Levelorder первый элемент является корнем дерева. Итак, мы знаем, что «20» является корнем для заданных последовательностей. Посредством поиска '20' в последовательности Inorder мы можем обнаружить, что все элементы слева от '20' находятся в левом поддереве, а элементы справа — в правом поддереве. Итак, теперь мы знаем структуру ниже.

             20
           /    \
          /      \ 
 {4,8,10,12,14}  {22}   

Давайте назовем {4,8,10,12,14} левым подмассивом в обходе Inorder и {22} правым подмассивом в обходе Inorder.
При обходе порядка уровней ключи левого и правого поддеревьев не являются последовательными. Таким образом, мы извлекаем все узлы из обхода порядка уровней, которые находятся в левом подмассиве обхода Inorder. Чтобы построить левое поддерево корня, мы возвращаемся к извлеченным элементам из обхода порядка уровней и левого подмассива обхода по порядку. В приведенном выше примере мы повторим для следующих двух массивов.

// Recur for following arrays to construct the left subtree
In[]    = {4, 8, 10, 12, 14}
level[] = {8, 4, 12, 10, 14} 

Точно так же мы повторяем для следующих двух массивов и строим правильное поддерево.

// Recur for following arrays to construct the right subtree
In[]    = {22}
level[] = {22} 

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

C ++

/ * программа для построения дерева с использованием обходов inorder и levelorder * /
#include <iostream>

using namespace std;

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

struct Node

{

    int key;

    struct Node* left, *right;

};

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

int search(int arr[], int strt, int end, int value)

{

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

        if (arr[i] == value)

            return i;

    return -1;

}

  
// n это размер уровня [], m это размер in [] и m <n. Эта
// функция извлекает ключи из уровня [], которые присутствуют в
// в[]. Порядок извлечения ключей должен быть сохранен

int *extrackKeys(int in[], int level[], int m, int n)

{

    int *newlevel = new int[m], j = 0;

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

        if (search(in, 0, m-1, level[i]) != -1)

            newlevel[j] = level[i], j++;

    return newlevel;

}

  
/ * функция, которая выделяет новый узел с заданным ключом * /

Node* newNode(int key)

{

    Node *node = new Node;

    node->key = key;

    node->left = node->right = NULL;

    return (node);

}

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

   Обход Inorder в [] и уровень обхода Order Order [].

   inSrt и inEnd - начальный и конечный индексы массива в []

   Начальные значения inStrt и inEnd должны быть 0 и n -1.

   Функция не выполняет проверку ошибок для случаев

   где inorder и levelorder не образуют дерево * /

Node* buildTree(int in[], int level[], int inStrt, int inEnd, int n)

{

  

    // Если начальный индекс больше конечного

    if (inStrt > inEnd)

        return NULL;

  

    / * Первый узел в обходе порядка уровня - root * /

    Node *root = newNode(level[0]);

  

    / * Если у этого узла нет потомков, вернуть * /

    if (inStrt == inEnd)

        return root;

  

    / * Иначе найти индекс этого узла в обходе Inorder * /

    int inIndex = search(in, inStrt, inEnd, root->key);

  

    // Извлекаем левые ключи поддеревьев из уровня обхода порядка

    int *llevel  = extrackKeys(in, level, inIndex, n);

  

    // Извлечение правильных ключей поддерева из обхода порядка уровня

    int *rlevel  = extrackKeys(in + inIndex + 1, level, n-inIndex-1, n);

  

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

    root->left = buildTree(in, llevel, inStrt, inIndex-1, n);

    root->right = buildTree(in, rlevel, inIndex+1, inEnd, n);

  

    // Освободить память, чтобы избежать утечки памяти

    delete [] llevel;

    delete [] rlevel;

  

    return root;

}

  
/ * Uti; функция для вывода обхода двоичного дерева * /

void printInorder(Node* node)

{

    if (node == NULL)

       return;

    printInorder(node->left);

    cout << node->key << " ";

    printInorder(node->right);

}

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

int main()

{

    int in[]    = {4, 8, 10, 12, 14, 20, 22};

    int level[] = {20, 8, 22, 4, 12, 10, 14};

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

    Node *root = buildTree(in, level, 0, n - 1, n);

  

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

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

    printInorder(root);

  

    return 0;

}

Джава

// Java-программа для построения дерева по порядку уровней и
// и прохождение заказа

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

class Node 

{

    int data;

    Node left, right;

   

    Node(int item) 

    {

        data = item;

        left = right = null;

    }

   

    public void setLeft(Node left) 

    {

        this.left = left;

    }

   

    public void setRight(Node right) 

    {

        this.right = right;

    }

}

   

class Tree 

{

    Node root;

   

    Node buildTree(int in[], int level[]) 

    {

        Node startnode = null;

        return constructTree(startnode, level, in, 0, in.length - 1);

    }

   

    Node constructTree(Node startNode, int[] levelOrder, int[] inOrder,

            int inStart, int inEnd) 

    {

   

        // если начальный индекс больше конечного

        if (inStart > inEnd)

            return null;

   

        if (inStart == inEnd)

            return new Node(inOrder[inStart]);

              

        boolean found = false;

        int index = 0;

   

        // он представляет индекс в массиве inOrder элемента, который

        // появляются первыми в массиве levelOrder.

        for (int i = 0; i < levelOrder.length - 1; i++) 

        {

            int data = levelOrder[i];

            for (int j = inStart; j < inEnd; j++) 

            {

                if (data == inOrder[j]) 

                {

                    startNode = new Node(data);

                    index = j;

                    found = true;

                    break;

                }

            }

            if (found == true)

                break;

        }

   

        // элементы, присутствующие перед индексом, являются частью левого потомка startNode.

        // элементы, присутствующие после индекса, являются частью правого потомка startNode.

        startNode.setLeft(constructTree(startNode, levelOrder, inOrder, 

                                                    inStart, index - 1));

        startNode.setRight(constructTree(startNode, levelOrder, inOrder, 

                                                     index + 1, inEnd));

   

        return startNode;

    }

   

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

    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[]) 

    {

        Tree tree = new Tree();

        int in[] = new int[]{4, 8, 10, 12, 14, 20, 22};

        int level[] = new int[]{20, 8, 22, 4, 12, 10, 14};

        int n = in.length;

        Node node = tree.buildTree(in, level);

   

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

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

        tree.printInorder(node);

    }

}

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

python3

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

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

class Node:

      

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

    def __init__(self, key):

        self.data = key

        self.left = None

        self.right = None

          
"" "Рекурсивная функция для построения двоичного дерева размером n из
Inorder traversal ino [] и Level Order traversal level [].
Функция не выполняет проверку ошибок для случаев
где inorder и levelorder не образуют дерево "" "

def buildTree(level, ino):

      

    # Если массив ino не пустой

    if ino :

          

        # Проверьте, существует ли этот элемент в порядке уровней

        for i in range(0, len(level)):

              

            if level[i] in ino:

                  

                # Создать новый узел с

                # соответствующий элемент

                node = Node(level[i])

                  

                # Получить индекс соответствующего элемента

                # в массиве порядка уровней

                io_index = ino.index(level[i])

                break

                  

        # Если массив inorder пустой, возвращаемый узел

        if not ino:

            return node

              

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

        node.left = buildTree(level, ino[0:io_index])

        node.right = buildTree(level, ino[io_index + 1:len(ino)])

        return node

  

def printInorder(node):

    if node is None:

        return

  

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

    printInorder(node.left)

  

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

    print(node.data, end=" ")

  

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

    printInorder(node.right)

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

  

levelorder = [20, 8, 22, 4, 12, 10, 14]

inorder = [4, 8, 10, 12, 14, 20, 22]

  

ino_len = len(inorder)

root = buildTree(levelorder, inorder)

  
# Давайте проверим дерево сборки
# печать Inorder обхода

print ("Inorder traversal of the constructed tree is")

printInorder(root)

  
# Этот код предоставлен 'Vaibhav Kumar'

C #

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

using System;

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

public class Node

{

    public int data;

    public Node left, right;

  

    public Node(int item)

    {

        data = item;

        left = right = null;

    }

  

    public virtual Node Left

    {

        set

        {

            this.left = value;

        }

    }

  

    public virtual Node Right

    {

        set

        {

            this.right = value;

        }

    }

}

  

class GFG

{

public Node root;

  

public virtual Node buildTree(int[] arr, 

                              int[] level)

{

    Node startnode = null;

    return constructTree(startnode, level, arr, 

                            0, arr.Length - 1);

}

  

public virtual Node constructTree(Node startNode, int[] levelOrder, 

                                  int[] inOrder, int inStart, int inEnd)

{

  

    // если начальный индекс больше конечного

    if (inStart > inEnd)

    {

        return null;

    }

  

    if (inStart == inEnd)

    {

        return new Node(inOrder[inStart]);

    }

  

    bool found = false;

    int index = 0;

  

    // он представляет индекс в inOrder

    // массив элементов, которые появляются первыми

    // в массиве levelOrder.

    for (int i = 0; i < levelOrder.Length - 1; i++)

    {

        int data = levelOrder[i];

        for (int j = inStart; j < inEnd; j++)

        {

            if (data == inOrder[j])

            {

                startNode = new Node(data);

                index = j;

                found = true;

                break;

            }

        }

        if (found == true)

        {

            break;

        }

    }

  

    // элементы, присутствующие перед индексом

    // часть левого потомка startNode.

    // элементы, присутствующие после индекса

    // часть правого потомка startNode.

    startNode.Left = constructTree(startNode, levelOrder, 

                                   inOrder, inStart, index - 1);

    startNode.Right = constructTree(startNode, levelOrder, 

                                    inOrder, index + 1, inEnd);

  

    return startNode;

}

  
/ * Утилита для печати заказа

   обход двоичного дерева * /

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

    int[] arr = new int[]{4, 8, 10, 12, 14, 20, 22};

    int[] level = new int[]{20, 8, 22, 4, 12, 10, 14};

    int n = arr.Length;

    Node node = tree.buildTree(arr, level);

  

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

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

    Console.Write("Inorder traversal of the "

                       "constructed tree is " + "\n");

    tree.printInorder(node);

}
}

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

Выход:

Inorder traversal of the constructed tree is
4 8 10 12 14 20 22

Верхняя граница сложности времени вышеупомянутого метода — O (n 3 ). В основной рекурсивной функции вызывается extractNodes (), что занимает O (n 2 ) времени.

Код может быть оптимизирован многими способами, и могут быть лучшие решения.
Построить дерево из обходов порядка и уровня | Набор 2

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

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

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

0.00 (0%) 0 votes