Рубрики

Построить дерево из матрицы предков

Учитывая матрицу предка mat [n] [n], где матрица предка определена, как показано ниже.

   mat[i][j] = 1 if i is ancestor of j
   mat[i][j] = 0, otherwise 

Построить двоичное дерево из заданной матрицы предков, где все его значения узлов от 0 до n-1.

  1. Можно предположить, что входные данные при условии, что программа действительна и из нее можно построить дерево.
  2. Многие двоичные деревья могут быть построены из одного входа. Программа построит любой из них.

Примеры:

Input: 0 1 1
       0 0 0 
       0 0 0 
Output: Root of one of the below trees.
    0                0
  /   \     OR     /   \
 1     2          2     1

Input: 0 0 0 0 0 0 
       1 0 0 0 1 0 
       0 0 0 1 0 0 
       0 0 0 0 0 0 
       0 0 0 0 0 0 
       1 1 1 1 1 0
Output: Root of one of the below trees.
      5              5               5
   /    \           / \            /   \
  1      2   OR    2   1    OR    1     2  OR ....
 /  \   /        /    /  \       / \    /
0   4  3        3    0    4     4   0  3
There are different possible outputs because ancestor
matrix doesn't store that which child is left and which
is right.

Эта проблема в основном обратная по сравнению с проблемой ниже.

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

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

  1. Строки, которые соответствуют листьям, имеют все 0
  2. Строка, соответствующая корню, имеет максимальное количество единиц.
  3. Количество единиц в i-й строке указывает количество потомков узла i.

Идея состоит в том, чтобы построить дерево снизу вверх .
1) Создать массив указателей узлов node [].

2) Хранить номера строк, которые соответствуют заданному количеству. Мы использовали мультикарту для этой цели.

3) Обработка всех записей мультикарты от наименьшего счета к наибольшему (обратите внимание, что записи в карте и мультикарте можно просматривать в отсортированном порядке). Делайте следующее для каждой записи.
…… .a) Создать новый узел для текущего номера строки.
…… .b) Если этот узел не является листовым узлом, рассмотрите всех его потомков, чей родитель не установлен, сделайте текущий узел его родительским.

4) Последний обработанный узел (узел с максимальной суммой) является корнем дерева.

Ниже приведена реализация вышеуказанной идеи на C ++. Ниже приведены шаги.

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

using namespace std;

  
# define N 6

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

struct Node

{

    int data;

    Node *left, *right;

};

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

Node* newNode(int data)

{

    Node* node = new Node;

    node->data = data;

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

    return (node);

}

  
// Создает дерево из матрицы предков

Node* ancestorTree(int mat[][N])

{

    // двоичный массив для определения

    // родитель установлен для узла i или нет

    int parent[N] = {0};

  

    // Корень будет хранить корень построенного дерева

    Node* root = NULL;

  

    // Создать мультикарту, сумма используется как ключ и строка

    // числа используются как значения

    multimap<int, int> mm;

  

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

    {

        int sum = 0; // Инициализируем сумму этой строки

        for (int j = 0; j < N; j++)

            sum += mat[i][j];

  

        // вставляем (sum, i) пары в мультикарту

        mm.insert(pair<int, int>(sum, i));

    }

  

    // узел [i] будет хранить узел для i в построенном дереве

    Node* node[N];

  

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

    // доступны в порядке возрастания суммы

    for (auto it = mm.begin(); it != mm.end(); ++it)

    {

      // создаем новый узел для каждого значения

      node[it->second] = newNode(it->second);

  

      // Для сохранения последнего обработанного узла. Этот узел будет

      // корень после завершения цикла

      root = node[it->second];

  

      // если не листовой узел

      if (it->first != 0)

      {

        // пройти строку 'it-> second' в матрице

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

        {

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

           if (!parent[i] && mat[it->second][i])

           {

             // проверка на незанятый левый / правый узел

             // и устанавливаем родителя узла i

             if (!node[it->second]->left)

               node[it->second]->left = node[i];

             else

               node[it->second]->right = node[i];

  

             parent[i] = 1;

           }

        }

      }

    }

    return root;

}

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

void printInorder(Node* node)

{

    if (node == NULL)

        return;

    printInorder(node->left);

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

    printInorder(node->right);

}

  
// Драйвер программы

int main()

{

    int mat[N][N] = {{ 0, 0, 0, 0, 0, 0 },

        { 1, 0, 0, 0, 1, 0 },

        { 0, 0, 0, 1, 0, 0 },

        { 0, 0, 0, 0, 0, 0 },

        { 0, 0, 0, 0, 0, 0 },

        { 1, 1, 1, 1, 1, 0 }

    };

  

    Node* root = ancestorTree(mat);

  

    cout << "Inorder traversal of tree is \n";

    printInorder(root);

  

    return 0;

}

Выход:

Inorder traversal of tree is 
0 1 4 5 3 2 

Обратите внимание, что мы можем также использовать массив векторов вместо мультикарты. Мы использовали мультикарту для простоты. Массив векторов улучшил бы производительность, поскольку вставка и доступ к элементам заняли бы O (1) времени.

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

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

Построить дерево из матрицы предков

0.00 (0%) 0 votes