我正在尝试在控制台中显示 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 - - -
如果我理解正确,当程序到达空叶子时递归停止,因此结果中的较低级别缺少“ - ”。但是我怎么知道我应该在较低的层次上画多少呢?如何使这项工作?