垂直打印树

Question

要了解同一垂直线是什么,我们需要先定义水平距离.如果两个节点具有相同的水平距离(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

Vertical-Line-2:只有一个节点2

Vertical-Line-3:有三个节点:1,5,6

Vertical-Line-4:只有一个节点3

Vertical-Line-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,满足我们从左到右的约束.

我已经读过某个地方,我们可以用更好的方式使用Doubly-Link List方法或者类似的东西.任何帮助人们？

Answer 1

您将必须访问每个节点一次才能获取其值 - 因此，正如您所说，除了进行完整遍历之外别无选择。在遍历时跟踪当前节点的水平距离很简单。

在遍历整个树之前，您无法知道要打印的第一个值，因此在打印任何内容之前，您必须将所有值收集到数据结构中。所以唯一的选择是使用什么数据结构。

您可以使用哪些结构取决于您的语言。

我会使用您语言中的 Java 等价物Map<HorizontalDistance,List<Node>>。

我没有看到任何特殊要求Map。List添加的需求必须便宜。如果它是一个链表，它至少应该维护一个指向其尾部的指针。不满足这个要求的主流列表实现不可能有很多。标准 JavaLinkedList就是这样做的。

因此，您按顺序遍历树，为每个节点调用此方法：

 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，将正 HD 映射到偶数索引，将负 HD 映射到奇数索引。

int index = hd < 0 ? ( -2 * hd - 1 ) : 2 * hd;

根据映射实现 - 和数组实现 - 以及在某些语言中，您是否足够提前了解数组的大小 - 这可能会更快且更节省内存。