Рубрики

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

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

Полное двоичное дерево — это двоичное дерево, в котором каждый узел имеет 0 или 2 дочерних элемента.

Ниже приведены примеры Полных Деревьев.

        1
      /   \
    2       3
  /  \     /  \
 4    5   6    7


       1
     /   \
   2      3
        /   \  
       4     5
           /   \  
          6    7
                  

          1
        /   \
      2       3
    /  \     /  \
   4    5   6    7
 /  \  
8    9 

Невозможно построить общее двоичное дерево из обходов по предварительному и последующему порядку (см. Это ). Но если известно, что двоичное дерево заполнено, мы можем построить дерево без двусмысленности. Позвольте нам понять это с помощью следующего примера.

Давайте рассмотрим два данных массива: pre [] = {1, 2, 4, 8, 9, 5, 3, 6, 7} и post [] = {8, 9, 4, 5, 2, 6, 7 , 3, 1};
В pre [] крайний левый элемент является корнем дерева. Так как дерево заполнено, а размер массива больше 1. Значение рядом с 1 в pre [], должно быть оставлено дочерним от корня. Итак, мы знаем, что 1 — корень, а 2 — дочерний. Как найти все узлы в левом поддереве? Мы знаем, что 2 является корнем всех узлов в левом поддереве. Все узлы до 2 в post [] должны быть в левом поддереве. Теперь мы знаем, что 1 — корень, элементы {8, 9, 4, 5, 2} находятся в левом поддереве, а элементы {6, 7, 3} — в правом поддереве.


                  1
                /   \
               /      \
     {8, 9, 4, 5, 2}     {6, 7, 3}

Мы рекурсивно следуем вышеуказанному подходу и получаем следующее дерево.

          1
        /   \
      2       3
    /  \     /  \
   4    5   6    7
  / \  
 8   9 

C ++

/ * программа для построения полного бинарного дерева * /
#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 [] и post [].
// preIndex используется для отслеживания индекса в pre [].
// l - низкий индекс, а h - высокий индекс для текущего подмассива в post []

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

                                int l, int h, int size) 

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

    if (*preIndex >= size || l > h) 

        return NULL; 

  

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

    // preIndex из preorder и сделать его корневым, и увеличить preIndex

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

    ++*preIndex; 

  

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

    if (l == h) 

        return root; 

  

    // Поиск следующего элемента pre [] в post []

    int i; 

    for (i = l; i <= h; ++i) 

        if (pre[*preIndex] == post[i]) 

            break

  

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

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

    if (i <= h) 

    

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

                                                l, i, size); 

        root->right = constructTreeUtil (pre, post, preIndex, 

                                                 i + 1, h, size); 

    

  

    return root; 

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

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

    int preIndex = 0; 

    return constructTreeUtil (pre, post, &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[] = {1, 2, 4, 8, 9, 5, 3, 6, 7}; 

    int post[] = {8, 9, 4, 5, 2, 6, 7, 3, 1}; 

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

  

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

  

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

    printInorder(root); 

  

    return 0; 

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

С

/ * программа для построения полного бинарного дерева * /
#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 [] и post [].
// preIndex используется для отслеживания индекса в pre [].
// l - низкий индекс, а h - высокий индекс для текущего подмассива в post []

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

                                int l, int h, int size)

{

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

    if (*preIndex >= size || l > h)

        return NULL;

  

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

    // preIndex из preorder и сделать его корневым, и увеличить preIndex

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

    ++*preIndex;

  

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

    if (l == h)

        return root;

  

    // Поиск следующего элемента pre [] в post []

    int i;

    for (i = l; i <= h; ++i)

        if (pre[*preIndex] == post[i])

            break;

  

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

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

    if (i <= h)

    {

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

                                        l, i, size);

        root->right = constructTreeUtil (pre, post, preIndex, 

                                         i + 1, h, size);

    }

  

    return root;

}

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

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

{

    int preIndex = 0;

    return constructTreeUtil (pre, post, &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[] = {1, 2, 4, 8, 9, 5, 3, 6, 7};

    int post[] = {8, 9, 4, 5, 2, 6, 7, 3, 1};

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

  

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

  

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

    printInorder(root);

  

    return 0;

}

Джава

// Java-программа для строительства
// полного двоичного дерева

public class fullbinarytreepostpre 

{

    // переменная для хранения индекса в массиве pre []

    static int preindex;

  

    static class node 

    {

        int data;

        node left, right;

  

        public node(int data) 

        {

            this.data = data;

        }

    }

  

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

    // из pre [] и post []. preIndex используется

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

    // низкий индекс, а h высокий индекс для

    // текущий подмассив в post []

    static node constructTreeUtil(int pre[], int post[], int l, 

                                   int h, int size) 

    {

          

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

        if (preindex >= size || l > h)

            return null;

  

        // Первый узел в обходе предзаказа

        // корень. Так что возьмите узел в preIndex из

        // Предзаказ и сделать его корнем, и увеличить

        // preIndex

        node root = new node(pre[preindex]);

        preindex++;

          

        // Если у текущего подарри есть только один

        // элемент, нет необходимости повторяться или

        // preIndex> размер после увеличения

        if (l == h || preindex >= size)

            return root;

        int i;

          

        // Поиск следующего элемента pre [] в post []

        for (i = l; i <= h; i++) 

        {

            if (post[i] == pre[preindex])

                break;

        }

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

        // postorder для разделения массива postorder

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

        if (i <= h) 

        {

            root.left = constructTreeUtil(pre, post, l, i, size);

            root.right = constructTreeUtil(pre, post, i + 1, h, size);

        }

        return root;

    }

  

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

    // Двоичное дерево из заданного предзаказа и

    // прохождение заказа. Эта функция

    // в основном использует constructTreeUtil ()

    static node constructTree(int pre[], int post[], int size) 

    {

        preindex = 0;

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

    }

  

    static void printInorder(node root) 

    {

        if (root == null)

            return;

        printInorder(root.left);

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

        printInorder(root.right);

    }

  

    public static void main(String[] args) 

    {

  

        int pre[] = { 1, 2, 4, 8, 9, 5, 3, 6, 7 };

        int post[] = { 8, 9, 4, 5, 2, 6, 7, 3, 1 };

  

        int size = pre.length;

        node root = constructTree(pre, post, size);

  

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

        printInorder(root);

    }

}

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

C #

// C # программа для строительства
// полного двоичного дерева

using System;

  

class GFG

{
// переменная для хранения индекса в массиве pre []

public static int preindex;

  

public class node

{

    public int data;

    public node left, right;

  

    public node(int data)

    {

        this.data = data;

    }

}

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

public static node constructTreeUtil(int[] pre, int[] post,

                                     int l, int h, int size)

{

  

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

    if (preindex >= size || l > h)

    {

        return null;

    }

  

    // Первый узел в обходе предзаказа

    // корень. Так что возьмите узел в preIndex из

    // Предзаказ и сделать его корнем, и увеличить

    // preIndex

    node root = new node(pre[preindex]);

    preindex++;

  

    // Если у текущего подарри есть только один

    // элемент, нет необходимости повторяться или

    // preIndex> размер после увеличения

    if (l == h || preindex >= size)

    {

        return root;

    }

    int i;

  

    // Поиск следующего элемента

    // из pre [] в post []

    for (i = l; i <= h; i++)

    {

        if (post[i] == pre[preindex])

        {

            break;

        }

    }

      

    // Используем индекс найденного элемента

    // в почтовом порядке, чтобы разделить почтовый заказ

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

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

    if (i <= h)

    {

        root.left = constructTreeUtil(pre, post, 

                                      l, i, size);

        root.right = constructTreeUtil(pre, post, 

                                       i + 1, h, size);

    }

    return root;

}

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

public static node constructTree(int[] pre,

                                 int[] post, int size)

{

    preindex = 0;

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

}

  

public static void printInorder(node root)

{

    if (root == null)

    {

        return;

    }

    printInorder(root.left);

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

    printInorder(root.right);

}

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

public static void Main(string[] args)

{

    int[] pre = new int[] {1, 2, 4, 8, 9, 5, 3, 6, 7};

    int[] post = new int[] {8, 9, 4, 5, 2, 6, 7, 3, 1};

  

    int size = pre.Length;

    node root = constructTree(pre, post, size);

  

    Console.WriteLine("Inorder traversal of "

                      "the constructed tree:");

    printInorder(root);

}
}

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


Выход:

Inorder traversal of the constructed tree:
8 4 9 2 5 1 6 3 7

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

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

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

0.00 (0%) 0 votes