Рубрики

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

Для данного массива, который представляет дерево таким образом, что индексы массива являются значениями в узлах дерева, а значения массива дают родительский узел этого конкретного индекса (или узла). Значение индекса корневого узла всегда будет равно -1, так как нет родительского для root. Построить стандартное связанное представление заданного двоичного дерева из этого заданного представления.

Примеры:

Input: parent[] = {1, 5, 5, 2, 2, -1, 3}
Output: root of below tree
          5
        /  \
       1    2
      /    / \
     0    3   4
         /
        6 
Explanation: 
Index of -1 is 5.  So 5 is root.  
5 is present at indexes 1 and 2.  So 1 and 2 are
children of 5.  
1 is present at index 0, so 0 is child of 1.
2 is present at indexes 3 and 4.  So 3 and 4 are
children of 2.  
3 is present at index 6, so 6 is child of 3.


Input: parent[] = {-1, 0, 0, 1, 1, 3, 5};
Output: root of below tree
         0
       /   \
      1     2
     / \
    3   4
   /
  5 
 /
6

Ожидаемая временная сложность O (n), где n — количество элементов в данном массиве.


Мы настоятельно рекомендуем свернуть ваш браузер и попробовать это в первую очередь.

Простое решение для рекурсивного конструирования: сначала поиск в текущем корне, затем повторение найденных индексов (может быть не более двух индексов) и создание их левого и правого поддеревьев корня. Это решение принимает O (n 2 ), так как мы должны линейно искать каждый узел.

Эффективное решение может решить вышеупомянутую проблему за время O (n). Идея состоит в том, чтобы использовать дополнительное пространство. Созданный массив [0..n-1] используется для отслеживания созданных узлов.

createTree (parent [], n)

  1. Создайте массив указателей, скажем, создан [0..n-1]. Значение созданного [i] равно NULL, если узел для индекса i не создан, иначе это указатель на созданный узел.
  2. Делайте следующее для каждого индекса i данного массива
    createNode (родитель, я, создан)

createNode (parent [], i, crated [])

  1. Если созданный [i] не НЕДЕЙСТВИТЕЛЕН, то узел уже создан. Так что вернись.
  2. Создайте новый узел со значением 'i'.
  3. Если parent [i] равен -1 (i — root), создайте созданный узел как root и вернитесь.
  4. Проверьте, создан ли родительский элемент для «i» (Мы можем проверить это, проверив, имеет ли созданный [parent [i]] значение NULL или нет.
  5. Если родитель не создан, повторите для родителя и сначала создайте родителя.
  6. Пусть указатель на родителя будет р. Если p-> left равен NULL, то сделайте новый узел левым потомком. Иначе сделать новый узел правым потомком родителя.

Следующее — реализация C ++ вышеупомянутой идеи.

C ++

// C ++ программа для построения двоичного дерева из родительского массива
#include<bits/stdc++.h>

using namespace std;

  
// Узел дерева

struct Node

{

    int key;

    struct Node *left, *right;

};

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

Node *newNode(int key)

{

    Node *temp = new Node;

    temp->key  = key;

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

    return (temp);

}

  
// Создает узел с ключом как «i». Если я root, то он меняется
// корень. Если родитель i не создан, то сначала создается родитель

void createNode(int parent[], int i, Node *created[], Node **root)

{

    // Если этот узел уже создан

    if (created[i] != NULL)

        return;

  

    // Создаем новый узел и устанавливаем созданный [i]

    created[i] = newNode(i);

  

    // Если 'i' - root, изменить корневой указатель и вернуть

    if (parent[i] == -1)

    {

        *root = created[i];

        return;

    }

  

    // Если родитель не создан, то сначала создайте родителя

    if (created[parent[i]] == NULL)

        createNode(parent, parent[i], created, root);

  

    // Найти родительский указатель

    Node *p = created[parent[i]];

  

    // Если это первый потомок родителя

    if (p->left == NULL)

        p->left = created[i];

    else // Если второй ребенок

        p->right = created[i];

}

  
// Создает дерево из parent [0..n-1] и возвращает корень созданного дерева

Node *createTree(int parent[], int n)

{

    // Создать созданный массив [] для отслеживания

    // созданных узлов, инициализируем все записи

    // как NULL

    Node *created[n];

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

        created[i] = NULL;

  

    Node *root = NULL;

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

        createNode(parent, i, created, &root);

  

    return root;

}

  
// Для добавления новой строки в программу

inline void newLine(){

    cout << "\n";

}

  
// Сервисная функция для выполнения обхода inorder

void inorder(Node *root)

{

    if (root != NULL)

    {

        inorder(root->left);

        cout << root->key << " ";

        inorder(root->right);

    }

}

  
// Метод драйвера

int main()

{

    int parent[] =  {-1, 0, 0, 1, 1, 3, 5};

    int n = sizeof parent / sizeof parent[0];

    Node *root = createTree(parent, n);

    cout << "Inorder Traversal of constructed tree\n";

    inorder(root);

    newLine();

}

Джава

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

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

class Node 

{

    int key;

    Node left, right;

   

    public Node(int key) 

    {

        this.key = key;

        left = right = null;

    }

}

   

class BinaryTree 

{

    Node root;

   

    // Создает узел с ключом как «i». Если я root, то он меняется

    // корень. Если родитель i не создан, то сначала создается родитель

    void createNode(int parent[], int i, Node created[]) 

    {

        // Если этот узел уже создан

        if (created[i] != null)

            return;

   

        // Создаем новый узел и устанавливаем созданный [i]

        created[i] = new Node(i);

   

        // Если 'i' - root, изменить корневой указатель и вернуть

        if (parent[i] == -1

        {

            root = created[i];

            return;

        }

   

        // Если родитель не создан, то сначала создайте родителя

        if (created[parent[i]] == null)

            createNode(parent, parent[i], created);

   

        // Найти родительский указатель

        Node p = created[parent[i]];

   

        // Если это первый потомок родителя

        if (p.left == null)

            p.left = created[i];

        else // Если второй ребенок

           

            p.right = created[i];

    }

   

    / * Создает дерево из родительского [0..n-1] и возвращает корень

       созданное дерево * /

    Node createTree(int parent[], int n) 

    {    

        // Создать созданный массив [] для отслеживания

        // созданных узлов, инициализируем все записи

        // как NULL

        Node[] created = new Node[n];

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

            created[i] = null;

   

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

            createNode(parent, i, created);

   

        return root;

    }

   

    // Для добавления новой строки в программу

    void newLine() 

    {

        System.out.println("");

    }

   

    // Сервисная функция для выполнения обхода inorder

    void inorder(Node node) 

    {

        if (node != null

        {

            inorder(node.left);

            System.out.print(node.key + " ");

            inorder(node.right);

        }

    }

   

    // Метод драйвера

    public static void main(String[] args) 

    {

   

        BinaryTree tree = new BinaryTree();

        int parent[] = new int[]{-1, 0, 0, 1, 1, 3, 5};

        int n = parent.length;

        Node node = tree.createTree(parent, n);

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

        tree.inorder(node);

        tree.newLine();

    }

}

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

питон

# Реализация Python для построения двоичного дерева из
# родительский массив

  
# Структура узла

class Node:

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

    def __init__(self, key):

        self.key = key

        self.left = None

        self.right = None

  
"" "Создает узел с ключом как 'i'. Если i - root, то

    это меняет корень. Если родитель i не создан, то

    сначала создается родитель

«»»

def createNode(parent, i, created, root):

  

    # Если этот узел уже создан

    if created[i] is not None:

        return

  

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

    created[i] = Node(i)

  

    # Если «i» - root, изменить корневой указатель и вернуть

    if parent[i] == -1:

        root[0] = created[i] # root [0] обозначает корень дерева

        return

  

    # Если родитель не создан, то сначала создайте родителя

    if created[parent[i]] is None:

        createNode(parent, parent[i], created, root )

  

    # Найти родительский указатель

    p = created[parent[i]]

  

    # Если это первый потомок родителя

    if p.left is None:

        p.left = created[i]

    # Если второй ребенок

    else:

        p.right = created[i]

  

  
# Создает дерево из родителя [0..n-1] и возвращает корень
# созданное дерево

def createTree(parent):

    n = len(parent)

      

    # Создать и создать массив [], чтобы отслеживать

    Количество созданных узлов, инициализировать все записи как None

    created = [None for i in range(n+1)]

      

    root = [None]

    for i in range(n):

        createNode(parent, i, created, root)

  

    return root[0]

  
# Порядок обхода дерева

def inorder(root):

    if root is not None:

        inorder(root.left)

        print root.key,

        inorder(root.right)

  
# Метод драйвера

parent = [-1, 0, 0, 1, 1, 3, 5]

root = createTree(parent)

print "Inorder Traversal of constructed tree"

inorder(root)

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

C #

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

using System;

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

public class Node

{

    public int key;

    public Node left, right;

  

    public Node(int key)

    {

        this.key = key;

        left = right = null;

    }

}

  

class GFG

{

public Node root;

  
// Создает узел с ключом как «i».
// Если я root, то он меняется
// корень. Если родитель я не создан,
// затем сначала создается родитель

public virtual void createNode(int[] parent, 

                               int i, Node[] created)

{

    // Если этот узел уже создан

    if (created[i] != null)

    {

        return;

    }

  

    // Создаем новый узел и устанавливаем созданный [i]

    created[i] = new Node(i);

  

    // Если 'i' является корнем, изменить корень

    // указатель и возврат

    if (parent[i] == -1)

    {

        root = created[i];

        return;

    }

  

    // Если родитель не создан, то

    // сначала создаем родителя

    if (created[parent[i]] == null)

    {

        createNode(parent, parent[i], created);

    }

  

    // Найти родительский указатель

    Node p = created[parent[i]];

  

    // Если это первый потомок родителя

    if (p.left == null)

    {

        p.left = created[i];

    }

    else // Если второй ребенок

    {

  

        p.right = created[i];

    }

}

  
/ * Создает дерево из родительского [0..n-1]
и возвращает корень созданного дерева * /

public virtual Node createTree(int[] parent, int n)

{

    // Создать массив, созданный [] для

    // отслеживать созданные узлы,

    // инициализируем все записи как NULL

    Node[] created = new Node[n];

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

    {

        created[i] = null;

    }

  

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

    {

        createNode(parent, i, created);

    }

  

    return root;

}

  
// Для добавления новой строки в программу

public virtual void newLine()

{

    Console.WriteLine("");

}

  
// Сервисная функция для выполнения обхода inorder

public virtual void inorder(Node node)

{

    if (node != null)

    {

        inorder(node.left);

        Console.Write(node.key + " ");

        inorder(node.right);

    }

}

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

public static void Main(string[] args)

{

    GFG tree = new GFG();

    int[] parent = new int[]{-1, 0, 0, 1, 1, 3, 5};

    int n = parent.Length;

    Node node = tree.createTree(parent, n);

    Console.WriteLine("Inorder traversal of "

                          "constructed tree ");

    tree.inorder(node);

    tree.newLine();

}
}

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


Выход:

Inorder Traversal of constructed tree
6 5 3 1 4 0 2

Аналогичная проблема: Найти высоту двоичного дерева, представленного родительским массивом

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

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

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

0.00 (0%) 0 votes