如何打印二进制搜索树的级别

Question

如果我们有一个深度为2:的树

6        <- depth = 0
/ 
/   
4     9     <- depth = 1
/      
3   5     10  <- depth = 2

我只想打印第二层，所以3、5和10(按顺序(，我该怎么做？我正在使用我为有序遍历编写的代码，但我一直在研究如何跟踪树的深度，并在达到所述深度时进行打印。

void printLevelNodesHelper(MovieNode * curr, int level){ //helper function
int lvl = level; //store initial value of level
if(curr != NULL){
printLevelNodesHelper(curr->left, level+1); 
if(level == lvl){
cout << "Movie: " << curr->title << " " << curr->rating << endl;
} 
printLevelNodesHelper(curr->right, level+1);
}
}
void MovieTree::printLevelNodes(int k){ //k is the desired level
MovieNode * curr = root;
if(root == NULL){ //if the tree is empty exit it
return;
}
else if(k == 0){ //print the root's title
cout << "Movie: " << curr->title << " " << curr->rating << endl;
}
else{
printLevelNodesHelper(curr, k);
}
}

这是我的结构和类的信息

struct MovieNode{
int ranking;
string title;
int year;
float rating;
MovieNode* left = NULL;
MovieNode* right = NULL;
};
class MovieTree{
private:
MovieNode* root;
public:
MovieTree();
~MovieTree();
void printMovieInventory();
void addMovieNode(int ranking, std::string title, int year, float rating);
void findMovie(std::string title);
void queryMovies(float rating, int year);
void averageRating();
void printLevelNodes(int k);
};

Answer 1

一些问题：

• 由于对printLevelNodesHelper的初始调用获得了所需的级别作为参数，因此使用level+1进行递归调用是没有意义的。想一想：当你复发时，你实际上在树上下降，距离所需的水平越来越近，所以你不应该增加到该水平的距离，而是减少距离。所以你应该通过level-1

• 在printLevelNodesHelper中，if条件level == lvl始终为真，因为这两个局部变量都不会改变值。从前面的观点来看，我们保证最终会得到level等于0的调用，我们应该检查level == 0(因此您不需要lvl变量(。

代码：

void printLevelNodesHelper(MovieNode * curr, int level) {
if (curr != NULL) {
printLevelNodesHelper(curr->left, level - 1); 
if (level == 0) {
cout << "Movie: " << curr->title << " " << curr->rating << endl;
} 
printLevelNodesHelper(curr->right, level - 1);
}
}

有了这个变化，MovieTree::printLevelNodes的代码就不需要处理root == NULL或k == 0的边界情况。这两者都在上面的helper函数中得到了很好的管理。另一方面，您可能希望添加一些保护，以防在printLevelNodes被调用时使用负值k:时出现无限递归

void MovieTree::printLevelNodes(int k) {
if (k >= 0) printLevelNodesHelper(root, k);
}