Dado un árbol binario donde todos los valores son de 0 a n-1 . Construya una array de antepasados mat[n][n] . La array de antepasados se define a continuación.
mat[i][j] = 1 if i is ancestor of j mat[i][j] = 0, otherwise
Ejemplos:
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
Le recomendamos encarecidamente que minimice su navegador y que pruebe esto usted mismo primero.
Método 1: La idea es atravesar el árbol. Mientras atraviesa, realice un seguimiento de los antepasados en una array. Cuando visitamos un Node, lo agregamos a la array de antepasados y consideramos la fila correspondiente en la array de adyacencia. Marcamos todos los ancestros en su fila como 1. Una vez que se procesan un Node y todos sus hijos, eliminamos el Node de la array de ancestros.
A continuación se muestra la implementación de la idea anterior.
C++
// C++ program to construct ancestor matrix for
// given tree.
#include<bits/stdc++.h>
using namespace std;
#define MAX 100
/* A binary tree node */
struct Node
{
int data;
Node *left, *right;
};
// Creating a global boolean matrix for simplicity
bool mat[MAX][MAX];
// anc[] stores all ancestors of current node. This
// function fills ancestors for all nodes.
// It also returns size of tree. Size of tree is
// used to print ancestor matrix.
int ancestorMatrixRec(Node *root, vector<int> &anc)
{
/* base case */
if (root == NULL) return 0;;
// Update all ancestors of current node
int data = root->data;
for (int i=0; i<anc.size(); i++)
mat[anc[i]][data] = true;
// Push data to list of ancestors
anc.push_back(data);
// Traverse left and right subtrees
int l = ancestorMatrixRec(root->left, anc);
int r = ancestorMatrixRec(root->right, anc);
// Remove data from list the list of ancestors
// as all descendants of it are processed now.
anc.pop_back();
return l+r+1;
}
// This function mainly calls ancestorMatrixRec()
void ancestorMatrix(Node *root)
{
// Create an empty ancestor array
vector<int> anc;
// Fill ancestor matrix and find size of
// tree.
int n = ancestorMatrixRec(root, anc);
// Print the filled values
for (int i=0; i<n; i++)
{
for (int j=0; j<n; j++)
cout << mat[i][j] << " ";
cout << endl;
}
}
/* 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);
}
/* Driver program to test above functions*/
int main()
{
/* Construct the following binary tree
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
// Java Program to construct ancestor matrix for a given tree
import java.util.*;
class GFG
{
// ancestorMatrix function to populate the matrix of
public static void ancestorMatrix(Node root ,
int matrix[][],int size)
{
// base case:
if (root==null)
return ;
// call recursively for a preorder {left}
ancestorMatrix(root.left, matrix, size);
// call recursively for preorder {right}
ancestorMatrix(root.right, matrix, size);
// here we will reach the root node automatically
// try solving on pen and paper
if (root.left != null)
{
// make the current node as parent of its children node
matrix[root.data][root.left.data] = 1;
// iterate through all the columns of children node
// all nodes which are children to
// children of root node will also
// be children of root node
for (int i = 0; i < size; i++)
{
// if children of root node is a parent
// of someone (i.e 1) then make that node
// as children of root also
if (matrix[root.left.data][i] == 1)
matrix[root.data][i] = 1;
}
}
// same procedure followed for right node as well
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;
}
}
}
// Driver program to test the program
public static void main(String[] args)
{
// construct the binary tree as follows
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);
// size of matrix
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();
}
}
// node class for tree node
static class Node
{
public int data ;
public Node left ,right;
public Node (int data)
{
this.data = data;
this.left = this.right = null;
}
}
}
// This code is contributed by Sparsh Singhal
Python3
# Python3 program to construct ancestor # matrix for given tree. class newnode: def __init__(self, data): self.data = data self.left = self.right = None # anc[] stores all ancestors of current node. # This function fills ancestors for all nodes. # It also returns size of tree. Size of tree # is used to print ancestor matrix. def ancestorMatrixRec(root, anc): global mat, MAX # base case if root == None: return 0 # Update all ancestors of current node data = root.data for i in range(len(anc)): mat[anc[i]][data] = 1 # Push data to list of ancestors anc.append(data) # Traverse left and right subtrees l = ancestorMatrixRec(root.left, anc) r = ancestorMatrixRec(root.right, anc) # Remove data from list the list of ancestors # as all descendants of it are processed now. anc.pop(-1) return l + r + 1 # This function mainly calls ancestorMatrixRec() def ancestorMatrix(root): # Create an empty ancestor array anc = [] # Fill ancestor matrix and find # size of tree. n = ancestorMatrixRec(root, anc) # Print the filled values for i in range(n): for j in range(n): print(mat[i][j], end = " ") print() # Driver Code MAX = 100 mat = [[0] * MAX for i in range(MAX)] # Construct the following binary tree # 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) # This code is contributed by PranchalK
C#
// C# Program to construct ancestor matrix for a given tree
using System;
class GFG
{
// ancestorMatrix function to populate the matrix of
public static void ancestorMatrix(Node root,
int [,]matrix, int size)
{
// base case:
if (root == null)
{
return;
}
// call recursively for a preorder {left}
ancestorMatrix(root.left, matrix, size);
// call recursively for preorder {right}
ancestorMatrix(root.right, matrix, size);
// here we will reach the root node automatically
// try solving on pen and paper
if (root.left != null)
{
// make the current node as parent of its children node
matrix[root.data,root.left.data] = 1;
// iterate through all the columns of children node
// all nodes which are children to
// children of root node will also
// be children of root node
for (int i = 0; i < size; i++)
{
// if children of root node is a parent
// of someone (i.e 1) then make that node
// as children of root also
if (matrix[root.left.data,i] == 1)
{
matrix[root.data,i] = 1;
}
}
}
// same procedure followed for right node as well
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;
}
}
}
}
// Driver code
public static void Main(String[] args)
{
// construct the binary tree as follows
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);
// size of matrix
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();
}
}
// node class for tree node
public class Node
{
public int data;
public Node left, right;
public Node(int data)
{
this.data = data;
this.left = this.right = null;
}
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
class Node
{
constructor(data)
{
this.data=data;
this.left = this.right = null;
}
}
function ancestorMatrixRec(root ,anc)
{
// base case:
if (root==null)
return 0;
let data = root.data;
for(let i=0;i<anc.length;i++)
{
matrix[anc[i]][data] = 1;
}
//document.write(data+"<br>")
// Push data to list of ancestors
anc.push(data);
// Traverse left and right subtrees
let l = ancestorMatrixRec(root.left, anc);
let r = ancestorMatrixRec(root.right, anc);
// Remove data from list the list of ancestors
// as all descendants of it are processed now.
anc.pop()
return l + r + 1;
}
function ancestorMatrix(root)
{
let anc = [];
let n = ancestorMatrixRec(root, anc);
for (let i = 0; i < n; i++)
{
for (let j = 0; j < n; j++)
{
document.write(matrix[i][j]+" ");
}
document.write("<br>");
}
}
// construct the binary tree as follows
let 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);
// size of matrix
let size = 100;
let matrix = new Array(size);
for(let i=0;i<size;i++)
{
matrix[i]=new Array(size);
for(let j=0;j<size;j++)
{
matrix[i][j]=0;
}
}
ancestorMatrix(tree_root);
// This code is contributed by rag2127
</script>
Producció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
La complejidad temporal de la solución anterior es O(n 2 ).
Espacio Auxiliar: O(n 2 )
Método 2:
Este método no utiliza ningún espacio auxiliar para almacenar valores en el vector. Cree una array 2D (digamos M) del tamaño dado. Ahora la idea es recorrer el árbol en PreOrder. Mientras atraviesa, mantenga un registro del último antepasado.
Cuando visitamos un Node, si el Node es NULL devuelve, de lo contrario asigna M[lastAncestorValue][currentNodeValue]=1.
A través de esto, tenemos Matrix (M) que realiza un seguimiento del antepasado más bajo. Ahora, al aplicar el cierre transitivo a esta Matrix (M), obtenemos el resultado requerido.
A continuación se muestra la implementación de la idea anterior.
C++
// C++ program to construct ancestor matrix for
// given tree.
#include<bits/stdc++.h>
using namespace std;
#define size 6
int M[size][size]={0};
/* 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);
}
void printMatrix(){
for(int i=0;i<size;i++){
for(int j=0;j<size;j++)
cout<<M[i][j]<<" ";
cout<<endl;
}
}
//First PreOrder Traversal
void MatrixUtil(Node *root,int index){
if(root==NULL)return;
int preData=root->data;
//Since there is no ancestor for root node,
// so we doesn't assign it's value as 1
if(index==-1)index=root->data;
else M[index][preData]=1;
MatrixUtil(root->left,preData);
MatrixUtil(root->right,preData);
}
void Matrix(Node *root){
// Call Func MatrixUtil
MatrixUtil(root,-1);
//Applying Transitive Closure for the given Matrix
for(int i=0;i<size;i++){
for (int j = 0;j< size; j++) {
for(int k=0;k<size;k++)
M[j][k]=M[j][k]||(M[j][i]&&M[i][k]);
}
}
//Printing Matrix
printMatrix();
}
/* Driver program to test above functions*/
int main()
{
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);
Matrix(root);
return 0;
}
Java
// Java program to conancestor matrix for
// given tree.
import java.util.*;
class GFG
{
static final int size = 6;
static int [][]M = new int[size][size];
/* A binary tree node */
static class Node
{
int data;
Node left, right;
};
/* Helper function to create a new node */
static Node newnode(int data)
{
Node node = new Node();
node.data = data;
node.left = node.right = null;
return (node);
}
static void printMatrix()
{
for(int i = 0; i < size; i++)
{
for(int j = 0; j < size; j++)
System.out.print(M[i][j] + " ");
System.out.println();
}
}
// First PreOrder Traversal
static void MatrixUtil(Node root, int index)
{
if(root == null)return;
int preData = root.data;
// Since there is no ancestor for root node,
// so we doesn't assign it's value as 1
if(index == -1)index = root.data;
else M[index][preData] = 1;
MatrixUtil(root.left, preData);
MatrixUtil(root.right, preData);
}
static void Matrix(Node root)
{
// Call Func MatrixUtil
MatrixUtil(root, -1);
// Applying Transitive Closure for the given Matrix
for(int i = 0; i < size; i++)
{
for (int j = 0; j < size; j++)
{
for(int k = 0; k < size; k++)
{
if(M[j][k] == 1)
M[j][k] = 1;
else if((M[j][i] == 1 && M[i][k] == 1))
M[j][k] = 1;
}
}
}
// Printing Matrix
printMatrix();
}
/* Driver program to test above functions*/
public static void main(String[] args)
{
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);
Matrix(root);
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 program to construct ancestor # matrix for given tree. size = 6 M = [[0 for j in range(size)] for i in range(size)] # A binary tree node class Node: def __init__(self, data): self.left = None self.right = None self.data = data # Helper function to create a new node def newnode(data): temp = Node(data) return temp def printMatrix(): for i in range(size): for j in range(size): print(M[i][j], end = ' ') print() # First PreOrder Traversal def MatrixUtil(root, index): if (root == None): return preData = root.data # Since there is no ancestor for # root node, so we doesn't assign # it's value as 1 if (index == -1): index = root.data else: M[index][preData] = 1 MatrixUtil(root.left, preData) MatrixUtil(root.right, preData) def Matrix(root): # Call Func MatrixUtil MatrixUtil(root, -1) # Applying Transitive Closure # for the given Matrix for i in range(size): for j in range(size): for k in range(size): M[j][k] = (M[j][k] or (M[j][i] and M[i][k])) # Printing Matrix printMatrix() # Driver code if __name__=="__main__": 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) Matrix(root) # This code is contributed by rutvik_56
C#
// C# program to conancestor matrix for
// given tree.
using System;
class GFG
{
static readonly int size = 6;
static int [,]M = new int[size, size];
/* A binary tree node */
public
class Node
{
public
int data;
public
Node left, right;
};
/* Helper function to create a new node */
static Node newnode(int data)
{
Node node = new Node();
node.data = data;
node.left = node.right = null;
return (node);
}
static void printMatrix()
{
for(int i = 0; i < size; i++)
{
for(int j = 0; j < size; j++)
Console.Write(M[i, j] + " ");
Console.WriteLine();
}
}
// First PreOrder Traversal
static void MatrixUtil(Node root, int index)
{
if(root == null)
return;
int preData = root.data;
// Since there is no ancestor for root node,
// so we doesn't assign it's value as 1
if(index == -1)index = root.data;
else M[index,preData] = 1;
MatrixUtil(root.left, preData);
MatrixUtil(root.right, preData);
}
static void Matrix(Node root)
{
// Call Func MatrixUtil
MatrixUtil(root, -1);
// Applying Transitive Closure for the given Matrix
for(int i = 0; i < size; i++)
{
for (int j = 0; j < size; j++)
{
for(int k = 0; k < size; k++)
{
if(M[j, k] == 1)
M[j, k] = 1;
else if((M[j, i] == 1 && M[i, k] == 1))
M[j, k] = 1;
}
}
}
// Printing Matrix
printMatrix();
}
/* Driver code*/
public static void Main(String[] args)
{
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);
Matrix(root);
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// javascript program to conancestor matrix for
// given tree.
var size = 6;
var M = Array(size).fill().map(()=>Array(size).fill(0));
/* A binary tree node */
class Node {
constructor(val) {
this.data = val;
this.left = null;
this.right = null;
}
}
/* Helper function to create a new node */
function newnode(data) {
var node = new Node();
node.data = data;
node.left = node.right = null;
return (node);
}
function printMatrix() {
for (i = 0; i < size; i++) {
for (j = 0; j < size; j++)
document.write(M[i][j] + " ");
document.write("<br/>");
}
}
// First PreOrder Traversal
function MatrixUtil(root , index) {
if (root == null)
return;
var preData = root.data;
// Since there is no ancestor for root node,
// so we doesn't assign it's value as 1
if (index == -1)
index = root.data;
else
M[index][preData] = 1;
MatrixUtil(root.left, preData);
MatrixUtil(root.right, preData);
}
function Matrix(root) {
// Call Func MatrixUtil
MatrixUtil(root, -1);
// Applying Transitive Closure for the given Matrix
for (i = 0; i < size; i++)
{
for (j = 0; j < size; j++) {
for (k = 0; k < size; k++) {
if (M[j][k] == 1)
M[j][k] = 1;
else if ((M[j][i] == 1 && M[i][k] == 1))
M[j][k] = 1;
}
}
}
// Printing Matrix
printMatrix();
}
/* Driver program to test above functions */
var 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);
Matrix(root);
// This code is contributed by gauravrajput1
</script>
Producció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
La complejidad temporal de la solución anterior es O(n 2 ).
Espacio Auxiliar: O(n 2 )
¿Cómo hacer inversa: construir un árbol a partir de la array de antepasados?
Construir árbol a partir de array de antepasados
Este artículo es una contribución de Aarti_Rathi y Dheeraj Gupta . 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