Binary Search Trees! Simple Class in C++

By K4Paul 0 Development , , , , , , , ,

Here is a really basic binary tree class, it just includes the basics of creating, inserting, erasing, and returning size. In later posts I will talk about printing and traversals.

This class also uses the Node.h talked about in this earlier post. You’ll notice that I really like to use recursion, I think this is cleaner than looping.

#include <assert.h>
#include "Node.h"
using namespace std;

class Bst
{
    public:

        //constructor for when a head Node is provided and when it is not
        Bst() {
            root = nullptr;
        }

        Bst(Node *np) {
            root = np;
        }

        //destroy the tree, we need to go through and destroy each node
        ~Bst() {
            destroyTree(root);
        }

        //get the number of nodes in the tree
        int size() {
            return size(root);
        }

        //erase a value in the tree
        void erase(int item) {
            erase(item, root);
        }

        //insert a Node in the tree
        void insert(int item) {
            insert(item, root);
        }

    private:

        Node* root;

        //Go through each branch and recursively destroy all Nodes
        void destroyTree(Node*& n) {
            if (n != nullptr) {
                destroyTree(n->left);
                destroyTree(n->right);
                delete n;
            }
        }

        //For each Node return the number of left and right nodes
        //Add it up recursively to get the total size
        int size(Node* n) {
            if (n != nullptr) {
                int left = size(n->left);
                int right = size(n->right);
                int self = 1;
                return left + self + right;
            }
            return 0;
        }

        //Find the minimum Node value
        Node* findMin(Node* n){
            assert(n != nullptr);
            if (n->left != nullptr) {
                return findMin(n->left);
            }
            return n;
        }

        //this one is a beast
        //look through all the nodes recursively
        //once you find the node value there are numerous cases we need to look for
        //If the current node does not have left and right nodes, just delete it
        //If it does have a left or right node, set the child to the parent
        //If it has both left and right, we need to work some magic. First we find
        //the smallest value and set the node we want to delete to that value (removing it)
        void erase(int item, Node*& n) {
            if (n != nullptr) {
                if (item == n->data) {
                    if (n->right == nullptr && n->left == nullptr) {
                        delete n;
                        n = nullptr;
                    } else if (n->right == nullptr) {
                        Node* temp = n;
                        n = n->left;
                        delete n;
                    } else if (n->left == nullptr){
                        Node* temp = n;
                        n = n->right;
                        delete n;
                    } else {
                        Node *temp = findMin(n->right);
                        n->data = temp->data;
                        erase(item, n->right);
                    }
                } else if (item < n->data) {
                    erase(item, n->left);
                } else {
                    erase(item, n->right);
                } 
            }
        }

        //look through all the nodes
        //insert the node on the correct node, it will be added to the left if the value is less
        //added to the right if the value is greater
        void insert(int item, Node*& n) {
            if (n != nullptr) {
                if (item < n->data) {
                    insert(item, n->left);
                } else {
                    insert(item, n->right);
                }
            } else {
                n = new Node(item);
            }
        }
};

Let me know if you have any improvements or comments!

Reading a File with C++

By K4Paul 0 Development , , , ,

Here is just a simple example of reading a file with iostream. Just follow my comments to understand.

Good luck, sometimes newlines and spaces can mess you up, you may need to utilize an ignore() or something else.

#include <fstream>
#include <iostream> 
using namespace std;

void evaluateFile(string ins); //Do something with the file contents
void readFile(); //Read the file

int main(){
    readFile();
    return EXIT_SUCCESS;
}

void readFile(){
    ifstream input;
    string fileName;
    cout << "What is the full path of file to be read" << endl;
    getline(cin, fileName); //Prompt user for filename, needs to be the fill path
    input.open(fileName); //Open thhe file
    if (input.fail()){ //Fail case
        cout << "Sorry, cannot open file. Quitting now." << endl;
        exit(0);
    }
    while(!input.eof()){ //Read file until the end of file is reached
        string line;
        getline(input, line);
        evaluateFile(line);
    }
    input.close();
}

void evaluateFile(string line){
    cout << line << endl;
    //DO SOMETHING WITH THE FILE INPUT
}

Setting a timer in C++

By K4Paul 0 Development , , , , , ,

I wanted to time some functions to measure performance of different types of functions in order to find what action was optimal. Here is my code for measuring the time of a C++ action.

Basically, you collect a start clock() and a end clock() then find the total time it took to perform something by taking the difference between the two. By default the clock() function uses the CLOCKS_PER_SEC variable to convert the found clocks to seconds. My code shows how to get the result in seconds and Microseconds.

Happy Coding!

#include <time.h> //Need this for clock()

int main() {
    int seconds_to_micro = 1000000; //conversion from seconds to microseconds var 
    
    clock_t start = clock(); //Get starting point clock
    
    //***********PERFORM AN ACTION HERE********
    
    clock_t end = clock(); //Get ending point clock
    
    float time_in_seconds = static_cast<float>(end - start)/ CLOCKS_PER_SEC //in seconds
    float time_in_microseconds = static_cast<float>(end - start)/ CLOCKS_PER_SEC * seconds_to_micro; //in microseconds
    
    return;
}

Intermediate and Advanced Software Carpentry in Python

By K4Paul 0 Development , , , ,

I am taking a slight break from C++, going back to Python, one of my favorite languages ever! I found the following material on structuring Python code and it is great! Posting it here so I can always come back to it. I recommend it to all the Python enthusiast looking at ways to improve their coding structure.

Intermediate and Advanced Software Carpentry in Python

Welcome! You have stumbled upon the class handouts for a course I taught at Lawrence Livermore National Lab, June 12-June 14, 2007. These notes are intended to accompany my lecture, which was a demonstration of a variety of “intermediate” Python features and packages. Because the demonstration was interactive, these notes are not complete notes of what went on in the course. (Sorry about that; they have been updated from my actual handouts to be more complete…) However, all 70 pages are free to view and print, so enjoy.
Source: ivory.idyll.org/articles/advanced-swc/

Simple List Class in C++

By K4Paul 0 Development , , , , , , , ,

Here is an example of a simple List class I wrote. Follow the comments to understand what is going on. This uses the node structure I wrote about here.

Best of luck!

#include <cstdlib>
#include "Node.h" //Your Node class, see previous post

using namespace std;

class List
    {
        public:
            List(){
                head= NULL;
            }
            ~List(){
                destroyList(head);
            }
            void append(int d){
                head = append(head, d);
            }
            void print(){
                if (head != nullptr)
                print(head);
            }
            void insertInOrder(int d){
                head = insertInOrder(head, d);
            }
            bool findValue (int d){
                return findValue(head, d);
            }
            int getSize(){
                return getSize(head);
            }
    
        private:
            Node *head; //Remember this struct from the previous post

            /* Destroy the list
            * We recursively call the destroy function to cycle through a list to the end.
            * Once the end node is reached, it is deleted. Then as we progress back through
            * our recursive call, each associated node is deleted from the end up.
            * This is called by our destructor to clean everything up.
            */
            void destroyList(Node *n){
                if (n->next != nullptr){
                    destroyList(n->next);
                }
                delete n;
            }

            /* Add a Node to the end of a list
            * Use recursion to cycle through the list to the end
            * Once the end is reached, the next pointer of the last node will by nullptr.
            * A new Node will then be inserted replacing that nullptr and chaining to the list
            */
            Node* append(Node *n, int d){
                if (n == nullptr){
                    return new Node(d);
                }
                else {
                    n->next= append(n->next, d);
                }
                return n;
            }

            /* Print the List
            * Use recursion to loop through and print each Node in a list
            */
            void print(Node *n){
                cout << n->data << endl;
                if (n->next != nullptr){
                    print(n->next);
                }
            }

            /* Insert a Node in Numeric order
            * Loop throug a list using recursion
            * Once the inserting value is less than the current Node
            * we know we need to insert the Node in that position
            * else we keep cycling through
            */
            Node* insertInOrder(Node *n, int d){
                if (n == nullptr){
                    return new Node(d);
                }
                else if (d > n->data){
                    n->next= insertInOrder(n->next, d);
                }
                else {
                    Node* temp = n; //Temp copy
                    n = new Node(d); //Set the pointer to a new Node
                    n->next = temp; //Chain the original onto the new Node's next pointer
                }
                return n;
            }

            /* Find a Node
            * Loop through the enitre list using recursion
            * Return true once the Node value we want is found
            */
            bool findValue(Node *n, int d){
                if (n->data == d){
                    return true;
                }
                else if(n->next != nullptr){
                    return findValue(n->next, d);
                }
                return false;
            }

            /* Get the Size of a List
            * Use recursion to cycle through the list
            * all the while keeping a counter going of each Node encountered
            */
            int getSize(Node *n, int i = 0){
                if (n != nullptr){
                    ++i;
                    return getSize(n->next, i);
                }
                return i;
            }

    };

The typical Node structure in C++

By K4Paul 0 Development , , , , , ,

The next couple of posts are going to require the use of a node object. I’ve seen people make the node way more complicating then it should be as a class. The point of a node is to hold data and be aware of it’s neighbors. All you really need is a simple struct.

In the instance of a stack or list, a node just really needs to know who’s next after them. Note in the code below, to create a node, I need some data passed in, that’s it. It’s up to the coder to set the next pointer in their code that is utilizing the node.

struct Node
{
    int data;
    Node* next;

    Node(int d){
        data = d;
        next = nullptr;
    }
};

When we start looking at linked lists and binary search trees, we might consider a struct that is aware of the nodes on both sides of it. Again, it is up to the code using the node structure to set the left and right pointers to the right node neighbors.

struct Node
{
    int data;
    Node* left;
    Node* right;

    Node(int d){
        data = d;
        left = nullptr;
        right = nullptr;
    }
};

Pretty dang simple!

Sequential Search in C++

By K4Paul 0 Development , , , , , , ,

Okay the sequential search is easier than the recursive and iterative binary searches, I figure I would include it to wrap up searches for now. For the sequential search, you loop through an array (or whatever data structure you are using) checking each position for the search value. Works just as well on sorted array lists as it does on unsorted array lists!

Good luck, let me know if you have questions or improvements!

int sizeOfArray; //size of array, way easy to store it than calculate it everytime
int* array; //contains a list of integers that you will search through

bool sequentialFind(int number){
    for(int i = 0; i < sizeOfArray; i++){
        if (array[i] == number){
            return true;
        }
    }
    return false;
}

Iterative Binary Search in C++

By K4Paul 0 Development , , , , , , ,

So yesterday’s post was on how to do a recursive binary search, today is looking at performing the exact same search on an array but doing it iteratively.  So instead of calling a function over and over and over again, we will use a loop. Again, this search is best on a sorted array.

The search function takes in an integer and will return a bool if the integer was found in a given array. The first thing we do is determine the search range, for the first loop, this will be from start of array to the end of array (0 to the size of the array),

Now we jump into the array, we will keep looping as long as the low bound is less than the high. Once the low bound is greater or equal to the high bound, we know that we exhausted the entire loop and did not find our integer in it.

Just like the recursive search, we find our middle first thing inside the loop. From there, we check if our search value is at that middle position. If not, we determine if the value is less than the middle or greater. If it is less than the middle position, we now know that the search value is in between our low bound and the middle and we can adjust our bounds for the next loop accordingly. If our value is greater than the middle, it is in between the middle and our high bound.

We keep adjusting our bounds and narrowing down the search range in this manner until the number is found or the low bound is no longer less than the high.

Happy programing, let me know if you have any questions or improvements!

int sizeOfArray; //contains the size of the search array
int* array; //integer array that we will search through

bool iterativeBinaryFind(int number){
    int highBound = sizeOfArray;
    int lowBound = 0;
    while (lowBound < highBound){
        int middle = (lowBound + highBound)/2;
        
        if (array[middle] == number) return true;
        else if (array[middle] > number) highBound = middle - 1;
        else lowBound = middle + 1;
    }
    return false;
}

Recursive Binary Search in C++

By K4Paul 0 Development , , , , , , ,

I wrote a recursive binary find that looks through a sorted array for a given number.  (You can use this on an unsorted array, it just isn’t as performant.)

This is how it works, the recursive function call requires the number to search and the lowest and highest positions in a search range. To start, you give the low position, 0, and the high position, the size of the array. This is seen in the first function calling the recursive helper function. Each recursive call, first checks to make sure the low position is actually lower than the high, if it is not, the number was not found in the array. Next, we find the middle of the search section (right now it’s 0 to the size of the array). Let’s say our size is 10, so we determine the middle to be 5.

The if/else statement then works a little magic to determine if the value we have is actually in the array. First we check if the middle position contains the value we want. If it does, return true, we found our number in the array! If not, is the middle position higher than the searching value, if it is make a recursive call to our function, passing the search number, keep the low position bound and pass middle -1 as the high position bound. This is because we know the middle is higher than the search value, so the search value must be between the low and the middle positions. Else, if the two previous conditions are not true, we know the search number must be between the middle and the high position value so we pass the recursive call the search number, middle + 1 and the high value.

This process then recursively repeats itself until it either narrows down the search range and finds the search value or it cycles through and never finds the search value. Below is the code demonstrating this process. Leave comments if you have any questions or improvements.

int sizeOfArray; //size of array
int* array; //contains your array

bool recursiveBinaryFind(int searchNum){
    //pass 0 as the low pasotion and the size of the array as the highest search range position
    return recursiveBinaryFind(searchNum, 0, sizeOfArray);
}

bool recursiveBinaryFind(int searchNum, int lowBound, int highBound){
    //If the low position is greater than the high, quit we looped through everything and didn\'t find our value
    if (lowBound > highBound)    return false;
    
    //Find the middle position
    int middle = (lowBound + highBound)/2;

    //Did we find our value?
    if (array[middle] == searchNum) {
        return true;
    } else if (array[middle] > searchNum) {
        //Search the lower search range half
        return recursiveBinaryFind(searchNum, lowBound, middle - 1);
    } else {
        //Search the higher search range half
        return recursiveBinaryFind(searchNum, middle + 1, highBound);
    }
}

Really cool but obscure command line

By K4Paul 0 Development, Linux , , , , ,

I found this site and just love it. It lists out a lot of obscure commands that can be used on Unix systems, like ledger, a terminal based accounting package! What?!? Check it out!

A little collection of cool unix terminal/console/curses tools Just a list of 20 (now 28) tools for the command line. Some are little-known, some are just too useful to miss, some are pure obscure — I hope you find something useful that you weren’t aware of yet! Use your operating system’s package manager to install most of them.
Source: kkovacs.eu/cool-but-obscure-unix-tools