0
\$\begingroup\$

I have written a simple binary tree using structures and a couple of functions in order to add, search, find the minimum and maximum values, remove a node as well as destroy the node, the problem is that I have been using recursion and dealing with it in the same way and I am having a hard time trying to comprehend if my function for sorting the algorithm is efficient enough.

The whole code is:

#include<iostream>
using namespace std;

/*
  This is a very simple example demonstrating a very basic binary tree to be
  implemented using structurs, later on I would like to create this by using
  classes, but for now, structures and pointers would suffice
*/


/*
 * The node is created in here, notice how the pointer has the ability to
 * self reference to 2 different positions, this means that there is the ability
 * to store to 2 different branches of memory
 *
 */

struct node{
  int key_value;
  node * p_left;
  node * p_right;
};

/*
 *
 * This is the creation of the add function that will add to the linked list
 *
 */

node* add(node * p_tree, int key) {
  //--The base case of the recursive function will be placed in here
  //--since binary trees are recursive in nature and linked data structures
  //--are as a whole in terms of space and memory, the recursive function will
  //--suffice for most cases involving binary trees.
  //--In this case, if the given parameter is null, we create the tree
  //--by allocating the necessary memory space
  if (p_tree == NULL) {
    node * pnew_tree = new node;
    pnew_tree->p_left = NULL;
    pnew_tree->p_right = NULL;
    pnew_tree->key_value = key;
    return pnew_tree;
  }// end of base case

  //--Depending of the value of the node, we determine if we will add to the left side or the right side of the subtree
  if (key < p_tree->key_value){
    // if it is less than the value, we add to the left
    p_tree->p_left = add(p_tree->p_left, key);
  }
  else{
    p_tree->p_right = add(p_tree->p_right, key);
  }
  return p_tree;
} // end of function


/*
 *
 * This is where the search function will be created
 * in here the function will go over all the subtrees untill the one with the necessary key is returned
 * again, this uses recursive functions doing things step by step:
 *
 * First: Look to see if the given tree node is empty(NULL) if yes then return NULL
 *
 * Second: If we find the key by referencing the key value, then we are done and return that particular tree
 *
 * Third: Otherwise, look into the left and right sides of the tree making recursive calls to this very same function until
 *        the one that we are looking for is found.
 *
 */

node* search(node *p_tree, int key) {
  //--First:
  if (p_tree == NULL) { return NULL; }

  //--Second:
  else if (p_tree->key_value == key) { return p_tree; }

  //--Third:
  else if(key < p_tree->key_value) {
    search(p_tree->p_left, key); //--Thus it looks into the left with the same recursive algorithm
  }
  else {
    search(p_tree->p_right, key);
  }
}//--End of recursive search function

/*
 *
 * Easiest function to implement, since the delete key is used being that the whole concept falls inside memory being allocated to the
 * list via the creation of new nodes(this means using the new keyword to allocate memory, much like creating new objects in other languages)
 *
 * First: Check to see if passed tree is not null, if not null destroy the left and right subtree using the same function
 *        else nothing.
 *
 * NOTE: The return value is set to void since it returns nothing back to the list
 *
 */
void destroy_node(node* p_tree) {
  //--First
  if (p_tree != NULL) {
    destroy_node(p_tree->p_left);
    destroy_node(p_tree->p_right);
    cout << endl;
    cout << "Destroying left subtree node" << endl;
    cout << "Destroying right subtree node" << endl;
    cout << "Deleting the entire node: " << p_tree->key_value << endl;
    cout << endl;
    delete p_tree;
  }
}//--End of recursive destroy function



/*
 *
 * Finding the max value is simple, we evaluate the left and right node and use base cases to see which node to return
 * Why just right?
 * looking back at the theory behind binary trees, the tree on the right is always the biggest element. That is how trees are normally sorted.
 * there is no need to look at the keys, the code will sort out by itself in this space since if it is not null it will return the highest.
 */
node* return_max(node* p_tree) {
  if (p_tree == NULL) {
    return NULL;
  }
  if (p_tree->p_right == NULL) {
    return p_tree;
  }
  return return_max(p_tree->p_right);
} //--End of return max recursive function


/*
 *
 * Max node, basically the opposite of the avobe taking advantage of the fact that the left node is lesser
 * recursion will be used again
 *
 */

node* return_min(node* p_tree){
  if (p_tree == NULL) {
    return NULL;
  }
  if(p_tree->p_left == NULL) {
    return p_tree;
  }
  return return_min(p_tree->p_left);
}//--End of recursive return min function

/*
 *
 * We need a remove max function in order to properly remove the biggest node in case it is found, that way we can implement a recursive
 * algorithm inside the  function in charge of removing the node we want, we can simply remove the node by using delete or destroy once we
 * find it because that would only destroy the entire tree! No no, that is not good.
 *
 */
node* remove_max_node(node* p_tree, node* p_max_node) {
  if (p_tree == NULL) { return NULL;}

  if (p_tree == p_max_node) {
    return p_max_node->p_left; //--Because the left one is lesser
  }
  //--Now for the recursive call, implementing this means that we will remove from the node on the right
  //--basing us on the sense that the right tree is the highest one, it will go then from top to bottom
  p_tree->p_right = remove_max_node(p_tree->p_right, p_max_node);
  //--return the tree after the changes in the addresses have been conducted properly
  return p_tree;

}




/*
 *
 *
 *
 *
 * Removing from a tree is also simple based on the recursive nature of the element being discussed
 *
 * First: Check to see if the tree is null, if yess, return null
 *
 */
node* removeN(node* p_tree, int key) {
  //--First:
  if (p_tree == NULL) { return NULL;}
  //--Second
  if(p_tree->key_value == key) {
    //--Third:
    if (p_tree->p_left == NULL) {
      node* p_right_sub = p_tree->p_right;
      delete p_tree;
      return p_right_sub;
    }
    if (p_tree->p_right == NULL) {
      node* p_left_sub = p_tree->p_left;
      delete p_tree;
      return p_left_sub;
    }

    node* p_maxN = return_max(p_tree->p_left);
    p_maxN->p_left = remove_max_node(p_tree->p_left, p_maxN);
    p_maxN->p_right = p_tree->p_right;
    delete p_tree;
    return p_maxN;
  }
  else if(key < p_tree->key_value) {
    p_tree->p_left = removeN(p_tree->p_left, key);
  }
  else {
    p_tree->p_right = removeN(p_tree->p_right, key);
  }
  //--After all  changes have been done
  return p_tree;
}

/*
 *
 * The entire implementation is sorted when calling return min and max
 *
 *
 */
 node* sortedN(node* p_tree){
  if (p_tree == NULL){return NULL;}

  return sortedN(return_max(p_tree));
 }





int main(int argv, char* []){

  cout << "This is merely a test" << endl;
  node myBinaryTree = {1};

  add(&myBinaryTree, 2);

  if(search(&myBinaryTree,2)) {cout << "Node found" << endl;}
  return 0;
}

My understanding is that the way I defined the other functions originally already sort and return the state of the node itself in a new way being that I am using pointers. Maybe I am wrong to think that my sorting function works. I have been with this all day and cannot think of a better way, most of my code was written for the understanding I have in it and the help of my books, my instructor is not being much help as well so I came here seeking some wisdom. (Originally posted in stack overflow but moved over here due to it working properly and only asking for a review and better implementation of the last algorithm)

\$\endgroup\$
2
\$\begingroup\$

Bugs

In this line of your search function (in a previous version of the post, before the fix):

else if (p_tree->key_value = key) { return p_tree; }

you used = when you meant to use ==. You should always turn on full compiler warnings to help find errors like this.

In this line of the same function:

search(p_tree->p_left, key);

you forgot to use return as in:

 return search(p_tree->p_left, key);

Again, compiler warnings would have alerted you to this error.

Infinite recursion

I'm not sure what sortedN() is supposed to do since your binary tree is already sorted. But what it actually does is recurse infinitely.

\$\endgroup\$
  • \$\begingroup\$ ah thank you, the bug had been corrected. I had thought the same regarding the sortedN() function, I already had in my head that the algorithm was already sorted in the proper way by the implementation of the additional nodes being added to the list, I just was not sure enough about it. Any other suggestions would be greatly appreciated. \$\endgroup\$ – Alex_adl04 Sep 30 '15 at 4:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.