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找的,其实也不难理解。
2 年多之前 回复
XwinterwinterwinterX
XwinterwinterwinterX 关于树的垂直结构
2 年多之前 回复
XwinterwinterwinterX
XwinterwinterwinterX 关于树的垂直结构
2 年多之前 回复
XwinterwinterwinterX
XwinterwinterwinterX 请问哪里有相关资料
2 年多之前 回复
XwinterwinterwinterX
XwinterwinterwinterX   2016.04.09 22:15
qq_18332445
qq_18332445   2016.04.11 14:52

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

Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
数据结构 非线性结构 树 介绍及存储方法
所谓树, 其实跟链表有类似的地方,  就是都是由节点和指针构成的数据结构.            在链表中,  每1个节点(尾节点除外)只有1个指针指向下1个节点. 所以链表各个节点可以由一条线链接起来, 就是一种线性结构.            而在树中, 每1个节点可以有1个或多个指针指向下1个节点,  如下图:               所以树是一种非线性结构, 对于这种
树 的结构
1、树的相关术语    节点的度:一个节点 含有的子树 的个数 称为该节点的度; 叶节点或终端节点:度为0的节点称为叶节点; (一般树图 的最下面的节点)非终端节点或分支节点:度不为0的节点; 双亲节点或父节点:若一个节点含有子节点,则这个节点称为其子节点的父节点; 孩子节点或子节点:一个节点含有的子树的根节点称为该节点的子节点; 兄弟节点:具有相同父节点的节点互称为兄弟节点; 树的度:一棵树中,...
垂直应用架构
解决垂直应用架构和一般平行架构之间相关区分,同时针对水平架构 及其流动计算架构进行简单分析
java - 菜单树形结构
1、结构一限制:(数据库添加数据的时候,进行限制最好;id 与 pid 为 int)  不要出现类似下面的情况,即 B = C && D > B,  换句话说,先 sort(pid) 再 sort(id) 之后,某一项的 pid 对应的 id应该在该项前面,即 A = D && B < DmenuList.add(new Menu(112, 116, "...
父子结构(树形结构)下拉框
项目中可能经常要做具有父子结构的下拉框,像这样: 实战时,思维一直是用js插件来实现,今天重新学习HTML5时,发现可以直接用select和option实现,具体代码如下:<select> <optgroup label="人力资源部"> <option>小花</option> <option>小梅</option> </optgroup>
【2.1】顺序表
第二章序言上一章的两节介绍了常用的算法,这些算法用来处理零散的数据。实际上我们有时候处理的数据之间是存在一种或者多种特定的关系时,我们称这些关系为结构。通常数据之间有三种基本的机构。(1)线性结构:数据元素之间为一对一的关系。(2)树形结构:数据元素之间为一对多的关系。(3)网状结构:数据元素之间为多对多的关系。什么是线性表?线性表示最基本、最简单、也是最常用的一种数据结构。它是一个含有n个节点的...
Java数据结构-树及树的存储结构
树的定义:n(n>=0)个节点的有限集。 n=0时称为空树。 n!=0时为非空树,有且仅有一个特定的节点——根;n>1时,其它节点可以分为m(m>0)个互不相交的有限集T1~Tm,其中每一个集合本身又是一棵树,并且称为根的子树。 树的一些基本术语: 树的结点:由一个数据元素和若干个指向其子树的分支组成。 结点的度:结点所拥有的子树的个数(即分支数)称为该结点的度。 叶子结点:度为0的结点称为叶子结点
js横向二级导航菜单
网页特效 js横向二级导航菜单 站长特效网 body { text-align: center; background: #FFF; font: 12px Tahoma, sans-serif; color: #000; } img { border: 0; } ul,li { list-style:
B+树索引结构
1.索引结构          1.1 B+树索引结构         从物理上说,索引通常可以分为:分区和非分区索引、常规B树索引、位图(bitmap)索引、翻转 (reverse)索引等。其中,B树索引属于最常见的索引    B树索引是一个典型的树结构,其包含的组件主要是:         叶子节点(Leaf node):包含条目直接指向表里的数据行。         分支
B*树索引——Oracle的默认索引结构
1、B*树索引 1.1 概述        B*树索引是Oracle默认的索引结构。我们使用CREATE INDEX语句创建索引时,创建的就是B*树索引。B*树索引的结构一个二 叉树,由根节点(root node)、分支部分(branch node)和叶子节点(leaf node)构成。       提示:B*树的B是单词Balanced的缩写,平衡之意。      ● 根节点:包含指向