如何打印二叉搜索树的级别？

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

这是我的结构和 class

的信息

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 总是为真，因为这两个 local变量永远改变价值。从上一点开始，我们保证最终我们会收到 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 的边界情况。这两个都在上面的辅助函数中得到了很好的管理。另一方面，如果使用 k:

的负值调用 printLevelNodes ，您可能希望添加一些保护措施以防止无限递归发生

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

如何打印二叉搜索树的级别？

How to print a level of a binary search tree?

c++

tree

binary-search-tree

data-structures