La vista superior de un árbol binario es el conjunto de Nodes visibles cuando el árbol se ve desde arriba. Dado un árbol binario, imprima la vista superior del mismo. Los Nodes de salida deben imprimirse de izquierda a derecha .
Nota : hay un Node x en la salida si x es el Node superior a su distancia horizontal. La distancia horizontal del hijo izquierdo de un Node x es igual a la distancia horizontal de x menos 1, y la del hijo derecho es la distancia horizontal de x más 1.
Input:
1
/ \
2 3
/ \ / \
4 5 6 7
Output: Top view: 4 2 1 3 7
Input:
1
/ \
2 3
\
4
\
5
\
6
Output: Top view: 2 1 3 6
La idea es hacer algo similar a Vertical Order Traversal . Al igual que Vertical Order Traversal , necesitamos agrupar Nodes de la misma distancia horizontal. Hacemos un recorrido de orden de nivel para que el Node superior en un Node horizontal se visite antes que cualquier otro Node de la misma distancia horizontal debajo de él. Se usa un mapa para mapear la distancia horizontal del Node con los datos del Node y la distancia vertical del Node.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to print Top View of Binary Tree
// using hashmap and recursion
#include <bits/stdc++.h>
using namespace std;
// Node structure
struct Node {
// Data of the node
int data;
// Horizontal Distance of the node
int hd;
// Reference to left node
struct Node* left;
// Reference to right node
struct Node* right;
};
// Initialising node
struct Node* newNode(int data)
{
struct Node* node = new Node;
node->data = data;
node->hd = INT_MAX;
node->left = NULL;
node->right = NULL;
return node;
}
void printTopViewUtil(Node* root, int height,
int hd, map<int, pair<int, int> >& m)
{
// Base Case
if (root == NULL)
return;
// If the node for particular horizontal distance
// is not present in the map, add it.
// For top view, we consider the first element
// at horizontal distance in level order traversal
if (m.find(hd) == m.end()) {
m[hd] = make_pair(root->data, height);
}
else{
pair<int, int> p = (m.find(hd))->second;
if (p.second > height) {
m.erase(hd);
m[hd] = make_pair(root->data, height);
}
}
// Recur for left and right subtree
printTopViewUtil(root->left, height + 1, hd - 1, m);
printTopViewUtil(root->right, height + 1, hd + 1, m);
}
void printTopView(Node* root)
{
// Map to store horizontal distance,
// height and node's data
map<int, pair<int, int> > m;
printTopViewUtil(root, 0, 0, m);
// Print the node's value stored by printTopViewUtil()
for (map<int, pair<int, int> >::iterator it = m.begin();
it != m.end(); it++) {
pair<int, int> p = it->second;
cout << p.first << " ";
}
}
int main()
{
Node* root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->right = newNode(4);
root->left->right->right = newNode(5);
root->left->right->right->right = newNode(6);
cout << "Top View : ";
printTopView(root);
return 0;
}
Java
// Java Program to print Top View of Binary Tree
// using hashmap and recursion
import java.util.*;
class GFG {
// Node structure
static class Node {
// Data of the node
int data;
// Reference to left node
Node left;
// Reference to right node
Node right;
};
static class pair {
int data, height;
public pair(int data, int height)
{
this.data = data;
this.height = height;
}
}
// Initialising node
static Node newNode(int data)
{
Node node = new Node();
node.data = data;
node.left = null;
node.right = null;
return node;
}
static void printTopViewUtil(Node root, int height,
int hd,
Map<Integer, pair> m)
{
// Base Case
if (root == null)
return;
// If the node for particular horizontal distance
// is not present in the map, add it.
// For top view, we consider the first element
// at horizontal distance in level order traversal
if (!m.containsKey(hd)) {
m.put(hd, new pair(root.data, height));
}
else {
pair p = m.get(hd);
if (p.height >= height) {
m.put(hd, new pair(root.data, height));
}
}
// Recur for left and right subtree
printTopViewUtil(root.left, height + 1, hd - 1, m);
printTopViewUtil(root.right, height + 1, hd + 1, m);
}
static void printTopView(Node root)
{
// Map to store horizontal distance,
// height and node's data
Map<Integer, pair> m = new TreeMap<>();
printTopViewUtil(root, 0, 0, m);
// Print the node's value stored by
// printTopViewUtil()
for (Map.Entry<Integer, pair> it : m.entrySet()) {
pair p = it.getValue();
System.out.print(p.data + " ");
}
}
// Driver code
public static void main(String[] args)
{
Node root = newNode(1);
root.left = newNode(2);
root.right = newNode(3);
root.left.right = newNode(4);
root.left.right.right = newNode(5);
root.left.right.right.right = newNode(6);
System.out.print("Top View : ");
printTopView(root);
}
}
Python3
# Python3 Program to prTop View of
# Binary Tree using hash and recursion
from collections import OrderedDict
# A binary tree node
class newNode:
# A constructor to create a
# new Binary tree Node
def __init__(self, data):
self.data = data
self.left = None
self.right = None
self.hd = 2**32
def printTopViewUtil(root, height, hd, m):
# Base Case
if (root == None):
return
# If the node for particular horizontal
# distance is not present in the map, add it.
# For top view, we consider the first element
# at horizontal distance in level order traversal
if hd not in m :
m[hd] = [root.data, height]
else:
p = m[hd]
if p[1] > height:
m[hd] = [root.data, height]
# Recur for left and right subtree
printTopViewUtil(root.left,
height + 1, hd - 1, m)
printTopViewUtil(root.right,
height + 1, hd + 1, m)
def printTopView(root):
# to store horizontal distance,
# height and node's data
m = OrderedDict()
printTopViewUtil(root, 0, 0, m)
# Print the node's value stored
# by printTopViewUtil()
for i in sorted(list(m)):
p = m[i]
print(p[0], end = " ")
# Driver Code
root = newNode(1)
root.left = newNode(2)
root.right = newNode(3)
root.left.right = newNode(4)
root.left.right.right = newNode(5)
root.left.right.right.right = newNode(6)
print("Top View : ", end = "")
printTopView(root)
# This code is contributed by SHUBHAMSINGH10
C#
// C# program to print Top View of Binary
// Tree using hashmap and recursion
using System;
using System.Collections.Generic;
class GFG{
// Node structure
class Node
{
// Data of the node
public int data;
// Reference to left node
public Node left;
// Reference to right node
public Node right;
};
class pair
{
public int data, height;
public pair(int data, int height)
{
this.data = data;
this.height = height;
}
}
// Initialising node
static Node newNode(int data)
{
Node node = new Node();
node.data = data;
node.left = null;
node.right = null;
return node;
}
static void printTopViewUtil(Node root, int height,
int hd,
SortedDictionary<int, pair> m)
{
// Base Case
if (root == null)
return;
// If the node for particular horizontal distance
// is not present in the map, add it.
// For top view, we consider the first element
// at horizontal distance in level order traversal
if (!m.ContainsKey(hd))
{
m[hd] = new pair(root.data, height);
}
else
{
pair p = m[hd];
if (p.height >= height)
{
m[hd] = new pair(root.data, height);
}
}
// Recur for left and right subtree
printTopViewUtil(root.left, height + 1,
hd - 1, m);
printTopViewUtil(root.right, height + 1,
hd + 1, m);
}
static void printTopView(Node root)
{
// Map to store horizontal distance,
// height and node's data
SortedDictionary<int,
pair> m = new SortedDictionary<int,
pair>();
printTopViewUtil(root, 0, 0, m);
// Print the node's value stored by
// printTopViewUtil()
foreach(var it in m.Values)
{
Console.Write(it.data + " ");
}
}
// Driver code
public static void Main(string[] args)
{
Node root = newNode(1);
root.left = newNode(2);
root.right = newNode(3);
root.left.right = newNode(4);
root.left.right.right = newNode(5);
root.left.right.right.right = newNode(6);
Console.Write("Top View : ");
printTopView(root);
}
}
// This code is contributed by rutvik_56
Javascript
<script>
// JavaScript program to print Top View of Binary
// Tree using hashmap and recursion
// Node structure
class Node
{
constructor()
{
// Data of the node
this.data = 0;
// Reference to left node
this.left = null;
// Reference to right node
this.right = null;
}
};
class pair
{
constructor(data, height)
{
this.data = data;
this.height = height;
}
}
// Initialising node
function newNode(data)
{
var node = new Node();
node.data = data;
node.left = null;
node.right = null;
return node;
}
function printTopViewUtil(root, height, hd, m)
{
// Base Case
if (root == null)
return;
// If the node for particular horizontal distance
// is not present in the map, add it.
// For top view, we consider the first element
// at horizontal distance in level order traversal
if (!m.has(hd))
{
m.set(hd, new pair(root.data, height));
}
else
{
var p = m.get(hd);
if (p.height >= height)
{
m.set(hd, new pair(root.data, height));
}
}
// Recur for left and right subtree
printTopViewUtil(root.left, height + 1,
hd - 1, m);
printTopViewUtil(root.right, height + 1,
hd + 1, m);
}
function printTopView(root)
{
// Map to store horizontal distance,
// height and node's data
var m = new Map();
printTopViewUtil(root, 0, 0, m);
// Print the node's value stored by
// printTopViewUtil()
for(var it of [...m].sort())
{
document.write(it[1].data + " ");
}
}
// Driver code
var root = newNode(1);
root.left = newNode(2);
root.right = newNode(3);
root.left.right = newNode(4);
root.left.right.right = newNode(5);
root.left.right.right.right = newNode(6);
document.write("Top View : ");
printTopView(root);
</script>
Producción
Top View : 2 1 3 6
Complejidad temporal: O(n) donde n es el número de Nodes del árbol binario
Publicación traducida automáticamente
Artículo escrito por AmishGupta y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA