以文本/ASCII格式呈现水平二进制ISH树的算法

如果有 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 作为端点的后缀。)
• 每行
  • 每列
    • 如果单元格包含节点或终结点
      • 打印固定前缀
      • 打印标签
      • 打印深度
      • 打印填充空间(最大标签长度-当前标签长度)
      • 打印适当的后缀
      • 如果节点是终结点,则跳到下一行
    • 如果单元格为空,则将填充空间打印到列宽
    • 如果单元格包含竖线,请打印选定的前缀、空格数、条形图,并用空格填充
    • 如果单元格包含一个连接,请打印一些选定的前缀、空格数、反斜杠,并用连字符填充
    • 如果单元格包含水平的,则打印连字符的完整列宽

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

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

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

我可能会采用以下方法:

1. 开始渲染“right”(右)节点(在您的例子中是“top”),直到我到达末尾。(即:渲染A、B、C和D)
2. 返回带有子节点的最后一个节点(即C),递归地执行相同的操作。

您必须在正在打印的wich行上保留一个全局变量。每次递归调用都会增加这个变量。

编辑:好吧,忍不住写一些未经测试的伪代码,希望它能工作:

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

如果从每个级别的标签宽度开始(不包括 [] 字符),等于该宽度的最大标签(在本例中,除了 j10 3级,2级和7级,0级)。

使每个级别的最大标签宽度不为零,并用一个等距 - 每个级别之间的字符,因此可以计算初始级别 y 位置。

给出每个节点的行号。

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

为a0至g1增加2至1级
增加1至2级,用于g1至k3
将1添加到4级,用于b3到[]

使用 \ 和 ` 对角线的字符。

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

下面是完全功能化的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]

如果不是搜索整个树,您可能需要执行深度优先搜索,以便正确地调整其大小,以便沿着2个维度进行输出。