我正在尝试在控制台中显示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 - - -

如果我没有正确理解,则递归将在程序进入空叶时停止,因此结果的较低级别上缺少“-”。但是,我怎么知道应该从较低的水平吸取多少呢?如何使这项工作?

最佳答案

我对代码进行了检测,以查看错误的位置(由于在浏览器中运行了调试器...),因此您可以实时看到它的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之间的唯一区别是,您无法从中读取值(因此可以用-替换它);但是,只有在level1时,您才真正读取该值(请注意,您也可能尝试读取leftright),因此除非您在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 "";
}

注意:我用“注释”“突出显示”了已修改的行。

现在,树可以正常打印了。

10-05 22:59
查看更多