要了解什么是垂直线，我们需要先定义水平距离。如果两个节点的水平距离(HD)相同，则它们在同一垂直线上。 HD的想法很简单。根的HD为0，将右边缘(连接到右子树的边缘)视为+1水平距离，而左边缘则视为-1水平距离。例如，在下面的树中，节点4的HD为-2，节点2的HD为-1，节点5和6的HD为0，节点7的HD为+2。
例子:
1
/ \
2 3
/ \ / \
4 5 6 7
这棵树有5条垂直线
Vertical-Line-1只有一个节点4
垂直线2:只有一个节点2
垂直线3:具有三个节点:1、5、6
垂直线4:只有一个节点3
垂直线5:只有一个节点7
现在换树
1
/ \
2 3
/ \ / \
4 5 6 7
/ \ / \
8 9 10 11
对于上面的树，我们应该从上到下，从水平到左，从左到右获取每个垂直级别的输出
8
4
2 9
1 5 6或1 6 5(因为6和5处于相同的垂直高度，并且具有相同的HD，所以顺序在其中无关紧要)
3 10
7
11
一种方法是简单地创建HD的多图，进行水平顺序遍历，然后将值插入相应的HD索引中。以水平顺序进行此操作将确保我们从上到下垂直访问。然后打印节点从最低HD到最高HD，满足了我们从左到右的约束。
我读过某个地方，我们可以使用“双向链接列表”方法或类似方法更好地做到这一点。有什么帮助的人吗？
最佳答案
您将不得不访问每个节点一次以获得其值(value)-因此，正如您所说的那样，除了进行完整遍历之外别无选择。遍历当前节点的“水平距离”很简单。
在遍历整棵树之前，您不知道要打印的第一个值，因此在打印任何内容之前，必须将所有值收集到数据结构中。因此，唯一的选择是使用哪种数据结构。
可用的结构取决于您的语言。
我将使用您的语言等效的Java Map<HorizontalDistance,List<Node>>。
我没有看到Map的任何特殊要求。 List需要便宜才能添加到其中。如果它是一个链表，则至少应保持一个指向其尾部的指针。没有很多不符合此要求的主流列表实现。标准的Java LinkedList可以。
因此，您按顺序遍历树，为每个节点调用此树:
private void addNode(Map<HorizontalDistance,List<Node>> data,
HorizontalDistance hd,
Node node)
{
List<Node> list = data.get(hd); // this is cheap
list.add(node); // this is cheap too
}
...然后通过遍历 map 键并打印每个列表将其打印出来。
我想，您可以用数组/列表替换Map，将正HD映射到偶数索引，将负HD映射到奇数索引。
int index = hd < 0 ? ( -2 * hd - 1 ) : 2 * hd;
根据映射实现和数组实现以及某些语言(取决于您是否知道足以预先确定数组大小)，这可能会更快，内存效率更高。
关于algorithm - 垂直打印树，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/20521098/