Dado un árbol binario, la tarea es encontrar la vista inferior de un árbol binario usando recursividad.
Ejemplos:
Input:
1
\
2
\
4
/ \
3 5
Output: 1 3 4 5
Input:
20
/ \
8 22
/ \ / \
5 10 21 25
/ \
9 14
Output: 5 9 21 14 25
Enfoque:
Podemos hacerlo usando recursividad y 2 arreglos cada uno con tamaño 2n+1 (en el peor de los casos), donde n = número de elementos en el árbol dado. Aquí, tomamos una Variable x que determina su Distancia Horizontal. Sea x la distancia horizontal de un Node. Ahora, el hijo de la izquierda tendrá una distancia horizontal de x-1 (x menos 1) y el hijo de la derecha tendrá una distancia horizontal de x+1 (x más 1). Tomar como prioridad otra Variable ‘p’ que decidirá a qué nivel pertenece este elemento.
1 (x=0, p=0)
\
2 (x=1, p=1)
\
4 (x=2, p=2)
/ \
(x=1, p=3) 3 5 (x=3, p=3)
Mientras atraviesa el árbol de la manera Derecha-> Node-> Izquierda, asigne x y p a cada Node y simultáneamente inserte los datos del Node en la primera array si la array está vacía en la posición (mid+x). Si la array no está vacía y un Node con mayor Prioridad ( p ) viene a actualizar la array con los datos de este Node como posición (mid+x). La segunda array mantendrá la prioridad (p) de cada Node insertado en el código de verificación de la primera array para una mejor comprensión.
A continuación se muestra la implementación del enfoque anterior:
C++
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
// left and right references
Node *left, *right;
// Constructor of tree Node
Node(int key)
{
data = key;
left = right = NULL;
}
};
int l = 0, r = 0;
int N;
// Function to generate bottom view of binary tree
void Bottom(Node* root, int arr[], int arr2[], int x, int p,
int mid)
{
// Base case
if (root == NULL)
return;
// To store leftmost value of x in l
if (x < l)
l = x;
// To store rightmost value of x in r
if (x > r)
r = x;
// To check if arr is empty at mid+x
if (arr[mid + x] == INT_MIN) {
// Insert data of Node at arr[mid+x]
arr[mid + x] = root->data;
// Insert priority of that Node at arr2[mid+x]
arr2[mid + x] = p;
}
// If not empty and priotiy of previously inserted Node
// is less than current*/
else if (arr2[mid + x] < p) {
// Insert current Node data at arr[mid+x]
arr[mid + x] = root->data;
// Insert priotiy of that Node at arr2[mid +x]
arr2[mid + x] = p;
}
// Go right first then left
Bottom(root->right, arr, arr2, x + 1, p + 1, mid);
Bottom(root->left, arr, arr2, x - 1, p + 1, mid);
}
// Utility function to generate bottom view of a biany tree
void bottomView(struct Node* root)
{
int arr[2 * N + 1];
int arr2[2 * N + 1];
for (int i = 0; i < 2 * N + 1; i++) {
arr[i] = INT_MIN;
arr2[i] = INT_MIN;
}
int mid = N, x = 0, p = 0;
Bottom(root, arr, arr2, x, p, mid);
for (int i = mid + l; i <= mid + r; i++)
cout << arr[i] << " ";
}
// Driver code
int main()
{
N = 5;
Node* root = new Node(1);
root->right = new Node(2);
root->right->right = new Node(4);
root->right->right->left = new Node(3);
root->right->right->right = new Node(5);
bottomView(root);
return 0;
}
// This code is contributed by Sania Kumari Gupta
// (kriSania804)
C
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node *left, *right;
} Node;
/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */
Node* newNode(int data)
{
Node* new_node = (Node*)malloc(sizeof(Node));
new_node->data = data;
new_node->left = new_node->right = NULL;
return new_node;
}
int l = 0, r = 0;
int N;
// Function to generate bottom view of binary tree
void Bottom(Node* root, int arr[], int arr2[], int x, int p,
int mid)
{
// Base case
if (root == NULL)
return;
// To store leftmost value of x in l
if (x < l)
l = x;
// To store rightmost value of x in r
if (x > r)
r = x;
// To check if arr is empty at mid+x
if (arr[mid + x] == INT_MIN) {
// Insert data of Node at arr[mid+x]
arr[mid + x] = root->data;
// Insert priority of that Node at arr2[mid+x]
arr2[mid + x] = p;
}
// If not empty and priotiy of previously inserted Node
// is less than current*/
else if (arr2[mid + x] < p) {
// Insert current Node data at arr[mid+x]
arr[mid + x] = root->data;
// Insert priotiy of that Node at arr2[mid +x]
arr2[mid + x] = p;
}
// Go right first then left
Bottom(root->right, arr, arr2, x + 1, p + 1, mid);
Bottom(root->left, arr, arr2, x - 1, p + 1, mid);
}
// Utility function to generate bottom view of a biany tree
void bottomView(struct Node* root)
{
int arr[2 * N + 1];
int arr2[2 * N + 1];
for (int i = 0; i < 2 * N + 1; i++) {
arr[i] = INT_MIN;
arr2[i] = INT_MIN;
}
int mid = N, x = 0, p = 0;
Bottom(root, arr, arr2, x, p, mid);
for (int i = mid + l; i <= mid + r; i++)
printf("%d ", arr[i]);
}
// Driver code
int main()
{
N = 5;
Node* root = newNode(1);
root->right = newNode(2);
root->right->right = newNode(4);
root->right->right->left = newNode(3);
root->right->right->right = newNode(5);
bottomView(root);
return 0;
}
// This code is contributed by Sania Kumari Gupta
// (kriSania804)
Java
class GFG {
static class Node {
int data;
// left and right references
Node left, right;
// Constructor of tree Node
public Node(int key)
{
data = key;
left = right = null;
}
};
static int l = 0, r = 0, N;
// Function to generate bottom view of binary tree
static void Bottom(Node root, int arr[], int arr2[],
int x, int p, int mid)
{
// Base case
if (root == null)
return;
// To store leftmost value of x in l
if (x < l)
l = x;
// To store rightmost value of x in r
if (x > r)
r = x;
// To check if arr is empty at mid+x
if (arr[mid + x] == Integer.MIN_VALUE) {
// Insert data of Node at arr[mid+x]
arr[mid + x] = root.data;
// Insert priority of that Node at arr2[mid+x]
arr2[mid + x] = p;
}
// If not empty and priotiy of previously inserted
// Node is less than current
else if (arr2[mid + x] < p) {
// Insert current Node data at arr[mid+x]
arr[mid + x] = root.data;
// Insert priotiy of that Node at arr2[mid +x]
arr2[mid + x] = p;
}
// Go right first then left
Bottom(root.right, arr, arr2, x + 1, p + 1, mid);
Bottom(root.left, arr, arr2, x - 1, p + 1, mid);
}
// Utility function to generate bottom view of a biany
// tree
static void bottomView(Node root)
{
int[] arr = new int[2 * N + 1];
int[] arr2 = new int[2 * N + 1];
for (int i = 0; i < 2 * N + 1; i++) {
arr[i] = Integer.MIN_VALUE;
arr2[i] = Integer.MIN_VALUE;
}
int mid = N, x = 0, p = 0;
Bottom(root, arr, arr2, x, p, mid);
for (int i = mid + l; i <= mid + r; i++)
System.out.print(arr[i] + " ");
}
// Driver code
public static void main(String[] args)
{
N = 5;
Node root = new Node(1);
root.right = new Node(2);
root.right.right = new Node(4);
root.right.right.left = new Node(3);
root.right.right.right = new Node(5);
bottomView(root);
}
}
// This code is contributed by Sania Kumari Gupta
// (kriSania804)
Python3
class Node: def __init__(self, data): self.data = data self.left = None self.right = None l = 0 r = 0 INT_MIN = -(2**32) # Function to generate # bottom view of # binary tree def Bottom(root, arr, arr2, x, p, mid): global INT_MIN, l, r # Base case if (root == None): return if (x < l): # To store leftmost # value of x in l l = x # To store rightmost # value of x in r if (x > r): r = x # To check if arr # is empty at mid+x if (arr[mid + x] == INT_MIN): # Insert data of Node # at arr[mid+x] arr[mid + x] = root.data # Insert priority of # that Node at arr2[mid+x] arr2[mid + x] = p # If not empty and priotiy # of previously inserted # Node is less than current*/ elif (arr2[mid + x] < p): # Insert current # Node data at arr[mid+x] arr[mid + x] = root.data # Insert priotiy of # that Node at arr2[mid +x] arr2[mid + x] = p # Go right first # then left Bottom(root.right, arr, arr2, x + 1, p + 1, mid) Bottom(root.left, arr, arr2, x - 1, p + 1, mid) # Utility function # to generate bottom # view of a biany tree def bottomView(root): global INT_MIN arr = [0]*(2 * N + 1) arr2 = [0]*(2 * N + 1) for i in range(2 * N + 1): arr[i] = INT_MIN arr2[i] = INT_MIN mid = N x = 0 p = 0 Bottom(root, arr, arr2, x, p, mid) for i in range(mid + l,mid + r + 1): print(arr[i], end = " ") # Driver code N = 5 root = Node(1) root.right = Node(2) root.right.right = Node(4) root.right.right.left = Node(3) root.right.right.right = Node(5) bottomView(root) # This code is contributed by SHUBHAMSINGH10
C#
using System;
class GFG{
class Node{
public int data;
// left and right references
public Node left, right;
// Constructor of tree Node
public Node(int key)
{
data = key;
left = right = null;
}
};
static int l = 0, r = 0, N;
// Function to generate
// bottom view of binary tree
static void Bottom(Node root, int []arr,
int []arr2, int x,
int p, int mid)
{
// Base case
if (root == null)
{
return;
}
if (x < l)
{
// To store leftmost
// value of x in l
l = x;
}
// To store rightmost
// value of x in r
if (x > r)
{
r = x;
}
// To check if arr
// is empty at mid+x
if (arr[mid + x] == Int32.MinValue)
{
// Insert data of Node
// at arr[mid+x]
arr[mid + x] = root.data;
// Insert priority of
// that Node at arr2[mid+x]
arr2[mid + x] = p;
}
// If not empty and priotiy
// of previously inserted
// Node is less than current*/
else if (arr2[mid + x] < p)
{
// Insert current
// Node data at arr[mid+x]
arr[mid + x] = root.data;
// Insert priotiy of
// that Node at arr2[mid +x]
arr2[mid + x] = p;
}
// Go right first
// then left
Bottom(root.right, arr, arr2,
x + 1, p + 1, mid);
Bottom(root.left, arr, arr2,
x - 1, p + 1, mid);
}
// Utility function to generate
// bottom view of a biany tree
static void bottomView(Node root)
{
int[] arr = new int[2 * N + 1];
int[] arr2 = new int[2 * N + 1];
for(int i = 0; i < 2 * N + 1; i++)
{
arr[i] = Int32.MinValue;
arr2[i] = Int32.MinValue;
}
int mid = N, x = 0, p = 0;
Bottom(root, arr, arr2, x, p, mid);
for(int i = mid + l; i <= mid + r; i++)
{
Console.Write(arr[i] + " ");
}
}
// Driver code
public static void Main(string[] args)
{
N = 5;
Node root = new Node(1);
root.right = new Node(2);
root.right.right = new Node(4);
root.right.right.left = new Node(3);
root.right.right.right = new Node(5);
bottomView(root);
}
}
// This code is contributed by rutvik_56
Javascript
<script>
class Node{
// Constructor of tree Node
constructor(key)
{
this.data = key;
this.left = null;
this.right = null;
}
};
var l = 0, r = 0, N;
// Function to generate
// bottom view of binary tree
function Bottom(root, arr, arr2, x, p, mid)
{
// Base case
if (root == null)
{
return;
}
if (x < l)
{
// To store leftmost
// value of x in l
l = x;
}
// To store rightmost
// value of x in r
if (x > r)
{
r = x;
}
// To check if arr
// is empty at mid+x
if (arr[mid + x] == -1000000000)
{
// Insert data of Node
// at arr[mid+x]
arr[mid + x] = root.data;
// Insert priority of
// that Node at arr2[mid+x]
arr2[mid + x] = p;
}
// If not empty and priotiy
// of previously inserted
// Node is less than current*/
else if (arr2[mid + x] < p)
{
// Insert current
// Node data at arr[mid+x]
arr[mid + x] = root.data;
// Insert priotiy of
// that Node at arr2[mid +x]
arr2[mid + x] = p;
}
// Go right first
// then left
Bottom(root.right, arr, arr2,
x + 1, p + 1, mid);
Bottom(root.left, arr, arr2,
x - 1, p + 1, mid);
}
// Utility function to generate
// bottom view of a biany tree
function bottomView(root)
{
var arr = Array(2*N +1).fill(-1000000000);
var arr2 = Array(2*N +1).fill(-1000000000);
var mid = N, x = 0, p = 0;
Bottom(root, arr, arr2, x, p, mid);
for(var i = mid + l; i <= mid + r; i++)
{
document.write(arr[i] + " ");
}
}
// Driver code
N = 5;
var root = new Node(1);
root.right = new Node(2);
root.right.right = new Node(4);
root.right.right.left = new Node(3);
root.right.right.right = new Node(5);
bottomView(root);
</script>
Producción:
1 3 4 5
Complejidad de tiempo : O (N) donde N es el número de Nodes en un árbol binario dado
Publicación traducida automáticamente
Artículo escrito por badrivishal142 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA