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 se pueden imprimir en cualquier orden.
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 una distancia horizontal de x menos 1, y la de un hijo derecho es la distancia horizontal de x más 1.
C++14
// C++ program to print top
// view of binary tree
#include <bits/stdc++.h>
using namespace std;
// Structure of binary tree
struct Node {
Node* left;
Node* right;
int hd;
int data;
};
// function to create a new node
Node* newNode(int key)
{
Node* node = new Node();
node->left = node->right = NULL;
node->data = key;
return node;
}
// function should print the topView of
// the binary tree
void topview(Node* root)
{
if (root == NULL)
return;
queue<Node*> q;
map<int, int> m;
int hd = 0;
root->hd = hd;
// push node and horizontal distance to queue
q.push(root);
cout << "The top view of the tree is : \n";
while (q.size()) {
hd = root->hd;
// count function returns 1 if the container
// contains an element whose key is equivalent
// to hd, or returns zero otherwise.
if (m.count(hd) == 0)
m[hd] = root->data;
if (root->left) {
root->left->hd = hd - 1;
q.push(root->left);
}
if (root->right) {
root->right->hd = hd + 1;
q.push(root->right);
}
q.pop();
root = q.front();
}
for (auto i = m.begin(); i != m.end(); i++) {
cout << i->second << " ";
}
}
// Driver code
int main()
{
/* Create following Binary Tree
1
/ \
2 3
\
4
\
5
\
6
*/
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 << "Following are nodes in top view of Binary "
"Tree\n";
topview(root);
return 0;
}
/* This code is contributed by Niteesh Kumar */
Java
// Java program to print top
// view of binary tree
import java.util.LinkedList;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Queue;
import java.util.TreeMap;
// class to create a node
class Node {
int data;
Node left, right;
public Node(int data)
{
this.data = data;
left = right = null;
}
}
// class of binary tree
class BinaryTree {
Node root;
public BinaryTree() { root = null; }
// function should print the topView of
// the binary tree
private void TopView(Node root)
{
class QueueObj {
Node node;
int hd;
QueueObj(Node node, int hd)
{
this.node = node;
this.hd = hd;
}
}
Queue<QueueObj> q = new LinkedList<QueueObj>();
Map<Integer, Node> topViewMap
= new TreeMap<Integer, Node>();
if (root == null) {
return;
}
else {
q.add(new QueueObj(root, 0));
}
System.out.println(
"The top view of the tree is : ");
// count function returns 1 if the container
// contains an element whose key is equivalent
// to hd, or returns zero otherwise.
while (!q.isEmpty()) {
QueueObj tmpNode = q.poll();
if (!topViewMap.containsKey(tmpNode.hd)) {
topViewMap.put(tmpNode.hd, tmpNode.node);
}
if (tmpNode.node.left != null) {
q.add(new QueueObj(tmpNode.node.left,
tmpNode.hd - 1));
}
if (tmpNode.node.right != null) {
q.add(new QueueObj(tmpNode.node.right,
tmpNode.hd + 1));
}
}
for (Map.Entry<Integer, Node> entry :
topViewMap.entrySet()) {
System.out.print(entry.getValue().data + " ");
}
}
// Driver Program to test above functions
public static void main(String[] args)
{
/* Create following Binary Tree
1
/ \
2 3
\
4
\
5
\
6
*/
BinaryTree tree = new BinaryTree();
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
tree.root.left.right = new Node(4);
tree.root.left.right.right = new Node(5);
tree.root.left.right.right.right = new Node(6);
System.out.println(
"Following are nodes in top view of Binary Tree");
tree.TopView(tree.root);
}
}
Python3
# Python3 program to print top
# view of binary tree
# Binary Tree Node
""" utility that allocates a newNode
with the given key """
class newNode:
# Construct to create a newNode
def __init__(self, key):
self.data = key
self.left = None
self.right = None
self.hd = 0
# function should print the topView
# of the binary tree
def topview(root):
if(root == None):
return
q = []
m = dict()
hd = 0
root.hd = hd
# push node and horizontal
# distance to queue
q.append(root)
while(len(q)):
root = q[0]
hd = root.hd
# count function returns 1 if the
# container contains an element
# whose key is equivalent to hd,
# or returns zero otherwise.
if hd not in m:
m[hd] = root.data
if(root.left):
root.left.hd = hd - 1
q.append(root.left)
if(root.right):
root.right.hd = hd + 1
q.append(root.right)
q.pop(0)
for i in sorted(m):
print(m[i], end="")
# Driver Code
if __name__ == '__main__':
""" Create following Binary Tree
1
/ \
2 3
\
4
\
5
\
6
"""
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("Following are nodes in top",
"view of Binary Tree")
topview(root)
# This code is contributed by
# Shubham Singh(SHUBHAMSINGH10)
C#
// C# program to print top
// view of binary tree
using System;
using System.Collections;
using System.Collections.Generic;
// Class to create a node
class Node {
public int data;
public Node left, right;
public Node(int data)
{
this.data = data;
left = right = null;
}
};
class QueueObj {
public Node node;
public int hd;
public QueueObj(Node node, int hd)
{
this.node = node;
this.hd = hd;
}
};
// Class of binary tree
class BinaryTree {
Node root;
public BinaryTree() { root = null; }
// function should print the topView of
// the binary tree
void TopView(Node root)
{
Queue q = new Queue();
SortedDictionary<int, Node> topViewMap
= new SortedDictionary<int, Node>();
if (root == null) {
return;
}
else {
q.Enqueue(new QueueObj(root, 0));
}
// count function returns 1 if the container
// contains an element whose key is equivalent
// to hd, or returns zero otherwise.
while (q.Count != 0) {
QueueObj tmpNode = (QueueObj)q.Dequeue();
if (!topViewMap.ContainsKey(tmpNode.hd)) {
topViewMap[tmpNode.hd] = tmpNode.node;
}
if (tmpNode.node.left != null) {
q.Enqueue(new QueueObj(tmpNode.node.left,
tmpNode.hd - 1));
}
if (tmpNode.node.right != null) {
q.Enqueue(new QueueObj(tmpNode.node.right,
tmpNode.hd + 1));
}
}
foreach(var entry in topViewMap.Values)
{
Console.Write(entry.data);
}
}
// Driver code
public static void Main(string[] args)
{
/* Create following Binary Tree
1
/ \
2 3
\
4
\
5
\
6*/
BinaryTree tree = new BinaryTree();
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
tree.root.left.right = new Node(4);
tree.root.left.right.right = new Node(5);
tree.root.left.right.right.right = new Node(6);
Console.WriteLine("Following are nodes "
+ "in top view of Binary Tree");
tree.TopView(tree.root);
}
}
// This code is contributed by rutvik_56
Javascript
<script>
// Javascript program to print top
// view of binary tree
class Node
{
constructor(data)
{
this.data=data;
this.left = this.right = null;
this.hd = 0;
}
}
// Driver Code
function topview(root)
{
if(root == null)
return;
let q = [];
let m = new Map();
let hd = 0;
root.hd = hd;
q.push(root);
while(q.length!=0)
{
root = q[0];
hd = root.hd;
if(!m.has(hd))
m.set(hd,root.data);
if(root.left)
{
root.left.hd = hd - 1;
q.push(root.left);
}
if(root.right)
{
root.right.hd = hd + 1;
q.push(root.right);
}
q.shift()
}
let arr = Array.from(m);
arr.sort(function(a,b){return a[0]-b[0];})
for (let [key, value] of arr.values())
{
document.write(value+" ");
}
}
let root = new Node(1)
root.left = new Node(2)
root.right = new Node(3)
root.left.right = new Node(4)
root.left.right.right = new Node(5)
root.left.right.right.right = new Node(6)
document.write("Following are nodes in top",
"view of Binary Tree<br>")
topview(root)
// This code is contributed by avanitrachhadiya2155
</script>
C++
#include <bits/stdc++.h>
using namespace std;
// Structure of binary tree
struct Node {
Node* left;
Node* right;
int data;
};
// function to create a new node
Node* newNode(int key)
{
Node* node = new Node();
node->left = node->right = NULL;
node->data = key;
return node;
}
// function to fill the map
void fillMap(Node* root, int d, int l,
map<int, pair<int, int> >& m)
{
if (root == NULL)
return;
if (m.count(d) == 0) {
m[d] = make_pair(root->data, l);
}
else if (m[d].second > l) {
m[d] = make_pair(root->data, l);
}
fillMap(root->left, d - 1, l + 1, m);
fillMap(root->right, d + 1, l + 1, m);
}
// function should print the topView of
// the binary tree
void topView(struct Node* root)
{
// map to store the pair of node value and its level
// with respect to the vertical distance from root.
map<int, pair<int, int> > m;
// fillmap(root,vectical_distance_from_root,level_of_node,map)
fillMap(root, 0, 0, m);
for (auto it = m.begin(); it != m.end(); it++) {
cout << it->second.first << " ";
}
}
// Driver Program to test above functions
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 << "Following are nodes in top view of Binary "
"Tree\n";
topView(root);
return 0;
}
/* This code is contributed by Akash Debnath */
Java
// Java program to print top
// view of binary tree
import java.util.*;
class GFG {
// Structure of binary tree
static class Node {
Node left;
Node right;
int data;
}
static class pair {
int first, second;
pair() {}
pair(int i, int j)
{
first = i;
second = j;
}
}
// map to store the pair of node value and
// its level with respect to the vertical
// distance from root.
static TreeMap<Integer, pair> m = new TreeMap<>();
// function to create a new node
static Node newNode(int key)
{
Node node = new Node();
node.left = node.right = null;
node.data = key;
return node;
}
// function to fill the map
static void fillMap(Node root, int d, int l)
{
if (root == null)
return;
if (m.get(d) == null) {
m.put(d, new pair(root.data, l));
}
else if (m.get(d).second > l) {
m.put(d, new pair(root.data, l));
}
fillMap(root.left, d - 1, l + 1);
fillMap(root.right, d + 1, l + 1);
}
// function should print the topView of
// the binary tree
static void topView(Node root)
{
fillMap(root, 0, 0);
for (Map.Entry<Integer, pair> entry :
m.entrySet()) {
System.out.print(entry.getValue().first + " ");
}
}
// 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.println("Following are nodes in"
+ " top view of Binary Tree");
topView(root);
}
}
// This code is contributed by Arnab Kundu
Python3
# Binary Tree Node
""" utility that allocates a newNode
with the given key """
class newNode:
# Construct to create a newNode
def __init__(self, key):
self.data = key
self.left = None
self.right = None
# function to fill the map
def fillMap(root, d, l, m):
if(root == None):
return
if d not in m:
m[d] = [root.data, l]
elif(m[d][1] > l):
m[d] = [root.data, l]
fillMap(root.left, d - 1, l + 1, m)
fillMap(root.right, d + 1, l + 1, m)
# function should print the topView of
# the binary tree
def topView(root):
# map to store the pair of node value and its level
# with respect to the vertical distance from root.
m = {}
fillMap(root, 0, 0, m)
for it in sorted(m.keys()):
print(m[it][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("Following are nodes in top view of Binary Tree")
topView(root)
# This code is contributed by SHUBHAMSINGH10
C#
// C# program to print top
// view of binary tree
using System;
using System.Collections;
using System.Collections.Generic;
class GFG {
// Structure of binary tree
class Node {
public Node left;
public Node right;
public int data;
}
class pair {
public int first, second;
public pair(int i, int j)
{
first = i;
second = j;
}
}
// map to store the pair of node value and
// its level with respect to the vertical
// distance from root.
static SortedDictionary<int, pair> m
= new SortedDictionary<int, pair>();
// function to create a new node
static Node newNode(int key)
{
Node node = new Node();
node.left = node.right = null;
node.data = key;
return node;
}
// function to fill the map
static void fillMap(Node root, int d, int l)
{
if (root == null)
return;
if (!m.ContainsKey(d)) {
m[d] = new pair(root.data, l);
}
else if (m[d].second > l) {
m[d] = new pair(root.data, l);
}
fillMap(root.left, d - 1, l + 1);
fillMap(root.right, d + 1, l + 1);
}
// function should print the topView of
// the binary tree
static void topView(Node root)
{
fillMap(root, 0, 0);
foreach(pair entry in m.Values)
{
Console.Write(entry.first + " ");
}
}
// 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.WriteLine("Following are nodes in"
+ " top view of Binary Tree");
topView(root);
}
}
// This code is contributed by pratham76
Javascript
<script>
// Javascript program to print top
// view of binary tree
// Structure of binary tree
class Node
{
constructor()
{
this.data = 0;
this.left = this.right = null;
}
}
class pair
{
constructor(i, j)
{
this.first = i;
this.second = j;
}
}
// map to store the pair of node value and
// its level with respect to the vertical
// distance from root.
let m = new Map();
// function to create a new node
function newNode(key)
{
let node = new Node();
node.left = node.right = null;
node.data = key;
return node;
}
// function to fill the map
function fillMap(root, d, l)
{
if (root == null)
return;
if (m.get(d) == null) {
m.set(d, new pair(root.data, l));
}
else if (m.get(d).second > l) {
m.set(d, new pair(root.data, l));
}
fillMap(root.left, d - 1, l + 1);
fillMap(root.right, d + 1, l + 1);
}
// function should print the topView of
// the binary tree
function topView(root)
{
fillMap(root, 0, 0);
let arr=Array.from(m.keys());
arr.sort(function(a,b){return a-b;});
for (let key of arr.values()) {
document.write(m.get(key).first + " ");
}
}
// Driver Code
let 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("Following are nodes in"
+ " top view of Binary Tree<br>");
topView(root);
// This code is contributed by rag2127
</script>
C++14
// C++ Program to print Top View of a binary Tree
#include <iostream>
#include <queue>
#include <stack>
using namespace std;
// class for Tree node
class Node {
public:
Node *left, *right;
int data;
Node() { left = right = 0; }
Node(int data)
{
left = right = 0;
this->data = data;
}
};
/*
1
/ \
2 3
\
4
\
5
\
6
Top view of the above binary tree is
2 1 3 6
*/
// class for Tree
class Tree {
public:
Node* root;
Tree() { root = 0; }
void topView()
{
// queue for holding nodes and their horizontal
// distance from the root node
queue<pair<Node*, int> > q;
// pushing root node with distance 0
q.push(make_pair(root, 0));
// hd is current node's horizontal distance from
// root node l is current left min horizontal
// distance (or max in magnitude) so far from the
// root node r is current right max horizontal
// distance so far from the root node
int hd = 0, l = 0, r = 0;
// stack is for holding left node's data because
// they will appear in reverse order that is why
// using stack
stack<int> left;
// vector is for holding right node's data
vector<int> right;
Node* node;
while (q.size()) {
node = q.front().first;
hd = q.front().second;
if (hd < l) {
left.push(node->data);
l = hd;
}
else if (hd > r) {
right.push_back(node->data);
r = hd;
}
if (node->left) {
q.push(make_pair(node->left, hd - 1));
}
if (node->right) {
q.push(make_pair(node->right, hd + 1));
}
q.pop();
}
// printing the left node's data in reverse order
while (left.size()) {
cout << left.top() << " ";
left.pop();
}
// then printing the root node's data
cout << root->data << " ";
// finally printing the right node's data
for (auto x : right) {
cout << x << " ";
}
}
};
// Driver code
int main()
{
// Tree object
Tree t;
t.root = new Node(1);
t.root->left = new Node(2);
t.root->right = new Node(3);
t.root->left->right = new Node(4);
t.root->left->right->right = new Node(5);
t.root->left->right->right->right = new Node(6);
t.topView();
cout << endl;
return 0;
}
Python3
# Python Program to print Top View of a binary Tree # Class of tree node class Node: def __init__(self, data): self.left = None self.right = None self.data = data ''' 1 / \ 2 3 \ 4 \ 5 \ 6 Top view of the above binary tree is 2 1 3 6 ''' # class for Tree class Tree: def __init__(self): self.root = None def topView(self): # queue for holding nodes and their horizontal # distance from the root node q = [] # pushing root node with distance 0 q.append((self.root, 0)) # hd is current node's horizontal distance from # root node l is current left min horizontal # distance (or max in magnitude) so far from the # root node r is current right max horizontal # distance so far from the root node hd = 0 l = 0 r = 0 # stack is for holding left node's data because # they will appear in reverse order that is why # using stack left = [] # list is for holding right node's data right = [] while len(q) > 0: node, hd = q[0] if hd < l: left.append(node.data) l = hd elif hd > r: right.append(node.data) r = hd if node.left != None: q.append((node.left, hd-1)) if node.right != None: q.append((node.right, hd+1)) q.pop(0) # printing the left node's data in reverse order while len(left) > 0: x = left.pop() print(x, end=" ") # then printing the root node's data print(self.root.data, end=" ") # finally printing the right node's data for x in right: print(x, end=" ") # Driver code if __name__ == '__main__': # Tree object t = Tree() t.root = Node(1) t.root.left = Node(2) t.root.right = Node(3) t.root.left.right = Node(4) t.root.left.right.right = Node(5) t.root.left.right.right.right = Node(6) t.topView() print() # This code is contributed by Tapesh(tapeshdua420)
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