一个信息可视化Demo的设计（三）：算法设计
作者：愤怒的小狐狸 撰写日期：2012-02-22 ~ 2011-02-28
博客链接：
此为系列博文，前续请看：
第一部分：
第二部分：
一、背景和废话若干
信息可视化一个简单概括性的说法即是将信息、数据、资源等能够通过可视化的手段和方式，直观地呈现给用户，帮助用户梳理其中的知识以及内在关联，必要时提供所见即所得（WYSIWYG）的交互方式。从一个产品设计的角度来考虑的话，好的信息可视化工具必然给用户带来一种自然而然的交互体验，甚至是用户根本没意识到某种交互行为的存在，也即是用户潜意识里面一直在念叨：交互行为不就应该是这样的吗？
作为一个信息可视化的Demo，最终前端的落脚点还是要依托于某种图形化的展示技术来实现。我们的方案是基于Silverlight，当然并不是说我们不可以选用其他的前端技术。正如之前所述，微软一般还是会用自己公司的产品，即便是和我搭档的小伙会用Flex，而我俩都不会Silverlight。插一句题外话，在来实习之前，我还是认为微软的大型在线服务系统如Bing会采用UNIX环境部署，后来得知是基于Win Server，这使我大吃一惊，看来Win Server性能应该还是不错的，虽然我没用过，见笑了各位~
Silverlight提供了交互能力强大且丰富的可视化控件，因此我们有了图形显示、交互的落地技术。然而，同时又有新问题摆在了我们面前，即如何合理地布局一棵树，使得树形结构的渲染简洁而又不失优雅。其实，早在我们刚刚接触这个项目的时候，我还对此不屑一顾，我认为这个项目真是太简单了，说白了不就是把描述Tree的文件载入，把Tree的结构还原，再用Silverlight显示出来嘛。后来，真正做的时候却是问题接踵而来，就比如现在的Tree的布局问题，猛的一看觉得简单的不得了，再仔细一想发现很难一下解决，再到后来看了几个Li给我的老外做的Demo之后，哥彻底清楚过来，如果要想实现的特别NB，还是很难驾驭的。其中，简单一点的Space Tree的Demo链接：，还有一些比较绚的渲染效果如FishEye Tree、Circular Treemap等，链接：。看完这些Demo你会觉得专业和非专业还是有蛮大差别，是我肯定是想不出这么多、这么绚的效果，而且交互作为黑NB~
对自己有了重新的定位后，我们开始选择最简单的原型设计，即输入一个树，把它完整地在页面上显示出来，使得节点与节点之间的排列布局井然有序简洁优雅而又层次结构关联逻辑清晰可见（- -|||）。那，这应该如何做到呢？说到底还是算法设计问题。
不搞不知道，一搞吓一跳，其实这个问题在几十年前，也就是70年代时候就有NB人物已经解决过了，而且解决的很好。其中比较著名的有Knuth提出的“Optimum binary search trees”，学计算机都知道这人是谁，不用多说。后来，找到一篇论文“Tidy Drawings of Trees”里面介绍了几种方法，感觉比较简单且易于实现，在此做个总结。
二、朴素的树形结构显示算法
首先来看一个朴素的树形结构显示算法，对于任一节点而言，至多存在一个前驱父节点，而根节点root的父节点为NULL，同等高度的节点应处于同一水平线层次。因此，一种朴素方法即是按照节点的高度进行平行绘制，高度可以表征节点的Y轴坐标，计算和获取每个节点高度是首要解决的问题，但在论文中该算法中先假设已经得到了这个值。
算法的基本思路在于将具有相同高度节点的Y轴坐标设置为一样的，即设为高度值，使它们处于同一水平线，剩下的只需要调整它们的X坐标，使得下一个节点的X坐标与上一节点之间存在一定的距离即可，思想是很简单的。
输入：定义良好的树形结构的root、最大高度max_height。
输出：每个节点的坐标(x, y)，假设每个节点的高度是已经知道。
算法伪码描述：
//节点数据结构
type node
data; //节点数据
father: branch; //父节点
children_num: integer; //子节点数目
children: array[1..children_num] of branch; //子节点数组
height: integer; //节点高度
x, y: integer; //X、Y轴坐标
status: 0..children_num; //处理子节点数目
end;
//变量定义
var next_x: array[0..max_height] of integer;
current: branch;
i: integer;
begin
//初始化每个高度的X轴首位置为1
for i = 0 to max_height do
next_x[i] = 1;
end for;
//初始化root处理的子节点数目为0
root.status = 0;
current = root;
//结束条件为root的父节点为NULL
while current != NULL do
//首先处理current节点本身
if current.status == 0 then
//X坐标记录在next_x中，用于使同一层次两个节点之间保持间隔
current.x = next_x[current.height];
//Y坐标直接使用节点高度
current.y = 2 * current.height + 1;
//同一层两个节点之间间隔为2
next_x[current.height] = next_x[current.height] + 2;
//初始化所有子节点
for i = 1 to current.children_num do
current.children[i].status = 0;
end for;
//设置current节点已经被处理过
current.status = 1;
//子节点尚未完全处理完
else if 1 <= current.status && current.status <= current.children_num then
current.status = current.status + 1;
current = current.children[current.status - 1];
//子节点处理则回溯到父节点
else current = current.father;
end if;
end while;
end;
其实，我并不明白为什么要假设节点的高度是已知的，而事实上我们并不需要提前知道节点的高度，而是可以在计算节点高度的过程中计算节点的（X、Y）坐标值，这一点借助于队列，利用层次遍历的思想很容易就实现了，子节点高度=父节点高度+1嘛，那样给出伪码比论文中给出的还要简单些，其伪码描述如下所示。
输入：定义良好的树形结构的root。
输出：每个节点的坐标(x, y)。
算法伪码描述：
//节点数据结构
type node
data; //节点数据
father: branch; //父节点
children_num: integer; //子节点数目
children: array[1..children_num] of branch; //子节点数组
height: integer; //节点高度
x, y: integer; //X、Y轴坐标
end;
//变量定义
var next_x: array[0..N] of integer;
current: branch;
i: integer;
N: integer;
q: Queue;
begin
//初始化每个高度的X轴首位置为1，N通常取一个较大的数，必须大于树形结构最大高度
for i = 0 to N do
next_x[i] = 1;
end for;
//初始化root的高度为0
root.height = 0;
//将root装入队列
q.push(root);
//如果队列不为空s
while !q.empty() do
//从队列中弹出节点
current = q.pop();
//设置弹出节点的X、Y轴坐标
current.x = next_x[current.height];
current.y = 2 * current.height + 1;
//同一层两个节点之间间隔为2
next_x[current.height] = next_x[current.height] + 2;
//对弹出节点的所有子节点进行处理
for i = 0 to children_num do
//子节点的高度为父节点+1
current.children[i].height = current.height + 1;
//将子节点装入队列
q.push(current.children[i]);
end for;
end while;
end;
按照朴素的树形结构显示算法得绘制的图形如下所示，当然，整体而言还算是比较整齐与简洁，但存在的问题是父子继承关系的连线不太美观与优雅，特别是当某一层次上节点过多时，布局看上去总是不那么Happy，这也是这种方法使用的局限所在。
三、二叉树显示算法
二叉树是应用非常广泛的特殊树形结构，其严格意义上并不属于“树”，因为其有明确的左右孩子节点之分，而对于树而言其所有的孩子节点均是平等的。Knuth利用中序遍历的思想，设计了一种二叉树图形渲染算法，基本思路：中序遍历，从而依次确定左孩子、父节点和右孩子节点的坐标。
输入：定义良好的树形结构的root。
输出：每个节点的坐标(x, y)，假设每个节点的高度是已经知道。
算法伪码描述：
//节点数据结构
type node
data; //节点数据
father: branch; //父节点
left_son, right_son: branch; //左右孩子节点
height: integer; //节点高度
x, y: integer; //X、Y轴坐标
status: (first_visit, left_visit, right_visit); //遍历的访问模式
end;
//变量定义
var current: branch;
next: integer;
begin
//初始化节点的X坐标
next = 1;
current = root;
current = first_visit;
//存在未处理的二叉树节点
while current != NULL do
//对current的访问情况进行分析
switch current.status
//初次访问模式
case first_visit:
//设定下次访问模式为左访问
current.status = left_visit;
//中序遍历
if current.left_son != NULL then
current = current.left_son;
current.status = first_visit;
end if;
break;
//走到当前子树的最左端，即可确定该节点的X坐标
case left_visit:
current.x = next;
current.y = 2 * current.height + 1;
//计算下一个节点X坐标
++next;
//左边为空，设置右访问模式
current.status = right_visit;
if current.right_son != NULL then
current = current.right_son;
current.status = first_visit;
end if;
break;
//表明右孩子为空，则回溯到父节点
case right_visit:
current = current.father;
break;
end case;
end switch;
end while;
end;
Kunth大神的这个算法很是简洁，只需一次中序遍历即确定了所有节点的X坐标，他是使用了一种非递归的方式书写了算法，当然递归的算法描述更为简单：
输入：定义良好的树形结构的root。
输出：每个节点的坐标(x, y)，假设每个节点的高度是已经知道。
算法伪码描述：
//变量定义
var current: branch;
next: integer;
//定义中序遍历函数
function in_order(current)
if current != NULL then
in_order(current.left_son);
//计算该节点X坐标
current.x = next++;
current.y = 2 * current.height + 1;
in_order(current.right_son);
end if;
end function;
begin
in_order(root);
end;
这种算法存在一个问题，即节点的布局过于分散化，因为所有节点的X坐标都是按照中序遍历的方式叠加上去的，而不存在某些节点具备相同的X坐标值，特别是对于节点之间next间隔设置较大的情况，二叉树的布局就显得不那么美观，如下图所示。
