콘솔에 바이너리 검색 트리를 올바르게 표시하는 방법은 무엇입니까?

Question

콘솔에 BST를 표시하려고합니다. 예를 들어, 결과에 대한

string printLevel(node *root, int level, string gap) { 
    if (!root) { 
    return gap + "-" + gap; 
    } 
    if (level==1) { 
    stringstream out; 
    out<<root->value; 
    return gap + out.str() + gap; 
    } else if (level>1) { 
    string leftStr = printLevel(root->left, level-1, gap); 
    string rightStr = printLevel(root->right, level-1, gap); 
    return leftStr + " " + rightStr; 
    } else return ""; 
} 

void printLevelOrder (node* root, int depth) { 
    for (int i=1; i<=depth; i++) { 
    string gap=""; 
    for (int j=0; j<pow(2,depth-i)-1; j++) { 
     gap+=" "; 
    } 
    string levelNodes = printLevel(root, i, gap); 
    cout<<levelNodes<<endl; 
    } 
} 

는 것과 같아야합니다 : 내 코드입니다 (: Printing Level Order Binary Search Tree Formatting는 여기에서 찾을 코드의 수정 된 버전입니다)

 4 
    1  6 
- 2 5 - 
- - - 3 - - - - 

그러나 대신은 다음과 같습니다

 4  
    1  6 
- 2 5 - 
- - 3 - - - 

만약 내가 undestand 올바르게, 프로그램이 빈 잎으로 만들고 따라서 거기에 부족한 "-"결과의 하위 수준에 재귀가 중지됩니다. 그러나 내가 하위 수준에서 얼마나 많이 끌어들이는지 어떻게 알 수 있습니까? 이 작품을 만드는 방법?

Answer 1

브라우저에서 디버거를 실행 한 이후로 어디서 오류가 발생했는지 확인할 수있는 코드를 설치하면 here을 볼 수 있습니다.

string printLevel(node *root, int level, string gap) { 
    if (root == 0) { 
    cout << ".. printLevel - " << root << ": " << gap << "-" << gap << "\n"; 
    return gap + "-" + gap; 
    } 
    if (level==1) { 
    stringstream out; 
    out<<root->value; 
    cout << ".. printLevel - " << root << ": " << gap << root->value << gap << "\n"; 
    return gap + out.str() + gap; 
    } else if (level>1) { 
    string leftStr = printLevel(root->left, level-1, gap); 
    string rightStr = printLevel(root->right, level-1, gap); 

    cout << ".. printLevel - " << root << ": '" << leftStr << "', '" << rightStr << "'\n"; 
    return leftStr + " " + rightStr; 
    } else return ""; 
} 

그리고 여기에 흥미로운 출력의 비트는 다음과 같습니다 : 재생 기능은

.. printLevel - <none>: - 
.. printLevel - <none>: - 
.. printLevel - { 3, <none>, <none> }: 3 
.. printLevel - { 2, <none>, { 3, <none>, <none> } }: '-', '3' 
.. printLevel - { 1, <none>, { 2, <none>, { 3, <none>, <none> } } }: '-', '- 3' 

그래서, 문제는 단락마다 root 실제로 문제가되는, 0 점이다 : -level이 1이 아니면 올바른 출력이 아닙니다.

root이 0이고 root이 0이 아닌 유일한 차이점은 값을 읽을 수 없다는 것입니다 (따라서 -으로 바꿀 수 있음). 그러나 level이 1 일 때 해당 값을 실제로 읽는 것입니다 (주의 : left 또는 right도 읽으려고 할 수 있음). 따라서 level == 1 분기에 있지 않으면 root == 0을 테스트 할 이유가 없습니다.

것은 우리가 약간 그러면 모든 일의 순서를 보자 :

string printLevel(node *root, int level, string gap) { 
    if (level==1) { 
// if (root == 0) { 
//  cout << ".. printLevel - " << root << ": " << gap << "-" << gap << "\n"; 
//  return gap + "-" + gap; 
// } 
    stringstream out; 
    out<<root->value; 
    cout << ".. printLevel - " << root << ": " << gap << root->value << gap << "\n"; 
    return gap + out.str() + gap; 
    } else if (level>1) { 
// string leftStr = printLevel(root ? root->left : 0, level-1, gap); 
// string rightStr = printLevel(root ? root->right : 0, level-1, gap); 

    cout << ".. printLevel - " << root << ": '" << leftStr << "', '" << rightStr << "'\n"; 
    return leftStr + " " + rightStr; 
    } else return ""; 
} 

참고 : 나는 "코멘트"로 수정 된 라인을 "강조".

이제 나무가 제대로 인쇄됩니다.

Answer 2

void BinaryTree::Display(TreeNode *current, int indent) 
{ 
    if (current != nullptr) 
    { 
     Display(current->left, indent + 4); 
     if (indent > 0) 
      cout << setw(indent) << " "; 
     cout << current->value << endl; 
     Display(current->right, indent + 4); 
    } 
} 

은 위에서 아래로 왼쪽에서 오른쪽으로 트리를 인쇄합니다.

  1 
     2 
    3 
     4 
5 
     6 
    7 
      8 
     12 
      18 

Answer 3

여기 내 코드입니다. 그것은 매우 잘 인쇄됩니다, 아마도 완벽하게 대칭이 아닐 수도 있습니다. 작은 설명 :

• 1 기능 - 레벨 별 인쇄 수준 (루트 LV -> 잎 정맥 주사)
• 2 기능 - 새로운 라인
• 3 함수의 시작으로부터의 거리 - 인쇄 노드 사이의 거리를 계산 두 권의 지문;

---

void Tree::TREEPRINT() 
{ 
    int i = 0; 
    while (i <= treeHeight(getroot())){ 
     printlv(i); 
     i++; 
     cout << endl; 
    } 
} 

void Tree::printlv(int n){ 
    Node* temp = getroot(); 
    int val = pow(2, treeHeight(root) -n+2); 
    cout << setw(val) << ""; 
    prinlv(temp, n, val); 
} 

void Tree::dispLV(Node*p, int lv, int d) 
{ 
    int disp = 2 * d; 
    if (lv == 0){ 
     if (p == NULL){ 

      cout << " x "; 
      cout << setw(disp -3) << ""; 
      return; 
     } 
     else{ 
      int result = ((p->key <= 1) ? 1 : log10(p->key) + 1); 
      cout << " " << p->key << " "; 
      cout << setw(disp - result-2) << ""; 
     } 
    } 
    else 
    { 
     if (p == NULL&& lv >= 1){ 
      dispLV(NULL, lv - 1, d); 
      dispLV(NULL, lv - 1, d); 
     } 
     else{ 
      dispLV(p->left, lv - 1, d); 
      dispLV(p->right, lv - 1, d); 
     } 
    } 
} 

입력 :

이

50-28-19-30-29-17-42-200-160-170-180-240-44-26-27 

출력 : 당신은 또한`3`이 표시되는 위치에 문제가 https://i.stack.imgur.com/TtPXY.png