Java 中二叉树的顶视图

2025年9月4日 | 阅读5分钟

在本节中，我们将学习 Java 二叉树的顶部视图 以及实现它的不同方法。在二叉树的顶部视图中，我们只打印从顶部查看二叉树时可见的节点。

例如，考虑以下二叉树。

上述二叉树的顶部视图是

对于下面的二叉树

上述二叉树的顶部视图是

注意：在二叉树的顶部视图中，节点显示的输出顺序并不重要。唯一重要的是，所有从二叉树顶部可见的节点都应包含在输出中。

方法 1：使用队列

在此方法中，我们需要通过将根节点作为参考来对具有相同水平距离的节点进行分组。我们使用队列对树进行层次遍历，以便先访问顶部节点，然后再访问下面的节点。使用哈希技术来识别给定的水平距离是否已查看。

实施

让我们通过水平距离方法来实现二叉树的顶部视图。

文件名： TopViewExample.java

// important import statements
import java.util.LinkedList;
import java.util.Map;
import java.util.TreeMap;
import java.util.Queue;
import java.util.Map.Entry;
// a node of a binary tree
class BinaryTreeNode 
{
// for keeping the value of a node
int v;
// l and r represents the  
// left child and the right child of a node
BinaryTreeNode l, r;
// constructor of the class BinaryTreeNode
// the construct and initializes the class fields
public BinaryTreeNode(int i)
{
v = i;
r = null;
l = null;
}
}
public class TopViewExample 
{
BinaryTreeNode rt;
// constructor of the class
public TopViewExample() { rt = null; }
// method that displays the top view of the binary tree
private void TopView(BinaryTreeNode root)
{
class QueObj 
{
BinaryTreeNode node;
int horDis;
// constructor of the class QueObj
QueObj(BinaryTreeNode node, int horDis)
{
this.node = node;
this.horDis = horDis;
}
}
Queue<QueObj> que = new LinkedList<QueObj>();
Map<Integer, BinaryTreeNode> mp = new TreeMap<Integer, BinaryTreeNode>();
if (root == null) 
{
return;
}
else 
{
que.add(new QueObj(root, 0));
}
while (!que.isEmpty()) 
{
QueObj tempNode = que.poll();
if (!mp.containsKey(tempNode.horDis)) 
{
mp.put(tempNode.horDis, tempNode.node);
}
if (tempNode.node.l != null) 
{
// -1 for the left node
que.add(new QueObj(tempNode.node.l, tempNode.horDis - 1));
}
if (tempNode.node.r != null) 
{
// +1 for the right node
que.add(new QueObj(tempNode.node.r, tempNode.horDis + 1));
}
}
// loop for printing the values of the node that are visible from the top view
for (Entry<Integer, BinaryTreeNode> entry : mp.entrySet()) 
{
System.out.print(entry.getValue().v + " ");
}
}
// main method
public static void main(String[] argvs)
{
// creating an object of the class TopViewExample
TopViewExample tv = new TopViewExample();
// root node of the binary tree
tv.rt = new BinaryTreeNode(3);
// other nodes of the binary tree
tv.rt.l = new BinaryTreeNode(4);
tv.rt.r = new BinaryTreeNode(2);
tv.rt.l.l = new BinaryTreeNode(7);
tv.rt.l.r = new BinaryTreeNode(6);
tv.rt.r.l = new BinaryTreeNode(5);
tv.rt.r.r = new BinaryTreeNode(1);
System.out.println("The following are the nodes present in the top view of the Binary Tree");
tv.TopView(tv.rt);
}
}

输出

The following are the nodes present in the top view of the Binary Tree
7 4 3 2 1

方法 2：使用两个变量

在前一种方法中，我们讨论了使用队列查看树的顶部。在此方法中，我们将使用两个变量而不是队列。一个变量用于识别节点的深度（将根节点作为参考），另一个用于查找与根节点的垂直距离。对于索引，我们使用垂直距离。如果再次访问具有相同垂直距离的任何其他节点，则必须检查新节点的深度是高于还是低于当前节点。当新节点的深度较低时，我们进行替换。

实施

让我们使用两个变量来实现二叉树的顶部视图。

文件名： TopViewExample1.java

// important import statements
import java.util.Map;
import java.util.Queue;
import java.util.TreeMap;
import java.util.Map.Entry;
import java.util.LinkedList;

class PairSet
{
int first;
int second;
PairSet() 
{

}
PairSet(int m, int n)
{
first = m;
second = n;
}
}
// a node of a binary tree
class BinaryTreeNode 
{
// for keeping the value of a node
int v;
// l and r represents the  
// left child and the right child of a node
BinaryTreeNode l, r;
// constructor of the class BinaryTreeNode
// the construct and initializes the class fields
public BinaryTreeNode(int i)
{
v = i;
r = null;
l = null;
}
}
public class TopViewExample1 
{
BinaryTreeNode rt;
// constructor of the class
public TopViewExample1() { rt = null; }
// a map to keep the node value pair and its level
// with respect to the vertical distance from the root.
public TreeMap<Integer, PairSet> mp = new TreeMap<>();
// method for filling the map
public void fillMap(BinaryTreeNode rt, int d, int i)
{
if (rt == null)
{
return;
}
if (mp.get(d) == null) 
{
mp.put(d, new PairSet(rt.v, i));
}
else if (mp.get(d).second > i) 
{
mp.put(d, new PairSet(rt.v, i));
}
fillMap(rt.l, d - 1, i + 1);
fillMap(rt.r, d + 1, i + 1);
}
// method that prints the topView of the binary tree
public void topView(BinaryTreeNode rt)
{
fillMap(rt, 0, 0);
for (Map.Entry<Integer, PairSet> en : mp.entrySet()) 
{
System.out.print(en.getValue().first + " ");
}
}
// main method
public static void main(String argvs[])
{
// creating an object of the class TopViewExample1
TopViewExample1 tv = new TopViewExample1();
// root node of the binary tree
tv.rt = new BinaryTreeNode(3);
// other nodes of the binary tree
tv.rt.l = new BinaryTreeNode(4);
tv.rt.r = new BinaryTreeNode(2);
tv.rt.l.l = new BinaryTreeNode(7);
tv.rt.l.r = new BinaryTreeNode(6);
tv.rt.r.l = new BinaryTreeNode(5);
tv.rt.r.r = new BinaryTreeNode(1);
System.out.println("The following are the nodes present in the top view of the Binary Tree");
tv.topView(tv.rt);
}

输出

The following are the nodes present in the top view of the Binary Tree
7 4 3 2 1

下一主题Java 适配器类

Java 中二叉树的顶视图

注意：在二叉树的顶部视图中，节点显示的输出顺序并不重要。唯一重要的是，所有从二叉树顶部可见的节点都应包含在输出中。

方法 1：使用队列

实施

方法 2：使用两个变量

实施

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Java Conversion

Java Misc

Java 中二叉树的顶视图

注意：在二叉树的顶部视图中，节点显示的输出顺序并不重要。唯一重要的是，所有从二叉树顶部可见的节点都应包含在输出中。

方法 1：使用队列

实施

方法 2：使用两个变量

实施

相关帖子

How to Improve Coding Skills in Java

Java int keyword

Travelling Salesman Problem

How to Sort ArrayList in Java

Java Program to Count Number of Hops

Java 中每个查询的最大 XOR 值

Java 中不使用循环打印 1 到 100

Java 中的多重继承

Java 中 & 运算符是什么

ORE Number Java

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器