Dada una array de antepasados mat[n][n] donde la array de antepasados se define como se muestra a continuación.
mat[i][j] = 1 if i is ancestor of j mat[i][j] = 0, otherwise
Construya un árbol binario a partir de una array de ancestro dada donde todos sus valores de Nodes sean de 0 a n-1.
- Se puede suponer que la entrada proporcionada por el programa es válida y se puede construir un árbol a partir de ella.
- Se pueden construir muchos árboles binarios a partir de una entrada. El programa construirá cualquiera de ellos.
Ejemplos:
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.
Le recomendamos encarecidamente que minimice su navegador y que pruebe esto usted mismo primero.
Observaciones utilizadas en la solución:
- Las filas que corresponden a hojas tienen todos 0
- La fila que corresponde a la raíz tiene un número máximo de 1.
- La cuenta de 1 en la i-ésima fila indica el número de descendientes del Node i.
La idea es construir el árbol de abajo hacia arriba .
- Cree una array de punteros de Node Node[].
- Almacene números de fila que correspondan a un recuento dado. Hemos utilizado multimapa para este propósito.
- Procese todas las entradas de multimapa desde el conteo más pequeño hasta el más grande (tenga en cuenta que las entradas en mapa y multimapa se pueden recorrer en orden). Haz lo siguiente para cada entrada.
- Cree un nuevo Node para el número de fila actual.
- Si este Node no es un Node hoja, considere todos los descendientes de él cuyo padre no está establecido, haga que el Node actual sea su padre.
- El último Node procesado (Node con suma máxima) es la raíz del árbol.
A continuación se muestra la implementación del enfoque anterior:
C++
// Given an ancestor matrix for binary tree, construct
// the tree.
#include <bits/stdc++.h>
using namespace std;
# define N 6
/* A binary tree node */
struct Node
{
int data;
Node *left, *right;
};
/* Helper function to create a new node */
Node* newNode(int data)
{
Node* node = new Node;
node->data = data;
node->left = node->right = NULL;
return (node);
}
// Constructs tree from ancestor matrix
Node* ancestorTree(int mat[][N])
{
// Binary array to determine whether
// parent is set for node i or not
int parent[N] = {0};
// Root will store the root of the constructed tree
Node* root = NULL;
// Create a multimap, sum is used as key and row
// numbers are used as values
multimap<int, int> mm;
for (int i = 0; i < N; i++)
{
int sum = 0; // Initialize sum of this row
for (int j = 0; j < N; j++)
sum += mat[i][j];
// insert(sum, i) pairs into the multimap
mm.insert(pair<int, int>(sum, i));
}
// node[i] will store node for i in constructed tree
Node* node[N];
// Traverse all entries of multimap. Note that values
// are accessed in increasing order of sum
for (auto it = mm.begin(); it != mm.end(); ++it)
{
// create a new node for every value
node[it->second] = newNode(it->second);
// To store last processed node. This node will be
// root after loop terminates
root = node[it->second];
// if non-leaf node
if (it->first != 0)
{
// traverse row 'it->second' in the matrix
for (int i = 0; i < N; i++)
{
// if parent is not set and ancestor exits
if (!parent[i] && mat[it->second][i])
{
// check for unoccupied left/right node
// and set parent of node i
if (!node[it->second]->left)
node[it->second]->left = node[i];
else
node[it->second]->right = node[i];
parent[i] = 1;
}
}
}
}
return root;
}
/* Given a binary tree, print its nodes in inorder */
void printInorder(Node* node)
{
if (node == NULL)
return;
printInorder(node->left);
printf("%d ", node->data);
printInorder(node->right);
}
// Driver code
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";
// Function call
printInorder(root);
return 0;
}
Java
// Given an ancestor matrix for binary tree, construct
// the tree.
import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.stream.Collectors;
/* A binary tree node */
class Node {
int data;
Node left, right;
Node(int d)
{
data = d;
left = right = null;
}
}
public class TreeFromAncestorMatrix {
static Node ancestorNode(int[][] mat)
{
int n = mat.length;
// Binary array to determine whether parent is set
// for node i or not
int[] parent = new int[n];
Node root = null;
// Map to store row numbers as key and
// their sum as their values
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < n; i++) {
int sum = 0;
for (int j = 0; j < n; j++)
sum += mat[i][j];
map.put(i, sum);
}
// node[i] will store node for i in
//constructed tree
Node node[] = new Node[n];
// Sorting the map according to its
//values
Map<Integer, Integer> sorted
= map.entrySet()
.stream()
.sorted(Map.Entry.comparingByValue())
.collect(Collectors.toMap(
e
-> e.getKey(),
e
-> e.getValue(),
(e1, e2) -> e2, LinkedHashMap::new));
// Traverse all entries of sorted Map.
// Note that values are accessed in increasing order
// of sum
for (Map.Entry<Integer, Integer> entry :
sorted.entrySet()) {
int key = entry.getKey();
int value = entry.getValue();
// create a new node for every
// value
node[key] = new Node(key);
// if its is an internal node
if (value != 0) {
// Traverse row
//corresponding to the node
for (int i = 0; i < n; i++)
{
// if parent is not set and
//ancestor exits
if (parent[i] == 0
&& mat[key][i] != 0)
{
// check for unoccupied
// left/right node and
//set parent of node i
if (node[key].left == null)
node[key].left = node[i];
else
node[key].right = node[i];
parent[i] = 1;
}
// To store last processed
// node. This node will be root after
// loop terminates
root = node[key];
}
}
}
return root;
}
/* Given a binary tree, print its nodes in inorder */
static void inOrder(Node root)
{
if (root == null)
return;
inOrder(root.left);
System.out.print(root.data + " ");
inOrder(root.right);
}
// Driver code
public static void main(String[] args)
{
int mat[][] = {
{ 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 = ancestorNode(mat);
// Function call
inOrder(root);
}
}
// contribute by amarsomani
Python3
# key structure to store a binary tree node
class Node:
def __init__(self, key, left = None, right = None):
self.key = key
self.left = left
self.right = right
# Utility function to print binary tree nodes in-order fashion
def inorder(node):
if node:
inorder(node.left)
print(node.key, end = ' ')
inorder(node.right)
# Function to construct a binary tree
# from specified ancestor matrix
def constructBT(mat):
# get number of rows in the matrix
N = len(mat)
# create an empty multi-dict
dict = {}
# Use sum as key and row numbers as values in the multi-dict
for i in range(N):
# find the sum of the current row
total = sum(mat[i])
# insert the sum and row number into the dict
dict.setdefault(total, []).append(i)
# node[i] will store node for i in constructed tree
node = [Node(-1)] * N
last = 0
# the value of parent[i] is true if parent is set for i'th node
parent = [False] * N
# Traverse the dictionary in sorted order (default behavior)
for key in dict.keys():
for row in dict.get(key):
last = row
# create a new node
node[row] = Node(row)
# if leaf node, do nothing
if key == 0:
continue
# traverse row
for i in range(N):
# do if parent is not set and ancestor exits
if not parent[i] and mat[row][i] == 1:
# check for the unoccupied node
if node[row].left is None:
node[row].left = node[i]
else:
node[row].right = node[i]
# set parent for i'th node
parent[i] = True
# last processed node is the root
return node[last]
# Construct a Binary Tree from Ancestor Matrix
if __name__ == '__main__':
mat = [[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, 0, 0]]
root = constructBT(mat)
inorder(root)
# This code is contributed by Priyadarshini Kumari
C#
// Given an ancestor matrix for binary tree, construct
// the tree.
using System;
using System.Collections.Generic;
using System.Linq;
/* A binary tree node */
public
class Node
{
public
int data;
public
Node left, right;
public
Node(int d)
{
data = d;
left = right = null;
}
}
public class TreeFromAncestorMatrix
{
static Node ancestorNode(int[,] mat)
{
int n = mat.GetLength(0);
// Binary array to determine whether parent is set
// for node i or not
int[] parent = new int[n];
Node root = null;
// Map to store row numbers as key and
// their sum as their values
Dictionary<int, int> map = new Dictionary<int, int>();
for (int i = 0; i < n; i++)
{
int sum = 0;
for (int j = 0; j < n; j++)
sum += mat[i, j];
map.Add(i, sum);
}
// node[i] will store node for i in
//constructed tree
Node []node = new Node[n];
var sorted = from entry in map orderby entry.Value ascending select entry;
// Traverse all entries of sorted Map.
// Note that values are accessed in increasing order
// of sum
foreach (KeyValuePair<int, int> entry in
sorted)
{
int key = entry.Key;
int value = entry.Value;
// create a new node for every
// value
node[key] = new Node(key);
// if its is an internal node
if (value != 0)
{
// Traverse row
//corresponding to the node
for (int i = 0; i < n; i++)
{
// if parent is not set and
//ancestor exits
if (parent[i] == 0
&& mat[key,i] != 0)
{
// check for unoccupied
// left/right node and
//set parent of node i
if (node[key].left == null)
node[key].left = node[i];
else
node[key].right = node[i];
parent[i] = 1;
}
// To store last processed
// node. This node will be root after
// loop terminates
root = node[key];
}
}
}
return root;
}
/* Given a binary tree, print its nodes in inorder */
static void inOrder(Node root)
{
if (root == null)
return;
inOrder(root.left);
Console.Write(root.data + " ");
inOrder(root.right);
}
// Driver code
public static void Main(String[] args)
{
int [,]mat = {
{ 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 = ancestorNode(mat);
// Function call
inOrder(root);
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Given an ancestor matrix for binary tree, construct
// the tree.
/* A binary tree node */
class Node
{
constructor(d)
{
this.data = d;
this.left = null;
this.right = null;
}
}
function ancestorNode( mat)
{
var n = mat.length;
// Binary array to determine whether parent is set
// for node i or not
var parent = Array(n).fill(0);
var root = null;
// Map to store row numbers as key and
// their sum as their values
var map = new Map();
for(var i = 0; i < n; i++)
{
var sum = 0;
for (var j = 0; j < n; j++)
sum += mat[i][j];
map.set(i, sum);
}
// node[i] will store node for i in
//constructed tree
var node = Array(n).fill(null);
// Traverse all entries of sorted Map.
// Note that values are accessed in increasing order
// of sum
for(var data of [...map].sort((a,b)=> a[1]-b[1]))
{
var key = data[0];
var value = data[1];
// create a new node for every
// value
node[key] = new Node(key);
// if its is an internal node
if (value != 0)
{
// Traverse row
//corresponding to the node
for (var i = 0; i < n; i++)
{
// if parent is not set and
//ancestor exits
if (parent[i] == 0
&& mat[key][i] != 0)
{
// check for unoccupied
// left/right node and
//set parent of node i
if (node[key].left == null)
node[key].left = node[i];
else
node[key].right = node[i];
parent[i] = 1;
}
// To store last processed
// node. This node will be root after
// loop terminates
root = node[key];
}
}
};
return root;
}
/* Given a binary tree, print its nodes in inorder */
function inOrder(root)
{
if (root == null)
return;
inOrder(root.left);
document.write(root.data + " ");
inOrder(root.right);
}
// Driver code
var mat = [
[ 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 ]
];
var root = ancestorNode(mat);
// Function call
inOrder(root);
// This code is contributed by rdtank.
</script>
Producción
0 1 4 5 3 2
Complejidad temporal: O(N 2 ), donde N es el número de Nodes del árbol.
Complejidad espacial: O(N 2 ) , donde N es el número de Nodes en el árbol.
Tenga en cuenta que también podemos usar una array de vectores en lugar de mapas múltiples. Hemos utilizado multimapa por simplicidad. La array de vectores mejoraría el rendimiento, ya que la inserción y el acceso a elementos llevaría O (1) tiempo.
Este artículo es una contribución de Aditya Goel . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA