如何在控制檯中正確顯示二叉搜索樹？

Question

我試圖在控制檯中顯示BST。這是我的代碼（這是代碼的修改版本在這裏找到：Printing Level Order Binary Search Tree Formatting）：

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

例如結果應該是這樣的：

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

但取而代之的則是：

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

如果我沒有正確的放置，當程序將它放到空葉子時，遞歸會停止，因此在結果中較低的層次上缺少「 - 」。但是我怎麼知道我應該在底層畫多少呢？如何使這項工作？

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

注：I 「突出」 和 「意見」 經修改的線。

現在，樹打印正確。

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

這是我的代碼。它打印得非常好，也許它不完美對稱。 小描述：

• 第一功能 - 通過水平打印水平（根LV - >葉LV）
• 第二功能 - 從新線
• 第三函數的開始距離 - 打印節點並計算之間的距離兩張印刷品;

---

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 

輸出：https://i.stack.imgur.com/TtPXY.png