2 xwinterwinterwinterx XwinterwinterwinterX 于 2016.04.09 22:15 提问

请问树的垂直结构是怎样的?

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


The output of print this tree vertically will be:
4
2
1 5 6
3 8
7
9 

看不懂这个例子

3个回答

caozhy
caozhy   Ds   Rxr 2016.04.09 22:34
已采纳
 http://stackoverflow.com/questions/20521098/print-a-tree-vertically

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

关键点是理解HD,垂直距离。

          1(0)
        /    \
       2 (-1)   3(1)
      / \    / \
     4(-2)5(0) 6(0)   7(2)
             \   \
              8(1)   9(3)

然后排序输出
-2 4
-1 2
0 1 5 6
1 3 8
2 7
3 0
caozhy
caozhy 回复XwinterwinterwinterX: 这不是一个很常见的概念,不过我的链接是google找的,其实也不难理解。
一年多之前 回复
XwinterwinterwinterX
XwinterwinterwinterX 关于树的垂直结构
一年多之前 回复
XwinterwinterwinterX
XwinterwinterwinterX 关于树的垂直结构
一年多之前 回复
XwinterwinterwinterX
XwinterwinterwinterX 请问哪里有相关资料
一年多之前 回复
XwinterwinterwinterX
XwinterwinterwinterX   2016.04.09 22:15
qq_18332445
qq_18332445   2016.04.11 14:52

你这是典型的中序遍历(LDR),中序遍历首先遍历左子树,然后访问根结点,最后遍历右子树。在遍历左、右子树时,仍然先遍历左子树,再访问根结点,最后遍历右子树。

Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!