>

GraphViz를 사용하여 이진 검색 트리에 대한 예제 다이어그램을 다시 만들려고합니다. 이것이 최종적으로 보이는 방법입니다 :

이것은 나의 첫 번째 시도입니다 :

digraph G {
    nodesep=0.3;
    ranksep=0.2;
    margin=0.1;
    node [shape=circle];
    edge [arrowsize=0.8];
    6 -> 4;
    6 -> 11;
    4 -> 2;
    4 -> 5;
    2 -> 1;
    2 -> 3;
    11 -> 8;
    11 -> 14;
    8 -> 7;
    8 -> 10;
    10 -> 9;
    14 -> 13;
    14 -> 16;
    13 -> 12;
    16 -> 15;
    16 -> 17;
}

안타깝게도 GraphViz는 트리의 수평 위치를 신경 쓰지 않으므로 다음과 같이 나타납니다.

정점의 수평 위치가 전체 순서를 반영하도록 구속 조건을 어떻게 추가 할 수 있습니까?


  • 답변 # 1

    균형 트리에 대한 graphviz FAQ에서 제안한 것처럼 보이지 않는 노드와 보이지 않는 가장자리를 추가하고 가장자리 가중치 등을 사용하는 일반적인 접근 방식을 따를 수 있습니다. 간단한 경우에는 이것으로 충분합니다.

    그러나 더 나은 해결책이 있습니다. Graphviz에는gvpr(그래프 패턴 스캐닝 및 처리 언어)이라는 도구가 제공되어

    와이즈 비즈

    Emden R. Gansner는 이진 트리를 멋지게 레이아웃하는 스크립트를 작성하여 이미 모든 작업을 수행 한 이후로 그 방법을 설명합니다 (모든 크레딧은 ERG로 이동).

    다음 gvpr 스크립트를

    copy input graphs to its output, possibly transforming their structure and attributes, creating new graphs, or printing arbitrary information

    라는 파일에 저장하십시오.  :

    tree.gv
    
    

    그래프를 포함하는 도트 파일을 BEGIN { double tw[node_t]; // width of tree rooted at node double nw[node_t]; // width of node double xoff[node_t]; // x offset of root from left side of its tree double sp = 36; // extra space between left and right subtrees double wd, w, w1, w2; double x, y, z; edge_t e1, e2; node_t n; } BEG_G { $.bb = ""; $tvtype=TV_postfwd; // visit root after all children visited } N { sscanf ($.width, "%f", &w); w *= 72; // convert inches to points nw[$] = w; if ($.outdegree == 0) { tw[$] = w; xoff[$] = w/2.0; } else if ($.outdegree == 1) { e1 = fstout($); w1 = tw[e1.head]; tw[$] = w1 + (sp+w)/2.0; if (e1.side == "left") xoff[$] = tw[$] - w/2.0; else xoff[$] = w/2.0; } else { e1 = fstout($); w1 = tw[e1.head]; e2 = nxtout(e1); w2 = tw[e2.head]; wd = w1 + w2 + sp; if (w > wd) wd = w; tw[$] = wd; xoff[$] = w1 + sp/2.0; } } BEG_G { $tvtype=TV_fwd; // visit root first, then children } N { if ($.indegree == 0) { sscanf ($.pos, "%f,%f", &x, &y); $.pos = sprintf("0,%f", y); } if ($.outdegree == 0) return; sscanf ($.pos, "%f,%f", &x, &y); wd = tw[$]; e1 = fstout($); n = e1.head; sscanf (n.pos, "%f,%f", &z, &y); if ($.outdegree == 1) { if (e1.side == "left") n.pos = sprintf("%f,%f", x - tw[n] - sp/2.0 + xoff[n], y); else n.pos = sprintf("%f,%f", x + sp/2.0 + xoff[n], y); } else { n.pos = sprintf("%f,%f", x - tw[n] - sp/2.0 + xoff[n], y); e2 = nxtout(e1); n = e2.head; sscanf (n.pos, "%f,%f", &z, &y); n.pos = sprintf("%f,%f", x + sp/2.0 + xoff[n], y); } } 라고 가정합니다 , 다음 줄을 실행할 수 있습니다 :

    binarytree.gv
    
    

    결과 :

    스크립트에서 한 줄 또는 두 줄을 바꾸면 단일 자식 노드가 오른쪽 대신 왼쪽으로 이동하게됩니다.

    dot binarytree.gv | gvpr -c -ftree.gv | neato -n -Tpng -o binarytree.png

  • 이전 c++ - C ++ 0x의 모든 생성자 전달
  • 다음 c# - NET Reflection에서 BindingFlagsDeclaredOnly와 함께 GetProperties () 사용