Рубрики

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

Дано двоичное дерево, где все значения от 0 до n-1 . Построить матрицу предка mat [n] [n] . Матрица предков определяется ниже.

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

Примеры:

Input: Root of below Binary Tree.
          0
        /   \
       1     2
Output: 0 1 1
        0 0 0 
        0 0 0 

Input: Root of below Binary Tree.
           5
        /    \
       1      2
      /  \    /
     0    4  3
Output: 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

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

Идея состоит в том, чтобы пройти через дерево. Во время обхода отслеживайте предков в массиве. Когда мы посещаем узел, мы добавляем его в массив предков и рассматриваем соответствующую строку в матрице смежности. Мы помечаем всех предков в его ряду как 1. Как только узел и все его дочерние элементы обработаны, мы удаляем узел из массива предков.

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

C ++

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

using namespace std;

#define MAX 100

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

struct Node

{

    int data;

    Node *left, *right;

};

  
// Создание глобальной логической матрицы для простоты

bool mat[MAX][MAX];

  
// anc [] хранит всех предков текущего узла. Эта
// функция заполняет предков для всех узлов.
// Также возвращает размер дерева. Размер дерева
// используется для печати матрицы предков.

int ancestorMatrixRec(Node *root, vector<int> &anc)

{

    /* базовый вариант */

    if (root == NULL) return 0;;

  

    // Обновляем всех предков текущего узла

    int data = root->data;

    for (int i=0; i<anc.size(); i++)

       mat[anc[i]][data] = true;

  

    // Перенесем данные в список предков

    anc.push_back(data);

  

    // Обход левого и правого поддеревьев

    int l = ancestorMatrixRec(root->left, anc);

    int r = ancestorMatrixRec(root->right, anc);

  

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

    // поскольку все его потомки обрабатываются сейчас.

    anc.pop_back();

  

    return l+r+1;

}

  
// Эта функция в основном вызывает ancestorMatrixRec ()

void ancestorMatrix(Node *root)

{

    // Создать пустой массив предков

    vector<int> anc;

  

    // Заполнить матрицу предка и найти размер

    // дерево.

    int n = ancestorMatrixRec(root, anc);

  

    // Распечатать заполненные значения

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

    {

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

            cout << mat[i][j] << " ";

        cout << endl;

    }

}

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

Node* newnode(int data)

{

    Node* node = new Node;

    node->data = data;

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

    return (node);

}

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

int main()

{

    / * Построить следующее двоичное дерево

                5

              / /

            1 2

          ///

         0 4 3 * /

    Node *root        = newnode(5);

    root->left        = newnode(1);

    root->right       = newnode(2);

    root->left->left  = newnode(0);

    root->left->right = newnode(4);

    root->right->left = newnode(3);

  

    ancestorMatrix(root);

  

    return 0;

}

Джава

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

import java.util.*;

  

class GFG

{

    // функция ancestorMatrix для заполнения матрицы

    public static void ancestorMatrix(Node root , 

                                    int matrix[][],int size)

    {

          

        // базовый вариант:

        if (root==null)

        return ;

          

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

        ancestorMatrix(root.left, matrix, size);

          

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

        ancestorMatrix(root.right, matrix, size);

          

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

        // попробуйте решить на ручке и бумаге

          

        if (root.left != null)

        {

            // сделать текущий узел родительским для его дочернего узла

            matrix[root.data][root.left.data] = 1;

              

            // перебирать все столбцы дочернего узла

            // все узлы которые являются дочерними

            // потомки корневого узла также

            // быть потомками корневого узла

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

            {

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

                // кого-то (то есть 1) затем сделать этот узел

                // как дети корня также

                if (matrix[root.left.data][i] == 1)

                matrix[root.data][i] = 1;

            }

        }

          

        // та же процедура, что и для правого узла

        if (root.right != null)

        {

            matrix[root.data][root.right.data] = 1;

              

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

            {

                if (matrix[root.right.data][i]==1)

                matrix[root.data][i] = 1;

            }

        }

              

          

    }

      

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

    public static void main(String[] args) 

    {

          

        // построить двоичное дерево следующим образом

        Node tree_root = new Node(5);

        tree_root.left = new Node (1);

        tree_root.right = new Node(2);

        tree_root.left.left = new Node(0);

        tree_root.left.right = new Node(4);

        tree_root.right.left = new Node(3);

          

        // размер матрицы

        int size = 6;

        int matrix [][] = new int[size][size];

          

        ancestorMatrix(tree_root, matrix, size);

          

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

        {

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

            {

                System.out.print(matrix[i][j]+" ");

            }

            System.out.println();

        }

    }

      

    // класс узла для узла дерева

    static class Node 

    {

        public int data ;

        public Node left ,right;

        public Node (int data)

        {

            this.data = data;

            this.left = this.right = null;

        }

    }

}

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

python3

# Python3 программа для конструирования предка
# матрица для данного дерева.

  

class newnode:

    def __init__(self, data):

        self.data = data

        self.left = self.right = None

          
# anc [] хранит всех предков текущего узла.
# Эта функция заполняет предков для всех узлов.
# Также возвращает размер дерева. Размер дерева
# используется для печати матрицы предков.

def ancestorMatrixRec(root, anc):

    global mat, MAX

      

    # базовый вариант

    if root == None:

        return 0

  

    # Обновление всех предков текущего узла

    data = root.data

    for i in range(len(anc)):

        mat[anc[i]][data] = 1

  

    # Передать данные в список предков

    anc.append(data) 

  

    # Пройти левое и правое поддеревья

    l = ancestorMatrixRec(root.left, anc) 

    r = ancestorMatrixRec(root.right, anc) 

  

    # Удалить данные из списка в списке предков

    # так как все его потомки обрабатываются сейчас.

    anc.pop(-1

  

    return l + r + 1

  
# Эта функция в основном вызывает ancestorMatrixRec ()

def ancestorMatrix(root):

      

    # Создать пустой массив предков

    anc = []

  

    # Заполните матрицу предков и найдите

    # размер дерева.

    n = ancestorMatrixRec(root, anc) 

  

    # Распечатать заполненные значения

    for i in range(n):

        for j in range(n):

            print(mat[i][j], end = " "

        print()

  
Код водителя

MAX = 100

mat = [[0] * MAX for i in range(MAX)]

  
# Построить следующее двоичное дерево
№ 5
# / /
# 1 2
# / / /
# 0 4 3

root = newnode(5

root.left = newnode(1

root.right = newnode(2

root.left.left = newnode(0

root.left.right = newnode(4

root.right.left = newnode(3

  
ancestorMatrix(root)

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

C #

// C # Программа для построения матрицы предков для данного дерева

using System;

  

class GFG 

{

    // функция ancestorMatrix для заполнения матрицы

    public static void ancestorMatrix(Node root,

                        int [,]matrix, int size) 

    {

  

        // базовый вариант:

        if (root == null

        {

            return;

        }

  

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

        ancestorMatrix(root.left, matrix, size);

  

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

        ancestorMatrix(root.right, matrix, size);

  

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

        // попробуйте решить на ручке и бумаге

        if (root.left != null)

        {

            // сделать текущий узел родительским для его дочернего узла

            matrix[root.data,root.left.data] = 1;

  

            // перебирать все столбцы дочернего узла

            // все узлы которые являются дочерними

            // потомки корневого узла также

            // быть потомками корневого узла

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

            {

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

                // кого-то (то есть 1) затем сделать этот узел

                // как дети корня также

                if (matrix[root.left.data,i] == 1) 

                {

                    matrix[root.data,i] = 1;

                }

            }

        }

  

        // та же процедура, что и для правого узла

        if (root.right != null)

        {

            matrix[root.data,root.right.data] = 1;

  

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

            {

                if (matrix[root.right.data,i] == 1) 

                {

                    matrix[root.data,i] = 1;

                }

            }

        }

  

    }

  

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

    public static void Main(String[] args)

    {

  

        // построить двоичное дерево следующим образом

        Node tree_root = new Node(5);

        tree_root.left = new Node(1);

        tree_root.right = new Node(2);

        tree_root.left.left = new Node(0);

        tree_root.left.right = new Node(4);

        tree_root.right.left = new Node(3);

  

        // размер матрицы

        int size = 6;

        int [,]matrix = new int[size,size];

  

        ancestorMatrix(tree_root, matrix, size);

  

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

        {

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

            {

                Console.Write(matrix[i,j] + " ");

            }

            Console.WriteLine();

        }

    }

  

    // класс узла для узла дерева

    public class Node

    {

  

        public int data;

        public Node left, right;

  

        public Node(int data) 

        {

            this.data = data;

            this.left = this.right = null;

        }

    }

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


Выход:

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
 

Временная сложность вышеуказанного решения составляет O (n 2 ).

Как сделать обратное — построить дерево из матрицы предков?
Построить дерево из матрицы предков

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

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

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

0.00 (0%) 0 votes