Tree-Painter
以垂直方式绘制一组树节点。允许导出SVG图像。
旧版本
运行示例
导出的图像
引言
图形用户界面可以提供对同一概念的多种理解方式，而“树”是计算机科学课程中学习的基本数据结构之一。
树形图、树状图或树形绘制可以快速轻松地理解层次结构、搜索地图、演化与继承、短语结构、组织图或思维导图，以及由此衍生出的各种应用。
这是绘图算法的基本描述，只是从个人角度解释一种布局。我希望它能帮助您或作为未来项目、扩展功能或简单“帮助”的基础。
也许过去有、现在有、将来还会有更多的解释、其他方法、不同的想法来实现相同的目标，但我们每个人的理解方式都不同，没有普遍的法律或普遍可理解的描述方式，所以，这是一种贡献，希望能为某些人带来好处，或为共同利益而扩展它。
背景
在我主修期间，当我学习“自动机理论语言”课程时，我们被要求开发一个程序，其主要任务是验证“上下文无关文法”，并且有一个次要目标是能够绘制“解析树”。
在那几年，Java版本是1.4，我的团队选择了它来编程作业，由于绘图不是项目的主要部分（理论逻辑才是），我们把它留到了最后，而我们的绘图并不美观……
在同一学期，我的朋友 Tomás Ortíz S. 更聪明，他使用了VB的一个树控件……完成了老师要求的任务，节点按顺序绘制并分组良好。换句话说，他很有效率，节省了时间。
几年后我毕业了，那个项目又回到我脑海中，我记得我们当时（那时）奇怪为什么不存在一个绘制树形或图形的控件……最近，我对此进行了一些搜索，发现没有太多项目（至少在描述方法方面）。我知道树很简单，但考虑到这一点，我想到这个结构有很多用途，我在介绍中已经提到。当然，我们现在有各种绘图工具……但在我看来，我们直接从原始需求跳到了最终应用，而没有记录过程。本文旨在填补这一空白。
我必须说……我写最后一段是为了说明我写这篇文章的第一个也是主要动机，但随后我不得不承认，在试图让我相信信息不多的时候，我错了，我最初考虑的4或5个选项……变成了10多个不同的方法，我想在最后以链接的形式总结和列出。我一开始并没有考虑所有这些，但在尝试了不同的搜索词“tree viewer”、“tree drawing code”、“tree painter”、“graph”、“visualization”……之后，我发现了很多“派生分支”。我希望保持这个列表，并随着社区的建议不断增长。
Using the Code
本文以两个控件为基础：TreeView 和 Panel 。它们都已标准化，文档齐全，并且有大量的示例。公开的代码演化了3个“主要”版本，第三个版本中，添加了 Label 控件来标识每个节点。
对于初学者和中级开发者，本文将继续保持其“初步方法”的目标。制作用户控件或组件，或将代码公开为Web服务可能是此任务的第二个发布版本。
对于输入，我决定使用 TreeView 。对于输出，如果我只想绘制矩形或椭圆形，我可以采用 Canvas ……但经过一番分析，您会发现 Panel 提供了 Canvas 图形对象，并作为我们“节点”（版本3中的Label）的容器。
在本文中，我将主要介绍源代码的最后一个版本。注释已放在代码中，并且与第一个版本应用了相同的原则。
分析
让我们开始吧。假设我们有一些具有不同节点数量的树。
图1、2和3是简单的例子。在每个例子中，复杂性都在增加。这些是“手工”布局。
而主要问题是：如何以“美观”的方式定位每个节点？嗯……这是一个关键点……应该花几个小时来解决。如果您继续阅读……您将剥夺自己解决这个谜题的机会，并且可能在脑海中发展出一些东西。但是，您也可以从本文开始，开发一种新的替代方案。
话虽如此……让我们假设我们计算了每个分支的最后一层……
对于第一个树形图，所有“子节点”的层级都相同……
对于图4、5和6，每个分支都有不同的“深度”。
关键点（获得节点排列）是“平衡”（如果没有更好的词）树。换句话说，填充每个分支，使每个分支包含相同数量的层级（深度）。每个分支不需要有相同数量的子节点，我们只需要相同的层级数量。图5可以近似说明如何想象较短分支中的“缺失”节点（您将如何平衡该树？）。在开始分析之后，相同的原理可以应用于任何类型的分支或树。只需“填补空白”。图5碰巧显示了每个分支下相同数量的子节点，图6显示了不必有相同数量的子节点。图5和6显示了灰色的缺失节点。
现在，这是完整的布局，下一个问题可能是从哪里开始绘制？。我们如何知道每个“父节点”的中心位置？这是另一个好问题（当您一无所知时）。
假设我们混合了图3和图4。
我们可以有一个“第一个美观的布局”。
但是如果我们添加了想象中的缺失节点，那么那些节点可能会“重叠”……
在观察了图5和图6的布局之后……如果我们寻找最小的空间或“连续节点”，很容易发现最深的层级可以确定节点的第一位置，而不会超出上层。
从一个简单的例子开始，序列将是以下情况：
因此，另一个关键点将是从底部开始（最深的层级），然后确定父节点的位置。我假设一个好的树或节点结构（与TreeView不同或替代）应该能够轻松确定节点的父节点。
下面解释的代码将利用前面暴露的分析。请检查注释。
代码
主函数在此处粘贴，但我建议您检查源代码中的代码并进行调试。
我认为locateNodes
/// <summary>
/// Function that obtains children for each node in the <c>TreeNodeCollection</c>.
/// The full 'family' will be contained in the <c>ArrayList</c>.
/// </summary>
/// <param name="nodes"><c>TreeNodeCollection</c> to read.</param>
/// <param name="array">Destination of data.</param>
/// <returns>A integer with the counter of all nodes.</returns>
private int getAllChildNodes(TreeNodeCollection nodes, ArrayList array)
...
/// <summary>
/// Function to iteratively add 'auxiliar' nodes to the current <c>t</c> node.
/// </summary>
/// <param name="t">A <c>TreeNode</c> contained in a TreeView.</param>
/// <param name="untilLevel">Maximum depth. If the <c>t</c> node is not in this level,
/// this function will add one 'auxiliar' node to it, as child.
/// </param>
private void addBlankNode(TreeNode t, int untilLevel)
...
/// <summary>
/// Main Function to Locate and Draw Nodes based on a TreeView.
/// V2 Named "drawNodes"
/// V3 Renames to "locateNodes"
/// </summary>
/// <param name="drawingPanel">Panel that will be used as Drawing Board.</param>
/// <param name="originalTree">TreeView containing the Nodes to draw.</param>
/// <param name="tempTree">Temporary (Work) variable.</param>
private void locateNodes(Panel drawingPanel, TreeView originalTree,
TreeView tempTree, out ArrayList labeledNodes)
{
tempTree.Nodes.Clear();
// Version 3 Feature
// ArrayList labeledNodes; // ArrayList which will contain Label objects.
Label labelAux; // Temporary Label which will be added to
// the labeledNodes arrayList.
labeledNodes = new ArrayList();
if (originalTree.Nodes.Count == 0)
return;
#region drawing variables
Graphics board = drawingPanel.CreateGraphics();
int x = 20;
int y = 20;
int maxDepht = 0;
ArrayList list;
ArrayList[] listByLevel;
int xInitial = int.Parse(xStart.Value.ToString());
int yInitial = int.Parse(yStart.Value.ToString());
// this.drawNodeFont = new Font(System.Windows.Forms.TextBox.DefaultFont.FontFamily,
this.drawNodeFont = new Font("Arial",
float.Parse(fontSize.Value.ToString()),FontStyle.Bold);
#endregion
/*
* 1. Obtain Nodes per each Level.
* 'x' position will identify the 'index' of the node in each level.
* 'y' position will identify the 'level'.
* 2. Draw nodes, starting from the left (first node) of the deepest level.
* The posterior nodes (from the same level) should have an 'x' position
* equal to the current 'x' node position plus the node width.
* 3. When each 'level' is fully drawn (printed), or located, then,
* the superior level should continue. ('y' is decreased).
* 4. The 'father' should know which is its own center, based on
* the 'x' position of the 'first' and 'last' child.
* 5. Each node should know its 'own' scope in 'x' and 'y' positions,
* based on its children. In other words, each time that a child
* is drawn (or printed), then, the parent should be 'updated' in
* its 'scope'.
* The 'Tag' property of each TreeNode can be used to store this info.
* A. Idea: Auxiliar (temporary) Nodes can be added to (fill) those
* TreeNodes that do not contain 'offspring' (any child). In this way,
* the drawing can 'start' with the 'deepest' level.
* Obviously, this 'temporary' Nodes will have a 'Tag' value
* indicating that the node is 'Non-printable'.
*
*/
list = new ArrayList();
int totalNodes = getAllChildNodes(originalTree.Nodes, list);
// Obtaining the deepest node.
foreach (TreeNode n in list)
if (n.Level > maxDepht)
maxDepht = n.Level; // Maximum Depth
// ArrayList to group nodes by level.
listByLevel = new ArrayList[maxDepht + 1];
// TreeNodes from originalTree are *copied* to tempTree (work TreeView)
foreach (TreeNode n in list)
if (n.Level == 0)
tempTree.Nodes.Add((TreeNode)n.Clone());
// Temporary adjusts will be made only on the tempTree (work TreeView)
list = new ArrayList();
totalNodes = getAllChildNodes(tempTree.Nodes, list);
// The 'branches' of tempTree will be checked; each branch should have the same 'depth'.
foreach (TreeNode n in list)
if (n.Nodes.Count == 0 && n.Level < maxDepht)
addBlankNode(n, maxDepht); // Recursive function
// Work Process is made only on the tempTree (work TreeView)
// At this point, each branch have the same 'depth'. Containing 'auxiliary' nodes.
list = new ArrayList();
totalNodes = getAllChildNodes(tempTree.Nodes, list);
// Nodes are grouped by its Level.
foreach (TreeNode n in list)
{
if (listByLevel[n.Level] == null)
listByLevel[n.Level] = new ArrayList();
listByLevel[n.Level].Add(n);
}
// Initial position for the bottom left node (last level, first node)
x = xInitial;
y = yInitial;
// Assigning Location of the nodes of the second tree, in hierarchical order.
for (int z = maxDepht; z >= 0; z--)
{
for (int index = 0; index < listByLevel[z].Count; index++)
{
TreeNode nodeToPaint = (TreeNode)(listByLevel[z][index]);
// Version 3 Feature
labelAux = new Label();
labelAux.Name = nodeToPaint.Name;
labelAux.Font = drawNodeFont;
labelAux.Text = nodeToPaint.Text;
labelAux.TextAlign = System.Drawing.ContentAlignment.MiddleCenter;
labelAux.AutoSize = true;
labelAux.BorderStyle = BorderStyle.FixedSingle;
labelAux.MouseLeave += new System.EventHandler(this.lblTest_MouseLeave);
labelAux.MouseEnter += new System.EventHandler(this.lblTest_MouseEnter);
labelAux.Tag = nodeToPaint;
// Drawing Style
if (nodeToPaint.Text == txbBlankValue.Text)
{ // Current node is auxiliar.
labelAux.BackColor = this.disabledNodeBackColor;
labelAux.ForeColor = this.disabledNodeForeColor;
}
else
{ // Current node contains valid data.
labelAux.BackColor = this.enabledNodeBackColor;
labelAux.ForeColor = this.enabledNodeForeColor;
}
unionNodeLinesPen = new Pen(labelAux.BackColor);
// Calculating Node Position.
labelAux.Location = new Point(x, y);
// nodeToPaint.Tag = labelAux.ClientRectangle;
nodeToPaint.Tag = new Rectangle(labelAux.Left,
labelAux.Top,
labelAux.PreferredWidth,
labelAux.PreferredHeight);
// If the current node is not in the last level, then,
// its position should be calculated based on its child nodes.
if (z < maxDepht)
{
Point posFirstChild =
getRectangleCenter((Rectangle)(nodeToPaint.FirstNode.Tag));
Point posLastChild =
getRectangleCenter((Rectangle)(nodeToPaint.LastNode.Tag));
Point relocatedPoint = labelAux.Location;
relocatedPoint.X = (posFirstChild.X + posLastChild.X) / 2 -
labelAux.PreferredWidth / 2;
System.Console.WriteLine(nodeToPaint.Text + " x= " + relocatedPoint.X
+ "\n ->1: " + nodeToPaint.FirstNode.Text + " (" + posFirstChild.X + ");"
+ "\n ->2: " + nodeToPaint.LastNode.Text + " (" + posLastChild.X + ");");
labelAux.Location = relocatedPoint;
// nodeToPaint.Tag = labelAux.ClientRectangle;
nodeToPaint.Tag = new Rectangle(labelAux.Left,
labelAux.Top,
labelAux.PreferredWidth,
labelAux.PreferredHeight);
}
// Union Lines
foreach (TreeNode t in nodeToPaint.Nodes)
{
Rectangle r = new Rectangle(labelAux.Left,
labelAux.Top,
labelAux.PreferredWidth,
labelAux.PreferredHeight);
// Parent Center
Point parentCenterPos = getRectangleCenter(r);
// Child Center
Point childCenterPos = getRectangleCenter((Rectangle)t.Tag);
childCenterPos.Y = ((Rectangle)t.Tag).Top;
board.DrawLine(unionNodeLinesPen, parentCenterPos, childCenterPos);
}
// Return Located Labels
labeledNodes.Add(labelAux);
// The next sibling node will be to the right of the current one.
// Where this node finishes plus Margin.
// Note: Label.Right != Label.Left + labelAux.PreferredWidth
x = labelAux.Left + labelAux.PreferredWidth +
int.Parse(xPadding.Value.ToString());
System.Console.WriteLine("Calculated X:" + x.ToString());
}
// The total nodes of the current level had been drawn.
// The previous (superior) level should be located above the current level.
y -= int.Parse(yPadding.Value.ToString());
}
// Drawing Root
//Point rootPos = new Point();
//Point posFirstRootChild = new Point();
//Point posLastRootChild = new Point();
//posFirstRootChild = (Point)((TreeNode)(listByLevel[0][0])).FirstNode.Tag;
//posLastRootChild =
(Point)((TreeNode)(listByLevel[0][listByLevel[0].Count - 1])).LastNode.Tag;
//rootPos.X = (posFirstRootChild.X + posLastRootChild.X) / 2;
//rootPos.Y = y;
//board.DrawString("Root", drawFont, drawBrush, rootPos.X, rootPos.Y);
//// Drawing Root Lines To First Level Nodes
//TreeNode[] tArr = (TreeNode[])listByLevel[0].ToArray(typeof(TreeNode));
//foreach (TreeNode t in tArr)
//{
// Point pChild = (Point)t.Tag;
// pChild.X += nodeWidth / 2;
// pChild.Y -= nodeHeight / 2 - 5;
// board.DrawLine(p, rootPos, pChild);
//}
//Last node (located at the bottom right position) of the last level.
//TreeNode rightNode = (TreeNode)(listByLevel[maxDepht][listByLevel[maxDepht].Count-1]);
//drawingPanel.AutoScrollMinSize = new Size(((Rectangle)(rightNode.Tag)).Right, 600);
}
关注点
起初，我决定解决这个问题作为个人挑战，但在看到我对代码的注释后，我想知道这是否可以被认为是我的第一个开源贡献，几天后，我决定迈出第一步，发布它，并可能从社区获得学习反馈。我认为我没有什么可失去的（这就是CodeProject的精神）。
我决定检查是否有人之前解决过这个问题，并且很高兴了解到不同的需求如何可以利用相同的原理。总结那些引起我注意的不同项目也很有趣。有C#、Java、Python、WPF的部署，以及Google Charts目前实验性的功能（我认为这些人现在有很多选择）。
我的谜题和个人挑战变成了一个对其他解决方案的研究，以及对不同在线工具、理论和符号的学习。我最初想象的是“少数”或“许多”应用程序，但事实上，如果您考虑到所有选项，它涵盖了“巨大的”范围。
搜索
- Piccolo2D。Piccolo2D是一个支持2D结构图形程序开发的工具包。Java和.NET。查看应用程序演示。
http://www.piccolo2d.org/ - Space Tree。Java。交互式树浏览器。
http://www.cs.umd.edu/hcil/spacetree/ - Google Chart Api。（特别是Graph Charts）。它指向GraphViz。
http://code.google.com/apis/chart/index.html - GraphViz。开源图形可视化软件。
https://graphviz.cn/ - Conchango Xml Visualizer。它指向Lithium。
http://consultingblogs.emc.com/howardvanrooijen/archive/2005/11/24/2424.aspx - Lithium。一个树形绘制组件（似乎因作者原因已停用）。它指向Netron。C#。
- Netron Project（原Lithium，C#）。
http://sourceforge.net/projects/netron-reloaded/ - Newick格式.
http://en.wikipedia.org/wiki/Newick_format
http://code.google.com/p/treepainter/（Python版）
http://www.phylodiversity.net/rree/drawtree/（Python，在线PDF或EPS树生成器） - Suffix Trees。http://marknelson.us/1996/08/01/suffix-trees/
http://www.jflap.org/（用于自动机） - Code Project. LayeredTreeDraw。WPF。
https://codeproject.org.cn/KB/WPF/LayeredTreeDraw.aspx - phpSyntaxTree - 轻松绘制语法树。
http://ironcreek.net/phpsyntaxtree/ - Automated Tree Drawing: XSLT and SVG。可以将紧凑的树表示转换为SVG图形。
http://www.xml.com/lpt/a/1472 - 树图绘制
http://domemtech.com/?p=26 - Silverlight实现的一些算法
http://domemtech.com/trees/index.html - 一个很好的列表（2003年制作）.
http://bioinfo.unice.fr/biodiv/Tree_editors.html - Dendroscope。Java。不同的可视化。德语。
http://ab.inf.uni-tuebingen.de/software/dendroscope/welcome.html
历史
版本简要总结
- V1. 一个窗体。一个树状视图。一个面板。节点大小有限，在
Panel控件的OnPaint事件中绘制。绘制文本，但不计算节点之间的边距，也不计算文本长度。 - V2. 重新组织的测试GUI。
节点大小动态。内部矩形指定位置（“x,y”坐标）和边界（文本的宽度和高度）。
文本宽度根据Font对象计算。
字体大小动态。
添加了动态“起始点”（起始点是指第一个最深子节点所在处的左下角位置）。
水平和垂直边距动态。
错误。Panel不显示超出可见区域的节点。 - V3. 添加了标签。内部矩形被移除。
大小无需计算，因为Label.Autosize属性可以完成这项工作。
Panel显示所有节点，超出可见区域的节点通过滚动条显示。 - V3.1 启用了导出到SVG文件的选项（内部和基本的SVG格式生成，没有使用特定库）。
未来
公开为 WebService：
想法/建议
- 输入：Newick格式（字符串格式）或XML格式。
- 输出：SVG格式（字符串格式）。
- 功能：动态生成给定的URL字符串的树。
基于Google Chart项目：http://code.google.com/apis/chart/
http://code.google.com/apis/chart/docs/gallery/graphviz.html
提出圆形（径向）布局
如果我们有两个第一级节点，它们将分开180°。
如果我们有三个第一级节点，它们将分开120°。
因此……360° / 节点是排列它们的对称公式，但当分支数量增加时，应考虑最深层级的位置，以避免重叠……
这是我在CodeProject上的第一篇文章，欢迎提出宝贵的意见，并且任何建议都将得到尊重和考虑。