C ++에서 BST를 인쇄하는 방법

StackOverflow https://stackoverflow.com/questions/2242097

  •  19-09-2019
  •  | 
  •  

문제

내 C ++ 프로그램은 이진 검색 트리를 만듭니다. 나는 선주문, 사후 주문 및 주문에서 값을 인쇄하는 방법을 알고 있습니다.

그러나 나는 조금 더 어려운 일을하고 싶습니다. 누군가가 종이에 나무를 그렸을 때 보는 방식으로 가치를 인쇄하고 싶습니다. 그것은 상단의 중앙에 뿌리를 내릴 것이고, 그것은 왼쪽 아이가 바로 아래와 왼쪽에 있으며, 바로 바로 아래와 오른쪽에있는 오른쪽 아이입니다. 나머지 노드는 그에 따라 그려집니다.

어떻게 할 수 있습니까?

도움이 되었습니까?

해결책

이 기사 필요한 것에 대한 코드가 포함되어 있습니다.

Alt Text http://www.cpp-programming.net/wp-content/uploads/2007/12/ascii_tree.jpg

편집 : 해당 사이트는 오프라인으로 갔다

여기에 있습니다 다른 것 다른 옵션을 탐색합니다.

다른 팁

다음은 근사한 의사 코드입니다. 기본 아이디어는 트리 레이어별로 걸어 다니면서 각 레이어의 모든 노드를 한 줄에 인쇄하는 것입니다. 각 노드는 아래 노드보다 두 배나 많은 공간으로 분리됩니다. 트리는 모두 균일 한 깊이가 아니기 때문에 노드가 존재하지 않는 빈 공간을 차지하기 위해 가상 노드로 인위적으로 패딩됩니다.

measure the depth of the tree, call that D
have two queues, called Q1 and Q2
enque the top node of the tree in Q1
for (i = D; --i>=0; ){
  foreach node in Q1 {

    on first iteration of this inner loop, print 2^i - 1 spaces,
    else print 2^(i+1) - 1 spaces.

    if node == null print blank
    else print node.value

    if node.left exists enque node.left in Q2
    else enque null in Q2

    if node.right exists enque node.right in Q2
    else enque null in Q2
  }
  copy Q2 to Q1
  clear Q2
  print end-of-line
}

인쇄 된 각 공간은 하나의 숫자 필드의 너비입니다. 트리에 깊이 d = 4가 있다고 가정합니다. 그러면 인쇄가 다음과 같습니다.

// it looks like this, and the space sequences are
i = 3: -------n 7
i = 2: ---n-------n 3 7
i = 1: -n---n---n---n 1 3 3 3
i = 0: n-n-n-n-n-n-n-n 0 1 1 1 1 1 1 1

한 가지 방법은 GraphViz를 사용하는 것입니다. 구체적으로 "DOT"프로그램을 사용하지만 출력을 정확하게 설명하는 것은 불가능할 수 있습니다. 

    void print(node *p,int start)
    {
        start++;
        if (p->right != NULL)
        {
            print(p->right,start);
        }
        for (int i = 0; i <= start; i++)
        {
            cout<<"    ";
        } 
        cout << p->value<<endl;
        if (p->left != NULL)
        {
            print(p->left, start);
        }
    }

글쎄, 터미널에서는 어렵습니다 ... 맞지 않을 수도 있습니다. 그러나 멋진 사진을 만들 수있는 그래프 드로잉 라이브러리가 있습니다. 가장 인기있는 그래비가 있습니다.

편집 : 텍스트를 인쇄하기 위해 실제로 Wan을 인쇄하는 경우 Graphvis는 사용자가 Graphvis로 전달할 수있는 마크 업 언어를 가지고있어 멋진 그림을 만듭니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top