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

查看:58
本文介绍了垂直打印一棵树的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

要了解什么是相同的垂直线,我们需要先定义水平距离.如果两个节点具有相同的水平距离 (HD),则它们在同一条垂直线上.高清的想法很简单.根的HD为0,右边缘(连接到右子树的边缘)被认为是+1水平距离,左边缘被认为是-1水平距离.例如,在下面的树中,节点 4 的 HD 为 -2,节点 2 的 HD 为 -1,5 和 6 的 HD 为 0,节点 7 的 HD 为 +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 条垂直线

Vertical-Line-1 只有一个节点 4

Vertical-Line-1 has only one node 4

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

Vertical-Line-2: has only one node 2

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

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

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

Vertical-Line-4: has only one node 3

Vertical-Line-5:只有一个节点 7

Vertical-Line-5: has only one node 7

现在是树

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

对于上面的树,我们应该得到从上到下,从左到右水平的每个垂直级别的输出

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 处于相同的垂直水平,并且相同的高清,它们的顺序无关紧要)

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

一种方法是简单地创建一个 HD 的 multimap,并进行层序遍历,并将值推送到相应的 HD 索引中.以层序方式执行此操作将保证我们从上到下垂直访问.然后打印节点从最低 HD 到最高 HD,满足我们从左到右的约束.

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.

我在某处读到过,我们可以使用双向链接列表方法或类似方法以更好的方式完成此操作.有任何帮助吗?

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 Map>.

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

我没有看到对 Map 的任何特殊要求.List 需要廉价添加.如果它是一个链表,它至少应该维护一个指向其尾部的指针.不符合这个要求的主流列表实现不可能有很多.标准的 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.

我想,您可以用数组/列表替换 Map,将正 HD 映射到偶数索引,将负 HD 映射到奇数索引.

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屋!

查看全文
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆