Vista inferior de un árbol binario usando recursividad

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *