如何在控制台中正确显示二叉搜索树？

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