以文本/ ASCIIforms渲染水平二进制树的算法

这是一个非常普通的二叉树，除了其中一个节点可能是空的。

我想找到一种以水平方式输出它的方法（也就是说，根节点在左边并向右扩展）。

我有一些垂直扩展树木的经验（根节点在顶部，向下扩展），但在这种情况下，我不知道从哪里开始。

最好是遵循以下几条规则：

• 如果一个节点只有一个子节点，则可以将其作为冗余跳过（始终显示“终端节点”，没有子节点）
• 相同深度的所有节点必须垂直对齐; 所有节点必须位于所有较低深度节点的右侧，并且位于所有较深节点的左侧。
• 节点具有包含其深度的字符串表示。
• 每个“端节点”都有自己独特的线路; 也就是说，行数是树中终端节点的数量，当终端节点在一条线上时，在该终端节点之后该行上可能没有其他内容。
• 作为最后一条规则的结果，根节点在左上角或左下角可能会更好; 左上角是首选。

例如，这是一个有效的树，有六个端节点（节点由一个名称及其深度表示）： 编辑：请参阅问题的底部以获得替代，更容易渲染

        
 [A0] ----------- [B3] ------ [C5] ------ [D8]
     \ ---- \ ------- [e9]
      ---- [f5]
       \  -  [G1] -------- [H4] ------ [I6]
             \ -------------------- [j10]
              \  -  [K3]

它代表垂直的显式二叉树：

 0 a
               / \
 1克*
             / \ \
 2 * * *
           / \ \
 3 k * b
                 / / \
 4小时*
               / \ \ \
 5 * * fc
             / \ / \
 6 * i * *
           / / \
 7 * * *
         / / \
 8 * * d
       //
 9 * e
     /
 10 j

（折叠为紧凑的分支; *表示冗余的单子节点;请注意*是实际节点，每个节点存储一个子节点，为了表示而省略了名称）

（另外，为了澄清，我想生成第一个水平树;不是这个垂直树）

我说语言不可知，因为我只是在寻找算法; 我说ruby是因为我最终还是要在ruby中实现它。

假设每个Node数据结构仅存储其id，左节点和右节点。

主Tree类保留所有节点的轨道，并具有足够的算法来查找：

• 节点的第n个祖先
• 节点的第n个后代
• 节点的所有端节点后代及其计数
• 生成节点
• 两个给定节点的最低共同祖先

我已经知道了 ：

• 端节点的数量

任何人都有我可以从哪里开始的想法？ 我应该采用递归方法吗？ 迭代？ 一些Psuedo代码也会很酷，非常感谢=）

---

进展

根据walkytalky的建议，我决定看看将每个“相关”或重要节点映射到网格的样子，其中列是深度，行可以通过其末端节点识别。 这是发生的事情（跳过第7列，因为深度7中没有重要的节点）：

深度：0 1 2 3 4 5 6 8 9 10
        A B C D
                                Ë
                       F
           GHI
                                   Ĵ
                 ķ

使用广度优先或深度优先搜索生成此网格应该很容易。 也许最简单的是通过简单地保持2D数组并将每个重要节点放入其中，为每个“第二个孩子”插入一行。

现在，了解这些事实：

• 一行中的最后一个节点必须是结束节点
• 子节点始终位于其父节点的右侧，同一行或更低位置。
• 所有非端节点必须只有两个子节点
• 因此，所有非端节点都有子列 ， 它们是列的右边第一个，第一个子节点位于同一行，第二个子节点位于它们下面n行，其中n是右侧节点的数量。它。

我们可以看到，给定任何有效网格，有一种明确的方法可以“连接点”，可以这么说; 有一个明确的树被代表。

现在，“连接点”不再是二元树结构问题……它只是一个装饰问题。 我们只需构建一个算法来正确放置权利和它们可以去的地方，也许只遵循简单的网格/词典规则 ，而不是二叉树结构规则。

基本上，这意味着渲染树的问题现在是渲染网格的更简单的问题，具有奇特的装饰。

任何人都可以建议任何制定这些规则的方法吗？ 或者可能完全不同的方法？

---

编辑

我已经设想了一个更容易，更简单的最终渲染：

 --d0 ---- d1 ---- d3 ---- d4 ---- d5 ---- d6 ---- d8 ---- d9 ---- d10-- =>引导线（没有渲染）

  [a0] ------- [b3] ------- [c5] ------- [d8]
    |  |  \ --------------- [e9]
    |  \ --------- [f5]
    \ --- [g1] ------- [h4] ------- [i6]
          |  \ --------------------------- [J10]
          \ --- [k3]

 --d0 ---- d1 ---- d3 ---- d4 ---- d5 ---- d6 ---- d8 ---- d9 ---- d10-- =>引导线（没有渲染）

尝试创建这个可能更容易，而不是我之前发布的那个。 首先，它保留了一个漂亮的网格形状，你不必与对角线变幻无常。 所有行都沿着清晰可见的列线映射。 不幸的是，它远没有第一个那么漂亮。

Answer 1

如果有N端节点，则必须有N-1内部节点，其中包含2个子节点。 （可以有任意数量的具有1个子节点的内部节点，我们必须对其进行计数才能获得深度，否则将忽略。）因此，生成树等同于将这些节点定位在网格上，其中：

• 网格中的行数是N
• 我认为列数在1+floor(log2(N))和2*N-1 ，具体取决于有多少重叠; 不过，这对我们的目的来说可能并不重要
• 每个端点出现在不同的行上
• 同一深度的所有节点都出现在同一列中
• 所有内部节点都显示在与其最右侧后代端点相同的行上

所以，让我们看看：

• 首先从右到左走树深度。
• 对于每个端点，记录其深度和标签。
• 对于每个2个孩子的内部，记录其最右侧和最左侧子端点的深度，标签和索引。
• 按深度对整批进行排序 – 这为您提供了列排序，其中不同深度的数量给出了实际的列数。 （我想，所有其他的顺序应该从步行中自动出来，但这不是这种情况，因为任何分支都可以是任何深度。）
• 将所有节点放在网格中。
• 将每个非端点节点右侧的空单元标记为水平分支。

• 将空单元格从每个内部节点向下标记为其左子节点上方的行作为垂直分支，并将左子节点级别的单元格标记为交汇点。

• 使用适当的ASCII装饰打印。

更新：

正如你所说，定位足以明确地确定连接，但你仍然需要做一些自下而上的工作才能做到这一点，所以我可能仍然会在网格构建过程中执行“标记”步骤。

我有点认为印刷很容易擦亮，但是：

• 迭代每列并确定列宽为size of fixed elements + max label length + floor(log10(depth) + 1) 。 （固定元素可能是[和]- ，例如。我们可以替换]\n作为端点的后缀。）
• 对于每一行
  • 对于每一列
    • 如果单元格包含节点或端点
      • 打印固定前缀
      • 打印标签
      • 印刷深度
      • 打印填充空格（最大标签长度 – 当前标签长度）
      • 打印适当的后缀
      • 如果node是端点，则跳到下一行
    • 如果单元格为空，则将填充空格打印到列宽
    • 如果单元格包含垂直，则打印一些选定的前缀空格数，一个条形，并填充空格
    • 如果单元格包含一个联结，则打印一些选定的前缀空格数，一个反斜杠，并用连字符填充
    • 如果单元格包含水平，则打印连字符的完整列宽

如果首先生成直接版本然后在字符数组中进行一些替换，则将此转换为打印对角线可能是最简单的 – 否则您可以获得在与其中的列不同的列中呈现长垂直分支的情况。起源。

在某些时候，我可能会尝试将其放入代码中，但它可能不会是今天 – 要做的事情！

Answer 2

看起来像一个有趣的问题; 如果我有更多的时间，我会很乐意尝试一下。

我可能会采用以下方法：

1. 开始呈现“正确”（或在您的情况下，“顶部”）节点，直到我到达结束。 （即：渲染a，b，c和d）
2. 返回带有子节点的最后一个节点（即：c），并以递归方式执行相同的操作

您必须保留一个全局变量，指示您要打印的行。 每次递归调用都会增加此变量。

编辑：确定，无法抗拒尝试编写一些未经测试的伪代码，希望它有效：

 function print_tree(Node n) { print "\n" // begin on a fresh new line childs = new Array(); do { if (n.hasLeftChild) { childs.push(n.leftChild) } print "---" + n.id //this needs a lot of tweaking, but you get the idea } while(n = n.rightChild) childs.reverse() foreach(child in childs) { print_tree(child); } } 

Answer 3

如果以每个级别的标签宽度开始（不包括[]字符），则等于该宽度的最大标签（在此示例中，宽度大多为2除了j10 ，即3，级别2和7为0） 。

每个级别的非零最大标签宽度均等间隔，每个级别之间有一个字符，因此您可以计算初始级别y位置。

给每个节点它的行号。

然后根据级别的子级之间的最大行数调整级别位置。

为a0到g1的级别1添加了2
为g1到k3为级别2添加1
为b3添加1到4级到[]

对角线使用\和`字符。

 [A0] --------- [B3] ------- [C5] ------ [D8]
     \ ----“---------- [e9]
      \`----- [f5]
       `[G1] -------- [H4] ------ [I6]
            \`-------------------- [j10]
             `[K3]

Answer 4

下面是function齐全的C＃代码，可以完全满足您的需求。 它是如何做到的：

• 树表示为从Nodeinheritance的类中的对象
• 首先计算叶子的数量并创建那么多行的数组
• 然后为每个级别：
  • 找出我们要写的线
  • 对于这些线，计算这些线上已有的线的最大值
  • 将所有节点写入max max（上一步的数字，上一级的结束）+1; 前置-以获取该列
  • 从所有二进制节点写入对角线直到他们右边的孩子的线（在我的程序中，第一个孩子被留下，第二个是对的，你有另一个方向）
  • 提升一个级别

该算法确保每个级别仅在前一个结束后才开始。 这可能是短名称的好选择，但对于更长的名字，这可能不应该强制实施。

 using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace SO_ASCII_tree { class Program { static void Main() { Node root = …; StringBuilder[] lines = Enumerable.Range(0, root.Leaves).Select(i => new StringBuilder()).ToArray(); Node[] currentLevel = new Node[] { root }; int level = 0; int min = 0; int max = 0; while (currentLevel.Any()) { NamedNode[] namedNodes = currentLevel.OfType().ToArray(); if (namedNodes.Any()) { min = namedNodes.Select(node => lines[node.Line].Length).Max(); min = Math.Max(min, max); if (min != 0) min++; foreach (NamedNode namedNode in namedNodes) WriteAtPosition(lines[namedNode.Line], namedNode.Write(level), min, '-'); max = namedNodes.Select(node => lines[node.Line].Length).Max(); // change to max = min + 1; for long names } foreach (Node node in currentLevel) node.SetChildLines(); Binary[] binaries = namedNodes.OfType().ToArray(); foreach (Binary binary in binaries) GoDown(lines, binary.Line, binary.Right.Line); currentLevel = currentLevel.SelectMany(node => node.Children).ToArray(); level++; } foreach (StringBuilder line in lines) Console.WriteLine(line.ToString()); } static void WriteAtPosition(StringBuilder line, string message, int position, char prepend = ' ') { if (line.Length > position) throw new ArgumentException(); line.Append(prepend, position - line.Length); line.Append(message); } static void GoDown(StringBuilder[] lines, int from, int to) { int line = from + 1; int position = lines[from].Length; for (; line <= to; line++, position++) WriteAtPosition(lines[line], "\\", position); } } abstract class Node { public int Line { get; set; } public abstract int Leaves { get; } public abstract IEnumerable Children { get; } public virtual void SetChildLines() { } } abstract class NamedNode : Node { public string Name { get; set; } public string Write(int level) { return '[' + Name + level.ToString() + ']'; } } class Binary : NamedNode { public Node Left { get; set; } public Node Right { get; set; } int? leaves; public override int Leaves { get { if (leaves == null) leaves = Left.Leaves + Right.Leaves; return leaves.Value; } } public override IEnumerable Children { get { yield return Left; yield return Right; } } public override void SetChildLines() { Left.Line = Line; Right.Line = Line + Left.Leaves; } } class Unary : Node { public Node Child { get; set; } int? leaves; public override int Leaves { get { if (leaves == null) leaves = Child.Leaves; return leaves.Value; } } public override IEnumerable Children { get { yield return Child; } } public override void SetChildLines() { Child.Line = Line; } } class Leaf : NamedNode { public override int Leaves { get { return 1; } } public override IEnumerable Children { get { yield break; } } } } 

编辑 ：您的示例树渲染与渲染完全相同：

 [a0]-----------[b3]------[c5]------[d8] \ \ \----------[e9] \ \----[f5] \-[g1]--------[h4]------[i6] \ \--------------------[j10] \-[k3] 

Answer 5

如果不搜索整个树，您可能需要执行深度优先搜索，以便为2维的输出正确resize。