Dado un árbol binario, necesitamos imprimir la vista inferior de izquierda a derecha. Un Node x está allí en la salida si x es el Node más bajo en su distancia horizontal. La distancia horizontal del hijo izquierdo de un Node x es igual a una distancia horizontal de x menos 1, y la de un hijo derecho es la distancia horizontal de x más 1.
Ejemplos:
20
/ \
8 22
/ \ \
5 3 25
/ \
10 14
Para el árbol anterior, la salida debe ser 5, 10, 3, 14, 25.
Si hay varios Nodes más abajo para una distancia horizontal desde la raíz, imprima el último en el recorrido de nivel. Por ejemplo, en el siguiente diagrama, 3 y 4 son los Nodes más inferiores a una distancia horizontal de 0, necesitamos imprimir 4.
20
/ \
8 22
/ \ / \
5 3 4 25
/ \
10 14
Para el árbol anterior, la salida debe ser 5 10 4 14 25.
Método 1 (usando cola): Los siguientes son pasos para imprimir la vista inferior del árbol binario.
- Ponemos los Nodes del árbol en una cola para el recorrido del orden de nivel.
- Comience con la distancia horizontal (hd) 0 del Node raíz y siga agregando un hijo izquierdo a la cola junto con la distancia horizontal como hd-1 y el hijo derecho como hd+1.
- Además, use un TreeMap que almacene pares clave-valor ordenados por clave.
- Cada vez que encontramos una nueva distancia horizontal o una distancia horizontal existente, coloque los datos del Node para la distancia horizontal como clave. Por primera vez se agregará al mapa, la próxima vez reemplazará el valor. Esto asegurará que el elemento más abajo para esa distancia horizontal esté presente en el mapa y si ve el árbol desde abajo, verá ese elemento.
A continuación se muestra la implementación de lo anterior:
C++
// C++ Program to print Bottom View of Binary Tree
#include<bits/stdc++.h>
using namespace std;
// Tree node class
struct Node
{
int data; //data of the node
int hd; //horizontal distance of the node
Node *left, *right; //left and right references
// Constructor of tree node
Node(int key)
{
data = key;
hd = INT_MAX;
left = right = NULL;
}
};
// Method that prints the bottom view.
void bottomView(Node *root)
{
if (root == NULL)
return;
// Initialize a variable 'hd' with 0
// for the root element.
int hd = 0;
// TreeMap which stores key value pair
// sorted on key value
map<int, int> m;
// Queue to store tree nodes in level
// order traversal
queue<Node *> q;
// Assign initialized horizontal distance
// value to root node and add it to the queue.
root->hd = hd;
q.push(root); // In STL, push() is used enqueue an item
// Loop until the queue is empty (standard
// level order loop)
while (!q.empty())
{
Node *temp = q.front();
q.pop(); // In STL, pop() is used dequeue an item
// Extract the horizontal distance value
// from the dequeued tree node.
hd = temp->hd;
// Put the dequeued tree node to TreeMap
// having key as horizontal distance. Every
// time we find a node having same horizontal
// distance we need to replace the data in
// the map.
m[hd] = temp->data;
// If the dequeued node has a left child, add
// it to the queue with a horizontal distance hd-1.
if (temp->left != NULL)
{
temp->left->hd = hd-1;
q.push(temp->left);
}
// If the dequeued node has a right child, add
// it to the queue with a horizontal distance
// hd+1.
if (temp->right != NULL)
{
temp->right->hd = hd+1;
q.push(temp->right);
}
}
// Traverse the map elements using the iterator.
for (auto i = m.begin(); i != m.end(); ++i)
cout << i->second << " ";
}
// Driver Code
int main()
{
Node *root = new Node(20);
root->left = new Node(8);
root->right = new Node(22);
root->left->left = new Node(5);
root->left->right = new Node(3);
root->right->left = new Node(4);
root->right->right = new Node(25);
root->left->right->left = new Node(10);
root->left->right->right = new Node(14);
cout << "Bottom view of the given binary tree :\n";
bottomView(root);
return 0;
}
Java
// Java Program to print Bottom View of Binary Tree
import java.util.*;
import java.util.Map.Entry;
// Tree node class
class Node
{
int data; //data of the node
int hd; //horizontal distance of the node
Node left, right; //left and right references
// Constructor of tree node
public Node(int key)
{
data = key;
hd = Integer.MAX_VALUE;
left = right = null;
}
}
//Tree class
class Tree
{
Node root; //root node of tree
// Default constructor
public Tree() {}
// Parameterized tree constructor
public Tree(Node node)
{
root = node;
}
// Method that prints the bottom view.
public void bottomView()
{
if (root == null)
return;
// Initialize a variable 'hd' with 0 for the root element.
int hd = 0;
// TreeMap which stores key value pair sorted on key value
Map<Integer, Integer> map = new TreeMap<>();
// Queue to store tree nodes in level order traversal
Queue<Node> queue = new LinkedList<Node>();
// Assign initialized horizontal distance value to root
// node and add it to the queue.
root.hd = hd;
queue.add(root);
// Loop until the queue is empty (standard level order loop)
while (!queue.isEmpty())
{
Node temp = queue.remove();
// Extract the horizontal distance value from the
// dequeued tree node.
hd = temp.hd;
// Put the dequeued tree node to TreeMap having key
// as horizontal distance. Every time we find a node
// having same horizontal distance we need to replace
// the data in the map.
map.put(hd, temp.data);
// If the dequeued node has a left child add it to the
// queue with a horizontal distance hd-1.
if (temp.left != null)
{
temp.left.hd = hd-1;
queue.add(temp.left);
}
// If the dequeued node has a right child add it to the
// queue with a horizontal distance hd+1.
if (temp.right != null)
{
temp.right.hd = hd+1;
queue.add(temp.right);
}
}
// Extract the entries of map into a set to traverse
// an iterator over that.
Set<Entry<Integer, Integer>> set = map.entrySet();
// Make an iterator
Iterator<Entry<Integer, Integer>> iterator = set.iterator();
// Traverse the map elements using the iterator.
while (iterator.hasNext())
{
Map.Entry<Integer, Integer> me = iterator.next();
System.out.print(me.getValue()+" ");
}
}
}
// Main driver class
public class BottomView
{
public static void main(String[] args)
{
Node root = new Node(20);
root.left = new Node(8);
root.right = new Node(22);
root.left.left = new Node(5);
root.left.right = new Node(3);
root.right.left = new Node(4);
root.right.right = new Node(25);
root.left.right.left = new Node(10);
root.left.right.right = new Node(14);
Tree tree = new Tree(root);
System.out.println("Bottom view of the given binary tree:");
tree.bottomView();
}
}
Python3
# Python3 program to print Bottom
# View of Binary Tree
# deque supports efficient pish and pop on both ends
from collections import deque
# Tree node class
class Node:
def __init__(self, key):
self.data = key
self.hd = float('inf')
self.left = None
self.right = None
# Method that prints the bottom view.
def bottomView(root):
if (root == None):
return
# Initialize a variable 'hd' with 0
# for the root element.
hd = 0
# Store minimum and maximum horizontal distance
# so that we do not have to sort keys at the end
min_hd, max_hd = 0, 0
hd_dict = dict()
# Queue to store tree nodes in level
# order traversal
q = deque()
# Assign initialized horizontal distance
# value to root node and add it to the queue.
root.hd = hd
q.append(root)
# Loop until the queue is empty (standard
# level order loop)
while q:
curr_node = q.popleft()
# Extract the horizontal distance value
# from the dequeued tree node.
hd = curr_node.hd
# Update the minimum and maximum hd
min_hd = min(min_hd, hd)
max_hd = max(max_hd, hd)
# Put the dequeued tree node to dictionary
# having key as horizontal distance. Every
# time we find a node having same horizontal
# distance we need to update the value in
# the map.
hd_dict[hd] = curr_node.data
# If the dequeued node has a left child, add
# it to the queue with a horizontal distance hd-1.
if curr_node.left:
curr_node.left.hd = hd - 1
q.append(curr_node.left)
# If the dequeued node has a right child, add
# it to the queue with a horizontal distance
# hd+1.
if curr_node.right:
curr_node.right.hd = hd + 1
q.append(curr_node.right)
# Traverse the map from least horizontal distance to
# most horizontal distance.
for i in range(min_hd, max_hd+1):
print(hd_dict[i], end = ' ')
# Driver Code
if __name__=='__main__':
root = Node(20)
root.left = Node(8)
root.right = Node(22)
root.left.left = Node(5)
root.left.right = Node(3)
root.right.left = Node(4)
root.right.right = Node(25)
root.left.right.left = Node(10)
root.left.right.right = Node(14)
print("Bottom view of the given binary tree :")
bottomView(root)
# This code is contributed by rutvik_56
C#
// C# program to print Bottom View of Binary Tree
using System;
using System.Collections;
using System.Collections.Generic;
// Tree node class
class Node
{
// Data of the node
public int data;
// Horizontal distance of the node
public int hd;
// left and right references
public Node left, right;
// Constructor of tree node
public Node(int key)
{
data = key;
hd = 1000000;
left = right = null;
}
}
// Tree class
class Tree
{
// Root node of tree
Node root;
// Default constructor
public Tree(){}
// Parameterized tree constructor
public Tree(Node node)
{
root = node;
}
// Method that prints the bottom view.
public void bottomView()
{
if (root == null)
return;
// Initialize a variable 'hd' with
// 0 for the root element.
int hd = 0;
// TreeMap which stores key value
// pair sorted on key value
SortedDictionary<int,
int> map = new SortedDictionary<int,
int>();
// Queue to store tree nodes in level order
// traversal
Queue queue = new Queue();
// Assign initialized horizontal distance
// value to root node and add it to the queue.
root.hd = hd;
queue.Enqueue(root);
// Loop until the queue is empty
// (standard level order loop)
while (queue.Count != 0)
{
Node temp = (Node) queue.Dequeue();
// Extract the horizontal distance value
// from the dequeued tree node.
hd = temp.hd;
// Put the dequeued tree node to TreeMap
// having key as horizontal distance.
// Every time we find a node having same
// horizontal distance we need to replace
// the data in the map.
map[hd] = temp.data;
// If the dequeued node has a left child
// add it to the queue with a horizontal
// distance hd-1.
if (temp.left != null)
{
temp.left.hd = hd - 1;
queue.Enqueue(temp.left);
}
// If the dequeued node has a right
// child add it to the queue with a
// horizontal distance hd+1.
if (temp.right != null)
{
temp.right.hd = hd + 1;
queue.Enqueue(temp.right);
}
}
foreach(int i in map.Values)
{
Console.Write(i + " ");
}
}
}
public class BottomView{
// Driver code
public static void Main(string[] args)
{
Node root = new Node(20);
root.left = new Node(8);
root.right = new Node(22);
root.left.left = new Node(5);
root.left.right = new Node(3);
root.right.left = new Node(4);
root.right.right = new Node(25);
root.left.right.left = new Node(10);
root.left.right.right = new Node(14);
Tree tree = new Tree(root);
Console.WriteLine("Bottom view of the " +
"given binary tree:");
tree.bottomView();
}
}
// This code is contributed by pratham76
Javascript
<script>
// JavaScript program to print Bottom View of Binary Tree
// Tree node class
class Node {
// Constructor of tree node
constructor(key) {
this.data = key; // Data of the node
this.hd = 1000000; // Horizontal distance of the node
this.left = null; // left and right references
this.right = null;
}
}
// Tree class
class Tree {
// Parameterized tree constructor
constructor(node) {
// Root node of tree
this.root = node;
}
// Method that prints the bottom view.
bottomView() {
if (this.root == null) return;
// Initialize a variable 'hd' with
// 0 for the root element.
var hd = 0;
// TreeMap which stores key value
// pair sorted on key value
var map = {};
// Queue to store tree nodes in level order
// traversal
var queue = [];
// Assign initialized horizontal distance
// value to root node and add it to the queue.
this.root.hd = hd;
queue.push(this.root);
// Loop until the queue is empty
// (standard level order loop)
while (queue.length != 0) {
var temp = queue.shift();
// Extract the horizontal distance value
// from the dequeued tree node.
hd = temp.hd;
// Put the dequeued tree node to TreeMap
// having key as horizontal distance.
// Every time we find a node having same
// horizontal distance we need to replace
// the data in the map.
map[hd] = temp.data;
// If the dequeued node has a left child
// add it to the queue with a horizontal
// distance hd-1.
if (temp.left != null) {
temp.left.hd = hd - 1;
queue.push(temp.left);
}
// If the dequeued node has a right
// child add it to the queue with a
// horizontal distance hd+1.
if (temp.right != null) {
temp.right.hd = hd + 1;
queue.push(temp.right);
}
}
for (const [key, value] of Object.entries(map).sort(
(a, b) => a[0] - b[0]
)) {
document.write(value + " ");
}
}
}
// Driver code
var root = new Node(20);
root.left = new Node(8);
root.right = new Node(22);
root.left.left = new Node(5);
root.left.right = new Node(3);
root.right.left = new Node(4);
root.right.right = new Node(25);
root.left.right.left = new Node(10);
root.left.right.right = new Node(14);
var tree = new Tree(root);
document.write("Bottom view of the " + "given binary tree:<br>");
tree.bottomView();
</script>
Producción
Bottom view of the given binary tree : 5 10 4 14 25
Método 2 (usando HashMap()): Cree un mapa donde la clave sea la distancia horizontal y el valor sea un par (a, b) donde a es el valor del Node y b es la altura del Node. Realice un recorrido de pedido anticipado del árbol. Si el Node actual a una distancia horizontal de h es el primero que hemos visto, insértelo en el mapa. De lo contrario, compare el Node con el existente en el mapa y si la altura del nuevo Node es mayor, actualice el Mapa.
A continuación se muestra la implementación de lo anterior:
C++
// C++ Program to print Bottom View of Binary Tree
#include <bits/stdc++.h>
#include <map>
using namespace std;
// Tree node class
struct Node
{
// data of the node
int data;
// horizontal distance of the node
int hd;
//left and right references
Node * left, * right;
// Constructor of tree node
Node(int key)
{
data = key;
hd = INT_MAX;
left = right = NULL;
}
};
void printBottomViewUtil(Node * root, int curr, int hd, map <int, pair <int, int>> & m)
{
// Base case
if (root == NULL)
return;
// If node for a particular
// horizontal distance is not
// present, add to the map.
if (m.find(hd) == m.end())
{
m[hd] = make_pair(root -> data, curr);
}
// Compare height for already
// present node at similar horizontal
// distance
else
{
pair < int, int > p = m[hd];
if (p.second <= curr)
{
m[hd].second = curr;
m[hd].first = root -> data;
}
}
// Recur for left subtree
printBottomViewUtil(root -> left, curr + 1, hd - 1, m);
// Recur for right subtree
printBottomViewUtil(root -> right, curr + 1, hd + 1, m);
}
void printBottomView(Node * root)
{
// Map to store Horizontal Distance,
// Height and Data.
map < int, pair < int, int > > m;
printBottomViewUtil(root, 0, 0, m);
// Prints the values stored by printBottomViewUtil()
map < int, pair < int, int > > ::iterator it;
for (it = m.begin(); it != m.end(); ++it)
{
pair < int, int > p = it -> second;
cout << p.first << " ";
}
}
int main()
{
Node * root = new Node(20);
root -> left = new Node(8);
root -> right = new Node(22);
root -> left -> left = new Node(5);
root -> left -> right = new Node(3);
root -> right -> left = new Node(4);
root -> right -> right = new Node(25);
root -> left -> right -> left = new Node(10);
root -> left -> right -> right = new Node(14);
cout << "Bottom view of the given binary tree :\n";
printBottomView(root);
return 0;
}
Java
// Java program to print Bottom View of Binary Tree
import java.io.*;
import java.lang.*;
import java.util.*;
class GFG{
// Tree node class
static class Node
{
// Data of the node
int data;
// Horizontal distance of the node
int hd;
// Left and right references
Node left, right;
// Constructor of tree node
public Node(int key)
{
data = key;
hd = Integer.MAX_VALUE;
left = right = null;
}
}
static void printBottomViewUtil(Node root, int curr, int hd,
TreeMap<Integer, int[]> m)
{
// Base case
if (root == null)
return;
// If node for a particular
// horizontal distance is not
// present, add to the map.
if (!m.containsKey(hd))
{
m.put(hd, new int[]{ root.data, curr });
}
// Compare height for already
// present node at similar horizontal
// distance
else
{
int[] p = m.get(hd);
if (p[1] <= curr)
{
p[1] = curr;
p[0] = root.data;
}
m.put(hd, p);
}
// Recur for left subtree
printBottomViewUtil(root.left, curr + 1,
hd - 1, m);
// Recur for right subtree
printBottomViewUtil(root.right, curr + 1,
hd + 1, m);
}
static void printBottomView(Node root)
{
// Map to store Horizontal Distance,
// Height and Data.
TreeMap<Integer, int[]> m = new TreeMap<>();
printBottomViewUtil(root, 0, 0, m);
// Prints the values stored by printBottomViewUtil()
for(int val[] : m.values())
{
System.out.print(val[0] + " ");
}
}
// Driver Code
public static void main(String[] args)
{
Node root = new Node(20);
root.left = new Node(8);
root.right = new Node(22);
root.left.left = new Node(5);
root.left.right = new Node(3);
root.right.left = new Node(4);
root.right.right = new Node(25);
root.left.right.left = new Node(10);
root.left.right.right = new Node(14);
System.out.println(
"Bottom view of the given binary tree:");
printBottomView(root);
}
}
// This code is contributed by Kingash
Python3
# Python3 program to print Bottom
# View of Binary Tree
class Node:
def __init__(self, key = None,
left = None,
right = None):
self.data = key
self.left = left
self.right = right
def printBottomView(root):
# Create a dictionary where
# key -> relative horizontal distance
# of the node from root node and
# value -> pair containing node's
# value and its level
d = dict()
printBottomViewUtil(root, d, 0, 0)
# Traverse the dictionary in sorted
# order of their keys and print
# the bottom view
for i in sorted(d.keys()):
print(d[i][0], end = " ")
def printBottomViewUtil(root, d, hd, level):
# Base case
if root is None:
return
# If current level is more than or equal
# to maximum level seen so far for the
# same horizontal distance or horizontal
# distance is seen for the first time,
# update the dictionary
if hd in d:
if level >= d[hd][1]:
d[hd] = [root.data, level]
else:
d[hd] = [root.data, level]
# recur for left subtree by decreasing
# horizontal distance and increasing
# level by 1
printBottomViewUtil(root.left, d, hd - 1,
level + 1)
# recur for right subtree by increasing
# horizontal distance and increasing
# level by 1
printBottomViewUtil(root.right, d, hd + 1,
level + 1)
# Driver Code
if __name__ == '__main__':
root = Node(20)
root.left = Node(8)
root.right = Node(22)
root.left.left = Node(5)
root.left.right = Node(3)
root.right.left = Node(4)
root.right.right = Node(25)
root.left.right.left = Node(10)
root.left.right.right = Node(14)
print("Bottom view of the given binary tree :")
printBottomView(root)
# This code is contributed by tusharroy
Producción
Bottom view of the given binary tree : 5 10 4 14 25
Método 3 (Llamar a la función recursivamente):
- Paso 1: primero cree la clase Node y declare los datos int, los Nodes izquierdo y derecho.
- Paso 2: Cree el constructor del Node de clase.
- Paso 3: Cree la clase principal y declare el Node raíz. En el método principal, declare e inicialice los valores del Node del árbol.
- Paso 4: Ahora, llama a la función estática print_bottom_view() con el Node raíz como argumento.
- Paso 5: compruebe si el Node actual es nulo.
- Paso 6: ahora, verifique si el Node izquierdo y el lado derecho del Node actual son nulos. Si ambos Nodes son nulos, estará en la parte inferior del árbol. El, simplemente imprime los datos en ese Node.
- Paso 7: para buscar el siguiente Node, llame a la función con el mismo método especificando print_bottom_view(n.left) y print_bottom_view(n.right). Llamará a las funciones hasta que el valor del Node actual se vuelva nulo.
Java
/*package whatever //do not write package name here */
import java.io.*;
class Node // tree node class
{
int data;
Node right,left;
public Node(int d) //constructor of the Node
{
data=d;
left=null;
right=null;
}
}
class GFG {
Node root;
public static void print_bottom_view(Node n)
{
if(n==null) //check whether the node is null
return;
if(n.left==null && n.right==null) // check whether the right and left side of the current nodes are null
{
System.out.print(n.data+" ");
}
print_bottom_view(n.left);
print_bottom_view(n.right);
}
public static void main (String[] args) {
GFG tree=new GFG();
tree.root=new Node(20);
tree.root.left=new Node(8);
tree.root.right=new Node(22);
tree.root.left.left=new Node(5);
tree.root.left.right=new Node(3);
tree.root.right.left=new Node(4);
tree.root.right.right=new Node(25);
tree.root.left.right.left=new Node(10);
tree.root.left.right.right=new Node(14);
System.out.println("Bottom View of the Tree :");
print_bottom_view(tree.root); //calling the function
}
}
//contributed by keerthikarathan123
Producción
Bottom View of the Tree : 5 10 14 4 25
Python3
# code
class Node:
def __init__(self, key = None,
left = None,
right = None):
self.data = key
self.left = left
self.right = right
def print_bottom_view(root):
if root is None:
return
if root.left is None and root.right is None :
print(root.data,end=" ")
print_bottom_view(root.left)
print_bottom_view(root.right)
if __name__ == '__main__':
root = Node(20)
root.left = Node(8)
root.right = Node(22)
root.left.left = Node(5)
root.left.right = Node(3)
root.right.left = Node(4)
root.right.right = Node(25)
root.left.right.left = Node(10)
root.left.right.right = Node(14)
print("Bottom view of the tree :")
print_bottom_view(root)
#contributed by keerthikarathan123
Producción
Bottom view of the tree : 5 10 14 4 25
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