Рубрики

Построить полное двоичное дерево из заданного массива в порядке уровней

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

Примеры:

Input  :  arr[] = {1, 2, 3, 4, 5, 6}
Output : Root of the following tree
                  1
                 / \
                2   3
               / \ /
              4  5 6


Input: arr[] = {1, 2, 3, 4, 5, 6, 6, 6, 6, 6}
Output: Root of the following tree
                   1
                  / \
                 2   3
                / \ / \
               4  5 6  6
              / \ /
             6  6 6

Если мы внимательно наблюдаем, мы можем видеть, что если родительский узел находится с индексом i в массиве, то левый потомок этого узла находится с индексом (2 * i + 1), а правый дочерний узел с индексом (2 * i + 2) в массив.
Используя эту концепцию, мы можем легко вставить левый и правый узлы, выбрав его родительский узел. Мы вставим первый элемент, присутствующий в массиве, в качестве корневого узла на уровне 0 в дереве и начнем обход массива, и для каждого узла i мы вставим в дерево его дочерние элементы, левые и правые.
Ниже приведена рекурсивная программа для этого:

C ++

// Программа CPP для построения бинарного файла
// дерево из заданного массива на уровне
// заказать мод Tree Tree
#include <bits/stdc++.h>

using namespace std;

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

struct Node

{

    int data;

    Node* left, * right;

};

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

Node* newNode(int data)

{

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

    node->data = data;

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

    return (node);

}

  
// Функция для вставки узлов в порядке уровней

Node* insertLevelOrder(int arr[], Node* root,

                       int i, int n)

{

    // Базовый вариант для рекурсии

    if (i < n)

    {

        Node* temp = newNode(arr[i]);

        root = temp;

  

        // вставляем левого ребенка

        root->left = insertLevelOrder(arr,

                   root->left, 2 * i + 1, n);

  

        // вставить правого ребенка

        root->right = insertLevelOrder(arr,

                  root->right, 2 * i + 2, n);

    }

    return root;

}

  
// Функция для печати узлов дерева в
// InOrder fashion

void inOrder(Node* root)

{

    if (root != NULL)

    {

        inOrder(root->left);

        cout << root->data <<" ";

        inOrder(root->right);

    }

}

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

int main()

{

    int arr[] = { 1, 2, 3, 4, 5, 6, 6, 6, 6 };

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

    Node* root = insertLevelOrder(arr, root, 0, n);

    inOrder(root);

}

  
// Этот код предоставлен Чхави

Джава

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

  

public class Tree {

    Node root;

  

    // Tree Node

    static class Node {

        int data;

        Node left, right;

        Node(int data)

        {

            this.data = data;

            this.left = null;

            this.right = null;

        }

    }

  

    // Функция для вставки узлов в порядке уровней

    public Node insertLevelOrder(int[] arr, Node root,

                                                int i)

    {

        // Базовый вариант для рекурсии

        if (i < arr.length) {

            Node temp = new Node(arr[i]);

            root = temp;

  

            // вставляем левого ребенка

            root.left = insertLevelOrder(arr, root.left,

                                             2 * i + 1);

  

            // вставить правого ребенка

            root.right = insertLevelOrder(arr, root.right,

                                               2 * i + 2);

        }

        return root;

    }

  

    // Функция для печати узлов дерева в стиле InOrder

    public void inOrder(Node root)

    {

        if (root != null) {

            inOrder(root.left);

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

            inOrder(root.right);

        }

    }

  

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

    public static void main(String args[])

    {

        Tree t2 = new Tree();

        int arr[] = { 1, 2, 3, 4, 5, 6, 6, 6, 6 };

        t2.root = t2.insertLevelOrder(arr, t2.root, 0);

        t2.inOrder(t2.root);

    }

}

python3

# Python3 программа для построения двоичного
# дерево из заданного массива на уровне
# заказать Fashion Tree Node

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

class newNode:

    def __init__(self, data):

        self.data = data 

        self.left = self.right = None

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

def insertLevelOrder(arr, root, i, n):

      

    # Базовый вариант для рекурсии

    if i < n:

        temp = newNode(arr[i]) 

        root = temp 

  

        # вставить левого ребенка

        root.left = insertLevelOrder(arr, root.left,

                                     2 * i + 1, n) 

  

        # вставить правильного ребенка

        root.right = insertLevelOrder(arr, root.right,

                                      2 * i + 2, n)

    return root

  
# Функция для печати узлов дерева в
# InOrder fashion

def inOrder(root):

    if root != None:

        inOrder(root.left) 

        print(root.data,end=" "

        inOrder(root.right)

  
Код водителя

if __name__ == '__main__':

    arr = [1, 2, 3, 4, 5, 6, 6, 6, 6]

    n = len(arr)

    root = None

    root = insertLevelOrder(arr, root, 0, n) 

    inOrder(root)

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

C #

// C # программа для построения двоичного дерева из
// данный массив в порядке уровня

using System;

      

public class Tree

{

    Node root;

  

    // Tree Node

    public class Node 

    {

        public int data;

        public Node left, right;

        public Node(int data)

        {

            this.data = data;

            this.left = null;

            this.right = null;

        }

    }

  

    // Функция для вставки узлов в порядке уровней

    public Node insertLevelOrder(int[] arr,

                            Node root, int i)

    {

        // Базовый вариант для рекурсии

        if (i < arr.Length) 

        {

            Node temp = new Node(arr[i]);

            root = temp;

  

            // вставляем левого ребенка

            root.left = insertLevelOrder(arr, 

                            root.left, 2 * i + 1);

  

            // вставить правого ребенка

            root.right = insertLevelOrder(arr, 

                            root.right, 2 * i + 2);

        }

        return root;

    }

  

    // Функция для печати дерева

    // узлы в стиле InOrder

    public void inOrder(Node root)

    {

        if (root != null

        {

            inOrder(root.left);

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

            inOrder(root.right);

        }

    }

  

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

    public static void Main(String []args)

    {

        Tree t2 = new Tree();

        int []arr = { 1, 2, 3, 4, 5, 6, 6, 6, 6 };

        t2.root = t2.insertLevelOrder(arr, t2.root, 0);

        t2.inOrder(t2.root);

    }

}

  
// Этот код предоставлен Rajput-Ji


Выход:

6 4 6 2 5 1 6 3 6 

Сложность времени : O (n), где n — общее количество узлов в дереве.

Эта статья предоставлена Харибаладжи Р. Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

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

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

Построить полное двоичное дерево из заданного массива в порядке уровней

0.00 (0%) 0 votes