Боковые бинарные деревья в GraphViz

Question

Я пытаюсь отформатировать 2 (или идеально N) отключенные бинарные деревья бок о бок, и я хочу, чтобы форматирование было «правильным» для двоичного дерева, примерно как так:

Даже если некоторые узлы отсутствуют, остальные должны оставаться именно там, где они есть.

Я сгенерировал приближение этого балансирования для одного дерева со сценарием под названием tree.gv из this Stack answer:

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 

Должным бок о бок, но нижние черные листья должны быть растопыренными право, оставляя место для своих пропавших родственников.

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

Для предотвращения независимых деревьев или веток деревьев из горизонтального перекрытия необходимо использовать кластеры (см мой ответ 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; 
    } 
}