I have the code for range search in a BST:

#include<bits/stdc  .h>
using namespace std;
class node{
   public:
      int data;
      node *left;
      node *right;
};
void nodesInRange(node *root, int k1, int k2){
   if ( NULL == root )
      return;
   if ( k1 < root->data )
      nodesInRange(root->left, k1, k2);
   if ( k1 <= root->data && k2 >= root->data )
      cout<<root->data<<",";
   if ( k2 > root->data )
      nodesInRange(root->right, k1, k2);
}
node* insert(int data){
   node *temp = new node();
   temp->data = data;
   temp->left = NULL;
   temp->right = NULL;
   return temp;
}
int main(){
   node *root = new node();
   int k1 = 12, k2 = 25;
   root = insert(20);
   root->left = insert(10);
   root->right = insert(24);
   root->left->left = insert(8);
   root->left->right = insert(15);
   root->right->right = insert(32);
   cout<<”The values of node within the range are\t”;
   nodesInRange(root, k1, k2);
   return 0;
}

The codecout<<root->data<<","; result 15,20,24, But I want to print 15,20,24, how do I do that?

I've tried using string.erase() or insert comma before each entry except the first, but they don't work in this case and they would just remove all commas in the result like 152024.

CodePudding user response：

You could let nodesInRange take a parameter that tells it if there's been any output prior to the call. As soon as there's been any output, the state will be passed on to the subsequent calls.

Example:

bool nodesInRange(node *root, int k1, int k2, bool got_output = false) {    
    if (root) {
        if (k1 < root->data)
            got_output = nodesInRange(root->left, k1, k2, got_output);

        if (k1 <= root->data && k2 >= root->data) {
            // only print a comma if there's been some output prior to this
            if(got_output) std::cout << ", ";
            else got_output = true;

            std::cout << root->data;            
        }

        if (k2 > root->data)
            got_output = nodesInRange(root->right, k1, k2, got_output);
    }
    return got_output;
}

Demo

CodePudding user response：

IMO best approach is to generalize code. Separate iteration from IO operation.

void forEachInRange(node* root, int k1, int k2, std::function<void(int data)> f)
{
   if ( NULL == root )
      return;
   if ( k1 < root->data )
      forEachInRange(root->left, k1, k2, f);
   if ( k1 <= root->data && k2 >= root->data )
      f(root->data);
   if ( k2 > root->data )
      forEachInRange(root->right, k1, k2, f);
}

Then handling separator becomes quite trivial:

void printInRange(node* root, int k1, int k2)
{
    std::string sep;
    forEachInRange(root, k1, k2, [&sep](int data) {
        std::cout << sep << data; 
        sep = ",";
    });
}

https://godbolt.org/z/qed1ndeed

CodePudding user response：

You have two options.

1. Change the logic of your output functions to omit the trailing ',' for the last element (e.g. if the right member has no members).
2. Or do not write the output directly to std::cout but to std::ostringstream. Then create a std::string_view that excludes the last character of std::ostringstream::str(). Output that view to std::cout.

Option 1 requires some careful thinking, while option 2 is fairly simple and straightforward to implement but at the cost of requiring additional memory and time to run.