Jumping into C++ cha 17 number 1 (binary tree and sorting)

[gdz98]

Hi guys I m going trough the Jumping into C++ book and im currently on the binary tree chapter. There s an exercise that tells me to write a code where I can add values to a binary tree list and then show them in a sorted order (lowest->highest). here s the code I got so far

  #include <iostream>

using namespace std;

struct node
{
    int key;
    node* p_left = NULL;
    node* p_right = NULL;
};

node* insert (node* p_tree, int key)
{
    if (p_tree == NULL)
    {
        node* p_new_node = new node;
        p_new_node->key = key;
        p_new_node->p_left = NULL;
        p_new_node->p_right = NULL;
        return p_new_node;
    }
    if (key < p_tree->key)
        insert (p_tree->p_left, key);
    else
        insert (p_tree->p_right, key);
}

node* FindRemaningSmallestValue (node* p_tree)
{
    if (p_tree->p_left == NULL)
    {
        return p_tree;
    }
    FindRemaningSmallestValue(p_tree->p_left);

}

node *Rearranging (node* p_tree, node* smallest_value)
{ while (p_tree != NULL)
   {
      if (smallest_value->p_right != NULL)
      {
          node* right_subtree = smallest_value->p_right;
          cout << smallest_value->key << "  ";
          delete smallest_value;
          return right_subtree;
      }
      else
      {
          delete smallest_value;
          return NULL;
      }
   }
}

int main ()
{
    node* p_tree = NULL;
    int key;
    int input;
    node* smallest_value = NULL;
    cout << "1. Add value" <<endl<<"2. See values in sorted order"<<endl<<"3. Quit"<<endl;
    cin>> input;
    while (input != 3)
    {
      switch (input)
      {
        case 1: cout<< "Enter the value you want to add" << endl;
                cin >> key;
                p_tree = insert (p_tree, key);break;
        case 2: while (p_tree != NULL)
                {
                  smallest_value=FindRemaningSmallestValue(p_tree);
                  cout<<smallest_value->key<<"  ";
                  p_tree = Rearranging(p_tree, smallest_value);
                }break;
      }
      cout << "1. Add value" <<endl<<"2. See values in sorted order"<<endl<<"3. Quit"<<endl;
      cin>>input;
    }



}

I know I could have likely done it in a better way, but anyway let s keep what I have.
The problem is (of course) in the Rearranging function... it doesn't work as it should... any help on that please??

[tpb]

Does the book you're using use NULL? NULL is not used in C++. Use either 0 (old style) or the new nullptr keyword.

You don't need to say endl all over the place. You can use the '\n' character in the string.

Don't prefix variables with p_ just because they're pointers.

insert says it returns a node, but not all paths do that. And the recursive calls ignore the return value.

The whole FindRemainingSmallestValue thing is kind of weird and I don't understand the point of it. It's way easier to print the values in order than that.

#include <iostream>
using namespace std;

struct Node {
    int key;
    Node *left, *right;
    
    Node(int k) : key(k), left(nullptr), right(nullptr) {}
};

Node* insert(Node* tree, int key) {
    if (!tree)
        return new Node(key);
    if (key < tree->key)
        tree->left = insert(tree->left, key);
    else
        tree->right = insert(tree->right, key);
    return tree;
}

void print(Node *tree) {
    if (!tree) return;
    print(tree->left);
    cout << tree->key << '\n';
    print(tree->right);
}

void delete_tree(Node *tree) {
    if (!tree) return;
    delete_tree(tree->left);
    delete_tree(tree->right);
    delete tree;
}

int main () {
    Node* tree = nullptr;

    cout << "1. Add value\n2. See values in sorted order\n3. Quit\n";\
    int input;
    cin >> input;

    while (input != 3) {
        switch (input) {
        case 1:
            cout<< "Enter the value you want to add: ";
            int key;
            cin >> key;
            tree = insert (tree, key);
            break;
        case 2:
            print(tree);
            break;
        }
        cout << "1. Add value\n2. See values in sorted order\n3. Quit\n";
        cin >> input;
    }

    delete_tree(tree);
}

[gdz98]

thanks a lot, you have been great with the print function... you reminded me how to use recursive calls in order to sort something. The only one thing I don t get is your last line of code in that function

[code]

print(tree->right);

[/code]

why would you call the function again on the right? Shouldn it go automatically there once the first recursive call is terminated?

Anyway I ve tried it both the way you ve done and deleting the last line of code of the print function and it doesn t print what it should.... it only prints the highest value :/ ….
Instead if I try to set a pointer to "nullptr" it tells me I need to declare it?! O.o

Regarding this:

    Node(int k) : key(k), left(nullptr), right(nullptr) {}

it s something I either never studied or seen xD
Next chapter is about the Standard Template Library and it may be in there...

[gdz98]

This is what I currently have:

#include <iostream>

using namespace std;

struct node
{
    int key;
    node* p_left = NULL;
    node* p_right = NULL;
};

node* insert (node* p_tree, int key)
{
    if (p_tree == NULL)
    {
        node* p_new_node = new node;
        p_new_node->key = key;
        p_new_node->p_left = NULL;
        p_new_node->p_right = NULL;
        return p_new_node;
    }
    if (key < p_tree->key)
        insert (p_tree->p_left, key);
    else
        insert (p_tree->p_right, key);
}

void print (node* p_tree)
{
    if (p_tree->p_left)
        {
           print (p_tree->p_left);
        }
    cout<< p_tree->key << '\n';

}

int main ()
{
    node* p_tree = NULL;
    int key;
    int input;
    cout << "1. Add value" <<endl<<"2. See values in sorted order"<<endl<<"3. Quit"<<endl;
    cin>> input;
    while (input != 3)
    {
      switch (input)
      {
        case 1: cout<< "Enter the value you want to add" << endl;
                cin >> key;
                p_tree = insert (p_tree, key);break;
        case 2: print (p_tree);
      }
      cout << "1. Add value" <<endl<<"2. See values in sorted order"<<endl<<"3. Quit"<<endl;
      cin>>input;
    }
}

I ve tried to almost totally change the print function but it still only prints the highest value within the ones inserted