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

Question

내 C++ 프로그램은 이진 검색 트리를 만듭니다. 나는 선주문, 후행 선 및 순서대로 값을 출력하는 방법을 안다.

그러나 조금 더 어려운 일을하고 싶습니다. 누군가가 종이에 그려진 나무를 그린다면 그 값을 인쇄하고 싶습니다. 그것은 맨 위의 중심에 루트를 가지게 될 것이고, 왼쪽 바로 아래에있는 아이이고, 오른쪽 바로 아래에 오른쪽 아이가 있습니다. 나머지 노드는 그에 따라 그려집니다.

어떻게하면됩니까?

Answer 1

This article는 당신이 필요로하는 코드가 들어 보인다 :

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

편집 :이 사이트는 몇 가지 다른 옵션을 탐험 오프라인

여기 another one 갔다.

Answer 2

음, 단말기에서 힘들어 ... 적합하지 않을 수 있습니다. 그러나 거기에 당신을 위해 멋진 그림을 만들 수있는 그래프 그리기 라이브러리가 있습니다. 가장 인기있는 그래프 바가 있습니다.

편집 : 그래도 텍스트를 인쇄 할 수 없다면 graphvis는 사용자가 그래픽스에 전달할 수있는 마크 업 언어를 사용하여 멋진 그림을 만듭니다.

Answer 3

한 가지 방법은 graphviz를 사용하는 것입니다. 특히 "도트"프로그램을 사용하지만 설명대로 정확하게 출력되도록하는 것은 불가능할 수 있습니다.

Answer 4

여기 대략적인 의사 코드가 있습니다. 기본 아이디어는 각 레이어의 모든 노드를 한 줄에 인쇄하여 레이어별로 트리를 이동하는 것입니다. 각 노드는 그 아래 노드만큼 두 배의 공간으로 분리됩니다. 트리가 모두 일정한 깊이가 아니기 때문에 가상 노드로 인위적으로 패딩되어 노드가없는 빈 공간을 차지합니다.

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 

Answer 5

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