Рубрики

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

Деревья

Имеется массив pre [], представляющий обход Preorder пространственного двоичного дерева, в котором каждый узел имеет 0 или 2 дочерних элемента. Дан еще один массив preLN [], который имеет только два возможных значения: L и N. Значение 'L' в 'preLN []' указывает, что соответствующий узел в двоичном дереве является листовым узлом, а значение 'N' указывает, что соответствующий узел является неконцевым узлом. Напишите функцию для построения дерева из заданных двух массивов.

Пример:

Input:  pre[] = {10, 30, 20, 5, 15},  preLN[] = {'N', 'N', 'L', 'L', 'L'}
Output: Root of following tree
          10
         /  \
        30   15
       /  \
      20   5

Первый элемент в pre [] всегда будет корневым. Таким образом, мы можем легко определить корень. Если левое поддерево пусто, правое поддерево также должно быть пустым, и запись preLN [] для root должна быть 'L'. Мы можем просто создать узел и вернуть его. Если левое и правое поддеревья не пусты, то рекурсивно вызывайте левое и правое поддеревья и связывайте возвращенные узлы с корнем.

C ++

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

  
/ * Бинарная древовидная структура * /

struct node

{

    int data;

    struct node *left;

    struct node *right;

};

  
/ * Служебная функция для создания нового узла двоичного дерева * /

struct node* newNode (int data)

{

    struct node *temp = new struct node;

    temp->data = data;

    temp->left = NULL;

    temp->right = NULL;

    return temp;

}

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

   preLN [] массивы. Функция возвращает корень дерева. используется index_ptr

   обновить значения индекса в рекурсивных вызовах. Индекс должен быть изначально

   передается как 0 * /

struct node *constructTreeUtil(int pre[], char preLN[], int *index_ptr, int n)

{

    int index = *index_ptr; // сохраняем текущее значение индекса в pre []

  

    // Базовый случай: все узлы построены

    if (index == n)

        return NULL;

  

    // Выделим память для этого узла и увеличим индекс для

    // последующие рекурсивные вызовы

    struct node *temp = newNode ( pre[index] );

    (*index_ptr)++;

  

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

    if (preLN[index] == 'N')

    {

      temp->left  = constructTreeUtil(pre, preLN, index_ptr, n);

      temp->right = constructTreeUtil(pre, preLN, index_ptr, n);

    }

  

    return temp;

}

  
// Оболочка над constructTreeUtil ()

struct node *constructTree(int pre[], char preLN[], int n)

{

    // Инициализировать индекс как 0. Значение индекса используется в рекурсии для поддержки

    // текущий индекс в массивах pre [] и preLN [].

    int index = 0;

  

    return constructTreeUtil (pre, preLN, &index, n);

}

  

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

void printInorder (struct node* node)

{

    if (node == NULL)

        return;

  

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

    printInorder (node->left);

  

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

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

  

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

    printInorder (node->right);

}

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

int main()

{

    struct node *root = NULL;

  

    / * Построение дерева приведено на рисунке выше

          10

         / /

        30 15

       / /

      20 5 * /

    int pre[] = {10, 30, 20, 5, 15};

    char preLN[] = {'N', 'N', 'L', 'L', 'L'};

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

  

    // построить вышеупомянутое дерево

    root = constructTree (pre, preLN, n);

  

    // Проверка построенного дерева

    printf("Following is Inorder Traversal of the Constructed Binary Tree: \n");

    printInorder (root);

  

    return 0;

}

Джава

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

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

class Node 

{

    int data;

    Node left, right;

   

    Node(int item) 

    {

        data = item;

        left = right = null;

    }

}

   

class Index 

{

    int index = 0;

}

   

class BinaryTree 

{

    Node root;

    Index myindex = new Index();

   

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

       preLN [] массивы. Функция возвращает корень дерева. используется index_ptr

       обновить значения индекса в рекурсивных вызовах. Индекс должен быть изначально

       передается как 0 * /

    Node constructTreeUtil(int pre[], char preLN[], Index index_ptr, 

                                                     int n, Node temp)

    {

        // сохраняем текущее значение индекса в pre []

        int index = index_ptr.index; 

   

        // Базовый случай: все узлы построены

        if (index == n)

            return null;

   

        // Выделим память для этого узла и увеличим индекс для

        // последующие рекурсивные вызовы

        temp = new Node(pre[index]);

        (index_ptr.index)++;

   

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

        // и связываем поддеревья

        if (preLN[index] == 'N') 

        {

            temp.left = constructTreeUtil(pre, preLN, index_ptr, n, 

                                                               temp.left);

            temp.right = constructTreeUtil(pre, preLN, index_ptr, n, 

                                                               temp.right);

        }

   

        return temp;

    }

   

    // Оболочка над constructTreeUtil ()

    Node constructTree(int pre[], char preLN[], int n, Node node) 

    {

        // Инициализировать индекс как 0. Значение индекса используется в рекурсии

        // поддерживать текущий индекс в массивах pre [] и preLN [].

        int index = 0;

   

        return constructTreeUtil(pre, preLN, myindex, n, node);

    }

   

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

    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, 30, 20, 5, 15};

        char preLN[] = new char[]{'N', 'N', 'L', 'L', 'L'};

        int n = pre.length;

   

        // построить вышеупомянутое дерево

        Node mynode = tree.constructTree(pre, preLN, n, tree.root);

   

        // Проверка построенного дерева

        System.out.println("Following is Inorder Traversal of the"  

                                      + "Constructed Binary Tree: ");

        tree.printInorder(mynode);

    }

}

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

  

python3

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

  
# Сервисная функция для создания
# новый узел двоичного дерева

class newNode:

    def __init__(self, data):

        self.data = data 

        self.left = None

        self.right = None

  
# Рекурсивная функция для создания
# Двоичное дерево из заданного pre [] preLN []
# массивы. Функция возвращает корень
# дерево. index_ptr используется для обновления
# значения индекса в рекурсивных вызовах. показатель
# должен быть изначально передан как 0

def constructTreeUtil(pre, preLN, index_ptr, n):

      

    index = index_ptr[0] # сохранить текущее значение

                         № индекса в pre []

  

    # Базовый случай: все узлы построены

    if index == n: 

        return None

  

    # Выделите память для этого узла и

    # индекс приращения для последующего

    # рекурсивные вызовы

    temp = newNode(pre[index]) 

    index_ptr[0] += 1

  

    # Если это внутренний узел, создайте левый

    # и правильные поддеревья и связать поддеревья

    if preLN[index] == 'N':

        temp.left = constructTreeUtil(pre, preLN, 

                                      index_ptr, n) 

        temp.right = constructTreeUtil(pre, preLN, 

                                       index_ptr, n) 

  

    return temp

  
# Оболочка над constructTreeUtil ()

def constructTree(pre, preLN, n):

      

    # Инициализировать индекс как 0. Значение индекса

    # используется в рекурсии для поддержания текущего

    # index в массивах pre [] и preLN [].

    index = [0]

  

    return constructTreeUtil(pre, preLN, index, n)

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

def printInorder (node):

    if node == None:

        return

  

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

    printInorder (node.left) 

  

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

    print(node.data,end=" ") 

  

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

    printInorder (node.right)

      
Код водителя

if __name__ == '__main__':

    root = None

  

    # Построение дерева дано в

    # приведенная выше цифра

    № 10

    # / /

    # 30 15

    # / /

    № 20 5

    pre = [10, 30, 20, 5, 15]

    preLN = ['N', 'N', 'L', 'L', 'L'] 

    n = len(pre) 

  

    # построить вышеупомянутое дерево

    root = constructTree (pre, preLN, n) 

  

    # Тест построенного дерева

    print("Following is Inorder Traversal of",

          "the Constructed Binary Tree:") 

    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;

    }

}

  

public class Index

{

    public int index = 0;

}

  

class GFG

{

public Node root;

public Index myindex = new Index();

  
/ * Рекурсивная функция для создания
Двоичное дерево из заданных массивов pre [] preLN [].
Функция возвращает корень дерева. index_ptr
используется для обновления значений индекса в рекурсивном
звонки. Индекс должен быть изначально передан как 0 * /

public virtual Node constructTreeUtil(int[] pre, char[] preLN, 

                                      Index index_ptr, int n,

                                      Node temp)

{

    // сохраняем текущее значение индекса в pre []

    int index = index_ptr.index;

  

    // Базовый случай: все узлы построены

    if (index == n)

    {

        return null;

    }

  

    // Выделим память для этого узла

    // и индекс приращения для

    // последующие рекурсивные вызовы

    temp = new Node(pre[index]);

    (index_ptr.index)++;

  

    // Если это внутренний узел,

    // построить левое и правое поддеревья

    // и связываем поддеревья

    if (preLN[index] == 'N')

    {

        temp.left = constructTreeUtil(pre, preLN, index_ptr,

                                      n, temp.left);

        temp.right = constructTreeUtil(pre, preLN, index_ptr,

                                       n, temp.right);

    }

  

    return temp;

}

  
// Оболочка над constructTreeUtil ()

public virtual Node constructTree(int[] pre, char[] preLN, 

                                  int n, Node node)

{

    // Инициализировать индекс как 0. Значение

    // индекс используется в рекурсии

    // поддерживать текущий индекс в

    // pre [] и preLN [] массивы.

    int index = 0;

  

    return constructTreeUtil(pre, preLN, 

                             myindex, n, node);

}

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

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[] pre = new int[]{10, 30, 20, 5, 15};

    char[] preLN = new char[]{'N', 'N', 'L', 'L', 'L'};

    int n = pre.Length;

  

    // построить вышеупомянутое дерево

    Node mynode = tree.constructTree(pre, preLN, 

                                     n, tree.root);

  

    // Проверка построенного дерева

    Console.WriteLine("Following is Inorder Traversal of the" + 

                                  "Constructed Binary Tree: ");

    tree.printInorder(mynode);

}
}

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


Выход:

Following is Inorder Traversal of the Constructed Binary Tree:
20 30 5 10 15

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

Построить полное k-арное дерево из его обхода по предзаказу

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

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

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

0.00 (0%) 0 votes