打印树垂直 [英] Print a Tree Vertically

问题描述

要了解什么是同一垂直线上，我们需要先定义的水平距离。如果两个节点具有相同的水平距离（HD），那么它们就同一垂直线上。高清的想法很简单。 HD为根是0，一个右边缘（边连接到右子树）被认为是1的水平距离和一个左边缘被认为是-1水平距离。例如，在下面的树，高清对于节点4是在-2，高清为节点2为-1，高清为5和6是0和HD为节点7是2

To understand what's same vertical line, we need to define horizontal distances first. If two nodes have the same Horizontal Distance (HD), then they are on same vertical line. The idea of HD is simple. HD for root is 0, a right edge (edge connecting to right subtree) is considered as +1 horizontal distance and a left edge is considered as -1 horizontal distance. For example, in the below tree, HD for Node 4 is at -2, HD for Node 2 is -1, HD for 5 and 6 is 0 and HD for node 7 is +2.

例如：

      1
    /   \

   2     3

  / \   / \
  4  5  6  7

该树有5个垂直线

The tree has 5 vertical lines

垂直线-1只有一个节点4

Vertical-Line-1 has only one node 4

垂直线-2：只有一个节点2

Vertical-Line-2: has only one node 2

垂直线，3：有三个节点：1,5,6

Vertical-Line-3: has three nodes: 1,5,6

垂直线，4：只有一个节点3

Vertical-Line-4: has only one node 3

垂直线-5：只有一个节点7

Vertical-Line-5: has only one node 7

现在的树

        1            
      /    \
    2        3       
   / \      /  \
  4   5    6    7    
 / \           / \
8   9        10   11

有关上述树，我们应该得到的输出从上到下每个垂直的水平，并从左到右horixontally

For the above tree , we should get the output each vertical level from top to bottom, and left to right horixontally

8

4

2 9

1 5 6 1 6 5（自6和5是在同一垂直水平，同样的HD，以便在其中并不重要）

1 5 6 or 1 6 5 ( since 6 and 5 are at same vertical level, and same HD, order doesn't matter in them)

3 10

7

11

要做到这一点是通过简单地创建高清的的多重映射，并办出水平序遍历，并推动值代入相应的高清指数.Doing这级别的顺序方式将保证我们从上参观底部垂直的一种方式。然后打印节点形成最低的高清到高清最高，履行我们从左到右约束。

One way to do it is by simply creating a multimap of HD's , and do a level order traversal, and push the values into corresponding HD index .Doing this in level order way will guarantee that we visit from top to bottom vertically .Then print the nodes form lowest HD to highest HD, fulfilling us left to right constraint.

我读的地方，我们就可以使用双向链接列表的方式或东西similar.Any帮助人们更好的办法做到这一点？

I've read somewhere that we can do it in a better way using Doubly-Link List approach or something similar.Any help people ?

推荐答案

你将要访问的每个节点，一旦得到它的价值 - 所以没有办法，只好让一个完整的遍历，就像你说。这是微不足道的跟踪当前节点的水平距离为你穿越。

You're going to have to visit each node once to get its value - so there's no alternative but to make a full traversal, as you've said. It's trivial to keep track of the current node's Horizontal Distance as you traverse.

您无法知道的第一个值来打印，直到你遍历整棵树，所以你要在打印任何东西之前，收集所有的值转换为数据结构。所以，唯一的选择是使用什么样的数据结构。

You can't know the first value to print until you've traversed the whole tree, so you're going to have to collect all the values into a data structure before printing anything. So the only choice is what data structure to use.

什么结构都可以给你要看你的语言。

What structures are available to you depends on your language.

我会用你的语言的相应的Java 地图＆LT的; Horizo​​ntalDistance，名单，其中，节点GT;＆GT;

I would use your language's equivalent of Java Map<HorizontalDistance,List<Node>>.

我不明白的地图的任何特殊要求。该列表需要贪便宜增加。如果它是一个链表，它应该保持一个指向它的尾巴，至少。不能有不符合这个要求很多主流列表实现。该标准的Java 的LinkedList 一样。

I don't see any special requirements for the Map. The List needs to be cheap to add to. If it's a linked list, it should maintain a pointer to its tail, at least. There can't be many mainstream list implementations that don't meet this requirement. The standard Java LinkedList does.

所以，你遍历为了树，调用此为每个节点：

So, you're traversing the tree in order, calling this for each node:

 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
 }

...然后打印出来，通过映射按键迭代，每次打印清单。

... then printing it out by iterating through the map keys, printing each list.

您可以，我想，有一个数组/列表更换地图，映射你的积极日立数据系统，甚至指数和你的底片奇怪的。

You could, I suppose, replace the Map with an array/list, mapping your positive HDs to even indices and your negatives to odd ones.

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

根据地图实现 - 与数组实现 - 在一些语言中，你是否知道足够的大小提前阵列 - 这可能是速度更快，内存更有效的

Depending on the map implementation - and the array implementation - and in some languages, whether you know enough to size the array in advance - this might be faster and more memory-efficient.

这篇关于打印树垂直的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！