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

Question

我想要在控制台中显示一颗二叉搜索树。这是我的代码（这是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 - - -

如果我理解正确，当程序到达空叶子时，递归停止，因此结果的较低级别缺少“-”符号。但是，我如何知道在较低级别上应该画多少个这些符号？如何使其运行？

- raven_raven

---

您还有一个问题，就是 3 的显示位置不正确，应该在 2 的右侧。 - Matthieu M.

@MatthieuM。这实际上与主要问题有关。如果树正确显示，3将会在它的位置上。从数据结构的角度来看，它是2的右子节点。 - raven_raven

Answer 1

这是我的代码。它打印得很好，但可能不是完全对称的。

• 第一个函数 - 按层级打印（从根层到叶子层）
• 第二个函数 - 距离新行开始的距离
• 第三个函数 - 打印节点并计算两个打印之间的距离；

---

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://istack.dev59.com/TtPXY.webp

- almighty Push

Answer 2

我已经对代码进行了仪器化以查看其出错的位置（因为在浏览器中运行调试器...），您可以在这里直接查看。重现的函数如下：

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），因此没有理由测试root == 0，除非您在level == 1分支中。

那么让我们稍微重新排列一下：

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

注意：我用“注释”突出了修改过的行。

现在，树已经正确地打印出来了。

- Matthieu M.

---

现在它完美地运行了！非常感谢您的技巧和代码！如此优雅的解决方案，还要感谢您分享这个liveworkspace链接，教给了我一些技巧。 - raven_raven

@raven_raven：liveworkspace（和其他在线编译器）是一个不错的解决方案，用于快速脏实验，因为我们在C ++中没有REPL...而且分享它非常容易！ - Matthieu M.

Answer 3

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

- RedFox