tree - GraphViz 中的并排二叉树

Question

我正在尝试并排格式化 2 个(或理想情况下 N 个)断开连接的二叉树，并且我希望格式化对于二叉树来说是“正确的”，大致如下:

即使某些节点丢失，其余节点也应保持原样。

我使用 this Stack answer 中名为 tree.gv 的脚本为一棵树生成了这种平衡的近似值。 :

dot one_tree.dot | gvpr -c -f tree.gv | neato -n -Tpdf -o tree.pdf

它并不像我想要的那样完美平衡，但它非常可行。

现在我想要多棵并排的树。这是我尝试过的:

dot trees.dot | neato -n -Goverlap=false -Tpdf -o tree.pdf

正确地并排放置，但底部的黑色叶子应该向右张开，为失踪的 sibling 留出空间。

dot trees.dot | gvpr -c -f tree.gv | neato -n -Tpdf -o tree.pdf

每棵树的格式都正确，但它们重叠。

将两者结合起来肯定可行吗？

dot trees.dot | gvpr -c -f tree.gv | neato -n -Goverlap=false -Tpdf -o tree.pdf

这是trees.dot:

digraph BST {
    graph [center=true, margin=0.01, nodesep=0.1, ranksep=0.3, width=1,ratio=.25];
    node [fontname="Arial",style=filled,color="0.0 0.0 0.0",fixedsize=true,width=0.15,shape=circle,label=""];
    node [margin=0.01,fillcolor="lightgrey"];
    edge [dir=none];
    node [fillcolor="black"];
    Lower;
    Lower -> LowerR;
    Lower -> LowerL;
    LowerL -> LowerLR;
    LowerR -> LowerRR;
    node [fillcolor="red"];
    Upper;
    Upper -> UpperR;
    Upper -> UpperL;
}

Answer 1

形成树的主要技巧是使用具有高边权重的额外不可见节点，然后将其直接放置在父节点下方。出现的顺序很重要。

digraph BST {
    graph [center=true, margin=0.01, nodesep=0.1, ranksep=0.3, width=1,ratio=.25];
    node [fontname="Arial",style=filled,color="0.0 0.0 0.0",fixedsize=true,width=0.15,shape=circle,label=""];
    node [margin=0.01,fillcolor="lightgrey"];
    edge [dir=none];
    node [fillcolor="black"];
    Lower;
    LowerL;
    LowerM [style=invis];
    LowerR;
    Lower -> LowerR;
    Lower -> LowerM [weight=100 style=invis];
    Lower -> LowerL;
    LowerLM [style=invis];
    LowerLR;
    LowerRM [style=invis];
    LowerRR;
    LowerL -> LowerLR;
    LowerL -> LowerLM [weight=100 style=invis];
    LowerR -> LowerRR;
    LowerR -> LowerRM [weight=100 style=invis];
    node [fillcolor="red"];
    Upper;
    UpperR;
    UpperM [style=invis];
    UpperL;
    Upper -> UpperR;
    Upper -> UpperM [weight=100 style=invis];
    Upper -> UpperL;
}

为了防止独立的树或 Twig 水平重叠，您必须使用簇(请参阅我对 Making graphviz trees have parents centred above children 的回答)

digraph BST {
    graph [center=true, margin=0.01, nodesep=0.1, ranksep=0.3, width=1,ratio=.25];
    node [fontname="Arial",style=filled,color="0.0 0.0 0.0",fixedsize=true,width=0.15,shape=circle,label=""];
    node [margin=0.01,fillcolor="lightgrey"];
    edge [dir=none];
    node [fillcolor="black"];
    graph [style=invis];
    subgraph cluster_Lower {
        Lower;
        LowerL;
        LowerM [style=invis];
        LowerR;
        Lower -> LowerR;
        Lower -> LowerM [weight=100 style=invis];
        Lower -> LowerL;
        LowerLM [style=invis];
        LowerLR;
        LowerRM [style=invis];
        LowerRR;
        LowerL -> LowerLR;
        LowerL -> LowerLM [weight=100 style=invis];
        LowerR -> LowerRR;
        LowerR -> LowerRM [weight=100 style=invis];
    }
    node [fillcolor="red"];
    subgraph cluster_Upper {
        Upper;
        UpperR;
        UpperM [style=invis];
        UpperL;
        Upper -> UpperR;
        Upper -> UpperM [weight=100 style=invis];
        Upper -> UpperL;
    }
}