将横向二叉树以文本/ASCII形式渲染的算法

Question

将横向二叉树以文本/ASCII形式渲染的算法

rubyalgorithmlanguage-agnostictextbinary-tree

8

这是一棵很普通的二叉树，唯一的不同之处在于其中一个节点可能为空。

我想找到一种水平输出它的方法（即，根节点在左侧并向右扩展）。

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

最好遵循以下几个规则：

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

例如，这是一个有效的树，有六个端节点（节点由名称及其深度表示）：EDIT：请参见问题底部的替代、更简单的渲染

（分支折叠以节省空间；*表示冗余的单一子节点；请注意，*是实际节点，每个节点仅存储一个子节点，但在此处为了演示而省略名称）

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

我说语言无关，因为我只是在寻找算法；我说ruby，因为最终我还必须在ruby中实现它。

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

一个主要的Tree类跟踪所有节点，并具有足够的算法来查找：

一个节点的第n个祖先
一个节点的第n个后代
一个节点的所有末端子孙，以及它们的数量
一个节点的一代
两个给定节点的最近公共祖先

我已经知道：

末端节点的数量

有人有任何想法从哪里开始吗？我应该采用递归方法还是迭代方法？伪代码也很酷，非常感谢 =）

进展

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

深度：0  1  2  3  4  5  6  8  9  10
       a        b     c     d
                               e
                      f
          g        h     i
                                  j
                k

生成此网格应该很容易，可以使用广度优先或深度优先搜索。可能最简单的方法是仅保留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-- => 指南线（不渲染）

相比之前发布的方案，这个方案更容易实现。首先，它保留了漂亮的网格形状，并且您不必担心对角线。所有行都沿着清晰可见的列线映射。不幸的是，它远没有第一个方案那么漂亮。

- Justin L.

这并不是你所问的，但你可以渲染到dot，然后告诉graphvis为你制作一张图片。 - Seth

关于您的编辑：以您的直接示例为例，将每行n个前导空格偏移，将所有管道替换为斜杠。这是一个简单的转换，可以从偏移形式转换为原始形式。 - Jimmy

@Jimmy - 谢谢！我想我会使用它；现在似乎更容易先构建直线示例，然后将其转换为曲线示例来解决问题？ - Justin L.

@Justin：你能发一下最终实现的代码吗？知道这个会很酷。 - alexkelbo

@alexraasch 这是用 Ruby 写的，代码在 https://github.com/mstk/Emerge/blob/master/lib/utils/graph_builder.rb .... 虽然我对代码的美观度不是太满意。但如果你想看的话可以去看看。'测试用例' 在底部被注释掉了，这样你就知道它应该如何使用了。 - Justin L.

显示剩余2条评论

5个回答

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);
    }
}

- gregschlom

2

如果您为每个级别（不包括[]字符）设置一个标签宽度，使其等于该宽度的最大标签（在本例中，宽度大多为2，除了j10是3，以及级别2和7是0），则每个具有非零最大标签宽度的级别之间用一个-字符等距分隔，以便计算初始级别y位置。

给每个节点分配其行号。

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

对a0至g1的级别1添加2
对g1至k3的级别2添加1
对b3至[]的级别4添加1

使用\和`字符来表示斜线。

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

- Stephen Denne

我喜欢这种方法，但是我不确定我完全理解它。你的“行初始化”似乎只覆盖了第一行，顶部行...如果要渲染第二行、第三行，你会如何进行初始渲染？ - Justin L.

1

以下是完全功能的C#代码，可以完全满足您的需求。它是如何实现的：

树被表示为从继承自Node类的对象中获取
首先计算叶子节点的数量并创建一个相应行数的数组
然后对于每个级别：
- 找出要写入哪些行
- 对于这些行，计算已经在这些行上的最大值
- 将所有节点写入到列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<NamedNode>().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<Binary>().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<Node> 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<Node> 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<Node> 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<Node> Children
        {
            get
            {
                yield break;
            }
        }
    }
}

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

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

- svick

你有给定树的输出吗？实际上，我一直想安装.NET和C#编译器...现在正在安装... - Justin L.

0

你可能需要执行深度优先搜索，如果不是搜索整个树的话，以便根据两个维度适当地调整其输出大小。

- btreat

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- walkytalky · Accepted Answer

如果有N个末端节点，则必须有N-1个具有2个子节点的内部节点。(可以有任意数量的只有1个子节点的内部节点，我们需要计算深度，但除此之外忽略它们。)因此，生成树等效于在网格上定位这些节点，其中:

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

所以，让我们看看:

从右到左深度优先遍历树。
对于每个端点，记录其深度和标签。
对于每个具有2个子节点的内部节点，记录其深度、标签和两个最右侧和最左侧子节点端点的索引。
按深度对整个内容进行排序——这给出了列顺序，具有不同深度的数量给出了实际列数。(我认为所有其他排序都应该自动从遍历中得出，但这里不是这样，因为任何分支都可以是任何深度。)
将所有节点放置在网格中。
将每个非末端节点右侧的空单元格标记为水平分支。
将每个内部节点向下标记为空单元格，直到其左子节点上方的行为垂直分支，并将左子节点所在级别的单元格标记为连接点。
使用适当的ASCII装饰打印。

更新:

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

我觉得打印是微不足道的，可以忽略:

迭代每一列并确定列宽为大小为固定元素+最大标签长度+floor(log10(depth) + 1)。（例如，固定元素可能是[和]-。我们可以将]\n替换为端点的后缀。）
对于每一行
- 对于每一列
  - 如果单元格包含节点或端点
    - 打印固定前缀
    - 打印标签
    - 打印深度
    - 打印填充空格（最大标签长度-当前标签长度）
    - 打印适当的后缀
    - 如果节点是端点，则跳到下一行
  - 如果单元格为空，则打印填充空间以占据整个列宽
  - 如果单元格包含垂直线，则打印一些选择的前缀数量的空格、一条竖线，并用空格填充
  - 如果单元格包含交叉点，则打印一些选择的前缀数量的空格、一个反斜杠，并用连字符填充
  - 如果单元格包含水平线，则打印整个列宽的连字符

如果您想将其转换为打印对角线，最简单的方法可能是先生成直线版本，然后在字符数组中进行一些替换--否则，您可能会遇到在不同列中呈现长垂直分支的情况。

在某个时候，我可能会尝试将其放入代码中，但今天可能不会--还有其他事情要做！