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 la 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 que el árbol se puede construir 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:
0
/ \
1 2
Input:
{ {0, 0, 0, 1, 1, 0},
{0, 0, 0, 0, 0, 1},
{1, 1, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0}
};
Output:
2
/ \
0 1
/ \ /
3 4 5
Consulte este artículo para conocer el enfoque de abajo hacia arriba : construir un árbol a partir de la array de antepasados.
Enfoque:
primero, encontraremos la raíz del árbol. La raíz es aquella cuya columna tiene todos ceros. Una vez que encontramos la raíz, podemos construir un árbol desde la raíz utilizando el enfoque recursivo DFS .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Node structure for
// Binary Tree
struct Node {
int data;
Node *left, *right;
Node(int _val)
{
data = _val;
left = right = NULL;
}
};
// Function to return
// root index of a
// binary tree
int getRootIndex(vector<vector<int> >& arr)
{
int root_index = -1;
for (int j = 0; j < arr[0].size(); j++) {
int count = 0;
for (int i = 0; i < arr.size(); i++)
if (arr[i][j] == 0) {
count++;
}
if (count == arr.size()) {
root_index = j;
break;
}
}
return root_index;
}
// Function to print
// in-order traversal of
// a tree
void printInorder(Node* node)
{
if (node == NULL) {
return;
}
printInorder(node->left);
cout << node->data << " ";
printInorder(node->right);
}
// Function to generate binary
// tree from parent matrix
Node* createTreeRec(vector<vector<int> >& arr, int index)
{
Node* node = new Node(index);
// If left is 1 then create
// left child. (for 1st one in row)
// If left is 2 then create
// right child.(for 1st one in row)
int left = 1;
for (int j = 0; j < arr[index].size(); j++) {
if (arr[index][j] == 1) {
// recur for left sub-tree
if (left == 1) {
node->left = createTreeRec(arr, j);
}
// recur for right sub-tree
else if (left == 2) {
node->right = createTreeRec(arr, j);
}
left++;
}
}
return node;
}
// Driver code
int main()
{
// Assuming leftmost 1 in a
// row is left child, if exists
// and rightmost 1 in a row
// is right child, if exists
vector<vector<int> > arr = {
{ 0, 0, 0, 1, 1, 0 },
{ 0, 0, 0, 0, 0, 1 },
{ 1, 1, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0 },
};
int root_index = getRootIndex(arr);
Node* root = createTreeRec(arr, root_index);
// Printing inorder traversal
// of tree to check the output
printInorder(root);
return 0;
}
Java
// Java implementation of
// the above approach
class GFG
{
// Node structure for
// Binary Tree
static class Node
{
int data;
Node left, right;
Node(int _val)
{
data = _val;
left = right = null;
}
};
// Function to return
// root index of a
// binary tree
static int getRootIndex(int [][]arr)
{
int root_index = -1;
for (int j = 0; j < arr[0].length; j++)
{
int count = 0;
for (int i = 0; i < arr.length; i++)
if (arr[i][j] == 0)
{
count++;
}
if (count == arr.length)
{
root_index = j;
break;
}
}
return root_index;
}
// Function to print
// in-order traversal of
// a tree
static void printInorder(Node node)
{
if (node == null)
{
return;
}
printInorder(node.left);
System.out.print(node.data + " ");
printInorder(node.right);
}
// Function to generate binary
// tree from parent matrix
static Node createTreeRec(int [][]arr, int index)
{
Node node = new Node(index);
// If left is 1 then create
// left child. (for 1st one in row)
// If left is 2 then create
// right child.(for 1st one in row)
int left = 1;
for (int j = 0; j < arr[index].length; j++)
{
if (arr[index][j] == 1)
{
// recur for left sub-tree
if (left == 1)
{
node.left = createTreeRec(arr, j);
}
// recur for right sub-tree
else if (left == 2)
{
node.right = createTreeRec(arr, j);
}
left++;
}
}
return node;
}
// Driver code
public static void main(String[] args)
{
// Assuming leftmost 1 in a
// row is left child, if exists
// and rightmost 1 in a row
// is right child, if exists
int[][] arr = {
{ 0, 0, 0, 1, 1, 0 },
{ 0, 0, 0, 0, 0, 1 },
{ 1, 1, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0 },
};
int root_index = getRootIndex(arr);
Node root = createTreeRec(arr, root_index);
// Printing inorder traversal
// of tree to check the output
printInorder(root);
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 implementation of # the above approach # Node structure for # Binary Tree class Node: def __init__(self, data): self.data = data self.left = None self.right = None # Function to return # root index of a # binary tree def getRootIndex(arr : list) -> int: root_index = -1 for j in range(len(arr)): count = 0 for i in range(len(arr)): if (arr[i][j] == 0): count += 1 if (count == len(arr)): root_index = j break return root_index # Function to print # in-order traversal of # a tree def printInorder(node : Node) -> None: if (node is None): return printInorder(node.left) print(node.data, end = " ") printInorder(node.right) # Function to generate binary # tree from parent matrix def createTreeRec(arr : list, index : int) -> Node: node = Node(index) # If left is 1 then create # left child. (for 1st one in row) # If left is 2 then create # right child.(for 1st one in row) left = 1 for j in range(len(arr[index])): if (arr[index][j] == 1): # recur for left sub-tree if (left == 1): node.left = createTreeRec(arr, j) # recur for right sub-tree elif (left == 2): node.right = createTreeRec(arr, j) left += 1 return node # Driver code if __name__ == "__main__": # Assuming leftmost 1 in a # row is left child, if exists # and rightmost 1 in a row # is right child, if exists arr = [[0, 0, 0, 1, 1, 0], [0, 0, 0, 0, 0, 1], [1, 1, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0]] root_index = getRootIndex(arr) root = createTreeRec(arr, root_index) # Printing inorder traversal # of tree to check the output printInorder(root) # This code is contributed by sanjeev2552
C#
// C# implementation of
// the above approach
using System;
class GFG
{
// Node structure for
// Binary Tree
class Node
{
public int data;
public Node left, right;
public Node(int _val)
{
data = _val;
left = right = null;
}
};
// Function to return
// root index of a
// binary tree
static int getRootIndex(int [,]arr)
{
int root_index = -1;
for (int j = 0; j < arr.GetLength(0); j++)
{
int count = 0;
for (int i = 0; i < arr.GetLength(1); i++)
if (arr[i, j] == 0)
{
count++;
}
if (count == arr.GetLength(0))
{
root_index = j;
break;
}
}
return root_index;
}
// Function to print
// in-order traversal of
// a tree
static void printInorder(Node node)
{
if (node == null)
{
return;
}
printInorder(node.left);
Console.Write(node.data + " ");
printInorder(node.right);
}
// Function to generate binary
// tree from parent matrix
static Node createTreeRec(int [,]arr, int index)
{
Node node = new Node(index);
// If left is 1 then create
// left child. (for 1st one in row)
// If left is 2 then create
// right child.(for 1st one in row)
int left = 1;
for (int j = 0; j < arr.GetLength(1); j++)
{
if (arr[index, j] == 1)
{
// recur for left sub-tree
if (left == 1)
{
node.left = createTreeRec(arr, j);
}
// recur for right sub-tree
else if (left == 2)
{
node.right = createTreeRec(arr, j);
}
left++;
}
}
return node;
}
// Driver code
public static void Main(String[] args)
{
// Assuming leftmost 1 in a
// row is left child, if exists
// and rightmost 1 in a row
// is right child, if exists
int[,] arr = {
{ 0, 0, 0, 1, 1, 0 },
{ 0, 0, 0, 0, 0, 1 },
{ 1, 1, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0 },
};
int root_index = getRootIndex(arr);
Node root = createTreeRec(arr, root_index);
// Printing inorder traversal
// of tree to check the output
printInorder(root);
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// JavaScript implementation of
// the above approach
// Node structure for
// Binary Tree
class Node
{
constructor(_val)
{
this.data = _val;
this.left = null;
this.right = null;
}
};
// Function to return
// root index of a
// binary tree
function getRootIndex(arr)
{
var root_index = -1;
for(var j = 0; j < arr.length; j++)
{
var count = 0;
for (var i = 0; i < arr.length; i++)
if (arr[i][j] == 0)
{
count++;
}
if (count == arr[0].length)
{
root_index = j;
break;
}
}
return root_index;
}
// Function to print
// in-order traversal of
// a tree
function printInorder(node)
{
if (node == null)
{
return;
}
printInorder(node.left);
document.write(node.data + " ");
printInorder(node.right);
}
// Function to generate binary
// tree from parent matrix
function createTreeRec(arr, index)
{
var node = new Node(index);
// If left is 1 then create
// left child. (for 1st one in row)
// If left is 2 then create
// right child.(for 1st one in row)
var left = 1;
for (var j = 0; j < arr.length; j++)
{
if (arr[index][j] == 1)
{
// recur for left sub-tree
if (left == 1)
{
node.left = createTreeRec(arr, j);
}
// recur for right sub-tree
else if (left == 2)
{
node.right = createTreeRec(arr, j);
}
left++;
}
}
return node;
}
// Driver code
// Assuming leftmost 1 in a
// row is left child, if exists
// and rightmost 1 in a row
// is right child, if exists
var arr = [
[ 0, 0, 0, 1, 1, 0 ],
[ 0, 0, 0, 0, 0, 1 ],
[ 1, 1, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0, 0 ]
];
var root_index = getRootIndex(arr);
var root = createTreeRec(arr, root_index);
// Printing inorder traversal
// of tree to check the output
printInorder(root);
</script>
Producción:
3 0 4 2 5 1
Publicación traducida automáticamente
Artículo escrito por Hrudwik_Dhulipalla y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA