Рубрики

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

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

Примеры:

Input: parent[] = {1, 5, 5, 2, 2, -1, 3}
Output:
Inorder Traversal of constructed tree
0 1 5 6 3 2 4
          5
        /  \
       1    2
      /    / \
     0    3   4
         /
        6 
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:
Inorder Traversal of constructed tree
6 5 3 1 4 0 2
         0
       /   \
      1     2
     / \
    3   4
   /
  5 
 /
6

Подход: рекурсивный подход к этой проблеме обсуждается здесь .
Ниже приводится итеративный подход:

1. Create a map with key as the array index and its 
   value as the node for that index.
2. Start traversing the given parent array.
3. For all elements of the given array:
   (a) Search the map for the current index.
       (i) If the current index does not exist in the map:
           .. Create a node for the current index
           .. Map the newly created node with its key by m[i]=node
       (ii) If the key exists in the map:
            .. it means that the node is already created
            .. Do nothing
   (b) If the parent of the current index is -1, it implies it is
       the root of the tree
       .. Make root=m[i]
       Else search for the parent in the map
       (i) If the parent does not exist:
           .. Create the parent node.
           .. Assign the current node as its left child 
           .. Map the parent node(as in Step 3.(a).(i))
       (ii) If the parent exists:
           .. If the left child of the parent does not exist
              -> Assign the node as its left child
           .. Else (i.e. right child of the parent does not exist)
              -> Assign the node as its right child

Этот подход работает, даже когда узлы не приведены в порядке.

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

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

}

  
// Полезная функция для выполнения
// порядок обхода дерева

void inorder(Node* root)

{

    if (root != NULL) {

        inorder(root->left);

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

        inorder(root->right);

    }

}

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

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

{

    // Карта для отслеживания всех созданных узлов.

    // Ключ: значение узла; Значение: указатель на этот узел

    map<int, Node*> m;

    Node *root, *temp;

    int i;

  

    // Итерация для всех элементов родительского массива.

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

  

        // Узел i не существует на карте

        if (m.find(i) == m.end()) {

  

            // Создать новый узел для текущего индекса

            temp = newNode(i);

  

            // Запись узла на карте с помощью

            // ключ как i и значение как temp

            m[i] = temp;

        }

  

        // Если родитель равен -1

        // Текущий узел i является корнем

        // Так что пометьте его как корень дерева

        if (parent[i] == -1)

            root = m[i];

  

        // Текущий узел не является корневым и родительским

        // этого узла еще не создано

        else if (m.find(parent[i]) == m.end()) {

  

            // Создать родителя

            temp = newNode(parent[i]);

  

            // Назначаем узел как

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

            temp->left = m[i];

  

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

            m[parent[i]] = temp;

        }

  

        // Текущий узел не является корневым и родительским

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

        else {

  

            // Левый потомок родителя не существует

            if (!m[parent[i]]->left)

                m[parent[i]]->left = m[i];

  

            // Правого потомка родителя не существует

            else

                m[parent[i]]->right = m[i];

        }

    }

    return root;

}

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

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

  

    return 0;

}

Джава

// Java реализация подхода

import java.util.*;

  

class GFG

{

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

static class Node 

    int key; 

    Node left, right; 

}; 

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

static Node newNode(int key) 

    Node temp = new Node(); 

    temp.key = key; 

    temp.left = temp.right = null

    return (temp); 

  
// Полезная функция для выполнения
// порядок обхода дерева

static void inorder(Node root) 

    if (root != null

    

        inorder(root.left); 

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

        inorder(root.right); 

    

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

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

    // Карта для отслеживания всех созданных узлов.

    // Ключ: значение узла; Значение: указатель на этот узел

    HashMap<Integer, Node> m=new HashMap<>(); 

    Node root=new Node(), temp=new Node(); 

    int i; 

  

    // Итерация для всех элементов родительского массива.

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

    

  

        // Узел i не существует на карте

        if (m.get(i) == null

        

  

            // Создать новый узел для текущего индекса

            temp = newNode(i); 

  

            // Запись узла на карте с помощью

            // ключ как i и значение как temp

            m.put(i, temp); 

        

  

        // Если родитель равен -1

        // Текущий узел i является корнем

        // Так что пометьте его как корень дерева

        if (parent[i] == -1

            root = m.get(i); 

  

        // Текущий узел не является корневым и родительским

        // этого узла еще не создано

        else if (m.get(parent[i]) == null

        

  

            // Создать родителя

            temp = newNode(parent[i]); 

  

            // Назначаем узел как

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

            temp.left = m.get(i); 

  

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

            m.put(parent[i],temp); 

        

  

        // Текущий узел не является корневым и родительским

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

        else

        

  

            // Левый потомок родителя не существует

            if (m.get(parent[i]).left == null

                m.get(parent[i]).left = m.get(i); 

  

            // Правого потомка родителя не существует

            else

                m.get(parent[i]).right = m.get(i); 

        

    

    return root; 

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

public static void main(String args[]) 

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

    int n = parent.length; 

    Node root = createTree(parent, n); 

    System.out.print( "Inorder Traversal of coned tree\n"); 

    inorder(root); 

  

}

  
// Этот код предоставлен Арнабом Кунду

C #

// C # реализация подхода

using System;

using System.Collections.Generic;

  

class GFG

{

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

class Node 

    public int key; 

    public Node left, right; 

}; 

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

static Node newNode(int key) 

    Node temp = new Node(); 

    temp.key = key; 

    temp.left = temp.right = null

    return (temp); 

  
// Полезная функция для выполнения
// порядок обхода дерева

static void inorder(Node root) 

    if (root != null

    

        inorder(root.left); 

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

        inorder(root.right); 

    

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

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

    // Карта для отслеживания всех созданных узлов.

    // Ключ: значение узла; Значение: указатель на этот узел

    Dictionary<int, Node> m = new Dictionary<int, Node>();

    Node root = new Node(), temp = new Node(); 

    int i; 

  

    // Итерация для всех элементов родительского массива.

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

    

  

        // Узел i не существует на карте

        if (!m.ContainsKey(i)) 

        

  

            // Создать новый узел для текущего индекса

            temp = newNode(i); 

  

            // Запись узла на карте с помощью

            // ключ как i и значение как temp

            m.Add(i, temp); 

        

  

        // Если родитель равен -1

        // Текущий узел i является корнем

        // Так что пометьте его как корень дерева

        if (parent[i] == -1) 

            root = m[i]; 

  

        // Текущий узел не является корневым и родительским

        // этого узла еще не создано

        else if (!m.ContainsKey(parent[i])) 

        

  

            // Создать родителя

            temp = newNode(parent[i]); 

  

            // Назначаем узел как

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

            temp.left = m[i]; 

  

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

            m.Add(parent[i], temp); 

        

  

        // Текущий узел не является корневым и родительским

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

        else

        

  

            // Левый потомок родителя не существует

            if (m[parent[i]].left == null

                m[parent[i]].left = m[i]; 

  

            // Правого потомка родителя не существует

            else

                m[parent[i]].right = m[i]; 

        

    

    return root; 

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

public static void Main(String []args) 

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

    int n = parent.Length; 

    Node root = createTree(parent, n); 

    Console.Write("Inorder Traversal of coned tree\n"); 

    inorder(root); 


}

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

Выход:

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

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

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

0.00 (0%) 0 votes