Linked list functions with dummy head and without it

Some linked list routines need to modify the head node (first node) of the list, if for example the head node is a new node, or the head node needs to be removed. This means that these routines need to modify the pointer to the head node, to point to a different node. In this cases, these routines can either return the new head node pointer, so that the function calling can update it, or get a pointer to the head node pointer, so that they can modify the head node pointer without any problems.

A different approach for this is to use a dummy head, which next pointer points to the head node. In this way the list functions can just pass a pointer to the dummy head, instead of a pointer to the head node pointer.

The following program illustrates both approaches:

#include <stdio.h>
#include <stdlib.h>

struct node {
    struct node *next;
    int value;
};
typedef struct node node_t;

void insert_ordered_dummy(node_t * dummy, int value) {
    node_t * newnode = malloc(sizeof(node_t));
    newnode->value = value;
    newnode->next = NULL;
    if (dummy->next == NULL) {
        dummy->next = newnode;
        return;
    }
    node_t * current = dummy->next;
    node_t * prev = dummy;
    while (current != NULL && current->value < value) {
        prev = current;
        current = current->next;
    }
    prev->next = newnode;
    newnode->next = current;
}

void insert_ordered_nodummy(node_t ** list, int value) {
    node_t * newnode = malloc(sizeof(node_t));
    newnode->next = NULL;
    newnode->value = value;

    // *list->value is equivalent to *(list->value)
    if (*list == NULL || (*list)->value > value) {
        newnode->next = *list;
        *list = newnode;
        return;
    }

    node_t * prev = *list;
    node_t * current = (*list)->next;
    while (current != NULL && current->value < value) {
        prev = current;
        current = current->next;
    }
    prev->next = newnode;
    newnode->next = current;
}
void insertend_nodummy(node_t **head, int value) {
    node_t *newnode = malloc(sizeof(node_t));
    newnode-&amp;gt;value = value;
    newnode-&amp;gt;next = NULL;

    if (*head == NULL) {
        *head = newnode; // if list empty, newnode is head
        return;
    }

    node_t *ptr = *head;
    while (ptr-&amp;gt;next != NULL) { // move ptr to last node
        ptr = ptr-&amp;gt;next;
    }
    ptr-&amp;gt;next = newnode; // insert after last node
}

void insertbeginning_withdummy(node_t *dummyhead, int value) {
    node_t * newnode = malloc(sizeof(node_t));
    newnode-&amp;gt;value = value;
    newnode-&amp;gt;next = dummyhead-&amp;gt;next;
    dummyhead-&amp;gt;next = newnode;  // now dummy head points to new node
}
void insertend_withdummy(node_t *dummyhead, int value) {
    node_t *newnode = malloc(sizeof(node_t));
    newnode-&amp;gt;value = value;
    newnode-&amp;gt;next = NULL;

    if (dummyhead-&amp;gt;next == NULL) {
        dummyhead-&amp;gt;next = newnode;
        return;
    }

    node_t *ptr = head;
    while (ptr-&amp;gt;next != NULL) { // move ptr to last node
        ptr = ptr-&amp;gt;next;
    }
    ptr-&amp;gt;next = newnode; // insert after last node
}

void printlist(node_t *head) {
    node_t *ptr = head;
    while (ptr != NULL) {
        printf(&amp;quot;%d, &amp;quot;, ptr-&amp;gt;value);
        ptr = ptr-&amp;gt;next;
    }
    printf(&amp;quot;\n&amp;quot;);
}

int main() {

    /* without dummy node: the first node is the head. main keeps a pointer
      to the first node (head). If a function needs to modify the head of
      the list (say a new node replaces the head node), then the head pointer
      needs to be modified, which means that a pointer to the head pointer needs
      to be passed to the function. Or otherwise the function could return the
      new head pointer */
    node_t * headptr = NULL; // dont forget NULL!!
    int numbs[] = {1,2,3,4,5};
    int i;
    for (i = 0; i &amp;lt; 5; i++) {
        insertbeginning_nodummy(&amp;amp;headptr, numbs[i]);
        printlist(headptr);
    }
    for (i = 0; i &amp;lt; 5; i++) {
        insertend_nodummy(&amp;amp;headptr, numbs[i]);
        printlist(headptr);
    }


    /* with dummy node: in this case you can just pass pointer to
       dummy head to any function, and the function will be able to
       modify the next pointer in the dummy head. So no need for
       double pointers */
    node_t dummy_head;
    dummy_head.next = NULL;
    dummy_head.value = -1;
    for (i = 0; i &amp;lt; 5; i++) {
        insertbeginning_withdummy(&amp;amp;dummy_head, numbs[i]); // pass ptr to dummy head
        printlist(dummy_head.next);
    }
    for (i = 0; i &amp;lt; 5; i++) {
        insertend_withdummy(&amp;amp;dummy_head, numbs[i]);
        printlist(dummy_head.next);
    }

    return 0;
}



&amp;gt;  gcc linkedlist.c  -g
&amp;gt; ./a.out
1,
2, 1,
3, 2, 1,
4, 3, 2, 1,
5, 4, 3, 2, 1,
5, 4, 3, 2, 1, 1,
5, 4, 3, 2, 1, 1, 2,
5, 4, 3, 2, 1, 1, 2, 3,
5, 4, 3, 2, 1, 1, 2, 3, 4,
5, 4, 3, 2, 1, 1, 2, 3, 4, 5,
1,
2, 1,
3, 2, 1,
4, 3, 2, 1,
5, 4, 3, 2, 1,
5, 4, 3, 2, 1, 1,
5, 4, 3, 2, 1, 1, 2,
5, 4, 3, 2, 1, 1, 2, 3,
5, 4, 3, 2, 1, 1, 2, 3, 4,
5, 4, 3, 2, 1, 1, 2, 3, 4, 5,

Linked List in C++

#include <iostream>
using std::cin;
using std::cout;
using std::endl;

class Node {
    /* friend funtion can access class private data */
    /* friend class' function can access the class private data */
    friend class List; /* List member functions can
                          access Node private data */
    public:
        int getData() const;
        Node(const int &data);
  private:
        int data;
        Node *next;
};

Node::Node(const int &d) :
    data (d), next(0) {
}

int Node::getData() const {
    return data;
}

class List {
    public:
        List();
        ~List();
        List& insertOrder(const int &data);
        bool remove(const int &data);
        bool isEmpty() const;
        void print() const;
    private:
        Node *head;
        Node * allocNode(const int &data);

};

List::List() :
    head (0) {
}

List::~List() {
    if (!isEmpty()) {
        Node *currentptr = head->next;
        Node *tmp;
        while (currentptr != 0) {
            tmp = currentptr;
            currentptr = currentptr->next;
            delete tmp;
        }
    }
}

Node * List::allocNode(const int &data) {
    return new Node(data);
}

List& List::insertOrder(const int &data) {
    Node *newnode = allocNode(data);
    if (isEmpty()) {
        head = newnode;
        return *this;
    }
    Node *current = head->next;
    Node *prev = head;
    while(current != 0) {
        if (current->getData() > data) {
            // insert node
            prev->next = newnode;
            newnode->next = current;
            return *this; // for cascading
        }
        // move forward
        prev = current;
        current = current->next;
    }
    // inserting at end
    prev->next = newnode;
    newnode->next = 0;
    return *this; // for cascading
}

bool List::remove(const int &d) {
    Node *current = head->next;
    Node *prev = head;
    while (current != 0) {
        if (current->getData() == d) {
            prev->next = current->next;
            delete current;
            cout << d << " removed from list" << endl;
            return true;
        }
        prev = current;
        current = current->next;
    }
    cout << "Couldnt remove " << d << " from list" << endl;
    return false;
}

bool List::isEmpty() const {
     return head == 0 ? true : false;
}


void List::print() const {
    if (!isEmpty()) {
        Node *current = head;
        while (current != 0) {
            cout << current->getData() << ", ";
            current = current->next;
        }
    }
    cout << endl;
}

int main() {
    int numbers[] = {1, 4, 7, 2, 3};
    List list;
    list.print();
    for (int i = 0; i < 5; i++) {
        list.insertOrder(numbers[i]).print();
    }
    list.remove(4);
    list.print();

    return 0;
}



g++ cpp_linkedlist.cpp -g
 ./a.out

1,
1, 4,
1, 4, 7,
1, 2, 4, 7,
1, 2, 3, 4, 7,
4 removed from list
1, 2, 3, 7,

reverse linked list

Function to reverse circular single linked list:

struct node {
    void * element;
    struct node *next;
};

typedef struct node node_t;

void reverselist(node_t *head) {
    node_t *current = head->next;
    node_t *prev = head;
    node_t *preprev;
    while (current != head) {
        preprev = prev;
        prev = current;
        current = current->next;

        prev->next = preprev;
    }
    head->next = prev;
}

Function to reverse circular double linked list:

struct node {
    void *element;
    struct node *next;
    struct node *prev;
};
typedef struct node node_t;


void reverse(node_t *head) {
    node_t *ptr = head->next;
    node_t *temp;
    while (ptr != head) {
        temp = ptr->next;

        ptr->next = ptr->prev;
        ptr->prev = temp;

        ptr = temp;
    }
    ptr = head->next;
    head->next = head->prev;
    head->prev = ptr;
}

B-tree

Btrees are usually used for sets of data that are too large to fit into main memory and use on-disk memory. When the data needs to be stored on disk, the number of disk accesses need to be minimized.
For tree structures, a search requires access to data every time a new node is visited. That means that the deeper branches are, the more memory accesses are required. An M-tree is a like a binary tree, but instead of two children per node, it can have M children. This means, that in the same way binary trees have one key per node (2-1), M-trees have M-1 keys per node. Binary trees have in the best case log2 N average branch length, while M-trees have logM N. This cuts down the number of access to disk to memory.
An Mtree that is not balanced could degenerate into a Binary tree and lose its property of shorter branches. To avoid that, a Btree is basically a balanced Mtree, which means it is an Mtree where all leaves have the same height.

/****************************************************/                                        
/* Using a Btree structure, read numbers from an    */
/* input file and form a tree. All keys in the nodes*/
/* of the left subtree will be lower than parent key*/
/* and all keys in the right subtree are higher     */
/* than the right subtree. Traverse the tree in     */
/* order after each split. Print the input values   */
/* and the output node key values in order to       */
/* output files                                     */
/* The display and                                  */
/* traverse functions are designed recursively      */
/* to simplify the design                           */
/****************************************************/


/* Preprocessor directives */
#include<stdio.h>
#include <stdlib.h>
#define M 5
#define FILENAME "input.txt"
#define FILEOUT "output.txt"

/* global variables */
struct node{
    int n;             /* number of keys in node */
    int keys[M-1];     /* array of keys */
    struct node *p[M]; /* pointers to children */
};
/* using enumeration for key status */
enum KeyStatus { Duplicate, SearchFailure, Success, InsertIt, LessKeys}; 
typedef struct node NODE;
NODE* root = NULL; /* defining tree's root as global */
FILE *fdout;

/* function prototypes */
void insert(int );
void display(NODE *, int, int);
enum KeyStatus insertHelper(NODE *, int , int *, NODE** );
int searchPos(int x, int *key_arr, int n);
void traverse(NODE *);


/* main function */
int main()
{
    int key;
    /* opening files */
    printf("Opening files %s and %s.\n", FILENAME, FILEOUT);
    FILE *fd = fopen(FILENAME, "r");
    fdout = fopen(FILEOUT, "w");
    if (fd == NULL || fdout == NULL)
    {
         perror("Could not open file");
         return -1;
    }
    /* reading input sequence */
    fscanf (fd, "%d, ", &key);
    fprintf(fdout, "Adding the following elements to tree as read from file %s:\n\n", FILENAME);
    while (fscanf (fd, "%d, ", &key) != EOF)
    {
        fprintf(fdout, "Adding key %d\n", key);
        /* insert key */
        insert(key); 
        fprintf(fdout, "Tree with new key:\n");
        /* display tree */
        display(root, 0, 0);
        fprintf(fdout, "\n");
        fprintf(fdout, "Traversing tree inorder:\n");
        /* traverse tree inorder */
        traverse(root);
        fprintf(fdout, "\n\n");
    }
    close(fd);
    close(fdout);

    printf("Sequence has been read from %s, and output written to %s\n", FILENAME, FILEOUT);

    return 0;
}/* end of main()*/

void insert(int key)
{
    struct node *newnode;
    int upKey;
    enum KeyStatus value;
    value = insertHelper(root, key, &upKey, &newnode); /* returns the key status, upkey, and newnode */
    if (value == Duplicate)
        fprintf(fdout, "Key is already in tree\n");
    if (value == InsertIt)
    {
        struct node *uproot = root;
        root=malloc(sizeof(struct node));
        root->n = 1;
        root->keys[0] = upKey;
        root->p[0] = uproot;
        root->p[1] = newnode;
    }/* end of if */
}/* end of insert()*/

enum KeyStatus insertHelper(struct node *ptr, int key, int *upKey, struct node **newnode)
{
    struct node *newPtr, *lastPtr;
    int pos, i, n, splitPos;
    int newKey, lastKey;
    enum KeyStatus value;
    /* inserting in root */
    if (ptr == NULL)
    {
        *newnode = NULL;
        *upKey = key;
        return InsertIt;
    }
    n = ptr->n; /* number of keys in node */
    pos = searchPos(key, ptr->keys, n); /* checking where to insert key in node */
    /* key is duplicate */
    if (pos < n && key == ptr->keys[pos])
        return Duplicate;
    value = insertHelper(ptr->p[pos], key, &newKey, &newPtr);
    if (value != InsertIt)
        return value;
    /*If keys in node is less than M (number of keys in node)*/
    if (n < M - 1)
    {
        pos = searchPos(newKey, ptr->keys, n);
        /*Shifting the key and pointer right for inserting the new key*/
        for (i=n; i>pos; i--)
        {
            ptr->keys[i] = ptr->keys[i-1];
            ptr->p[i+1] = ptr->p[i];
        }
        /*Key is inserted at exact location*/
        ptr->keys[pos] = newKey;
        ptr->p[pos+1] = newPtr;
        ++ptr->n; /*incrementing the number of keys in node*/
        return Success;
    }
    /* keys in node greater than M, so splitting is necessary */
    /*If keys in nodes are maximum and position of node to be inserted is last*/
    if (pos == M - 1)
    {
        lastKey = newKey;
        lastPtr = newPtr;
    }
    else /*If keys in node are maximum and position of node to be inserted is not last*/
    {
        lastKey = ptr->keys[M-2];
        lastPtr = ptr->p[M-1];
        for (i=M-2; i>pos; i--)
        {
            ptr->keys[i] = ptr->keys[i-1];
            ptr->p[i+1] = ptr->p[i];
        }
        ptr->keys[pos] = newKey;
        ptr->p[pos+1] = newPtr;
    }
    splitPos = (M - 1)/2;
    (*upKey) = ptr->keys[splitPos];

    (*newnode)=malloc(sizeof(struct node));/* right node after split*/
    ptr->n = splitPos; /* number of keys for left splitted node*/
    (*newnode)->n = M-1-splitPos;/* number of keys for right splitted node*/
    for (i=0; i < (*newnode)->n; i++)
    {
        (*newnode)->p[i] = ptr->p[i + splitPos + 1];
        if(i < (*newnode)->n - 1)
            (*newnode)->keys[i] = ptr->keys[i + splitPos + 1];
        else
            (*newnode)->keys[i] = lastKey;
    }
    (*newnode)->p[(*newnode)->n] = lastPtr;
    fprintf(fdout, "Node has been splitted at key %d\n", ptr->keys[splitPos]);
    return InsertIt;
}/* end of ins() */

void display(struct node *nodeptr, int blanks, int childno)
{
    if (nodeptr)
    {
        int i;
        for(i=1; i<=blanks; i++)
            fprintf(fdout, " ");
        if (childno != 0) 
            fprintf(fdout, "child node %d: ", childno);
        else
            fprintf(fdout, "root node: ");
        for (i=0; i < nodeptr->n; i++)
            fprintf(fdout, "%d ", nodeptr->keys[i]);
        fprintf(fdout, "\n");
        for (i=0; i <= nodeptr->n; i++)
            display(nodeptr->p[i], blanks+5, i+1); /* display child */
    }/* end of if */
}/* end of display() */

void traverse(struct node *nodeptr)
{
    int i;
    if (nodeptr)
    {
        for (i = 0; i < nodeptr->n; i++) // traverse keys and children in node 
        {
            traverse(nodeptr->p[i]);      // print left subtree from key position 
            fprintf(fdout, "%d, ", nodeptr->keys[i]); // print key 
        }
        //i++; //for loop post-increments i, so i is incremented after leaving loop
        traverse(nodeptr->p[i]); // there is one more child pointer than key
    }
} /* end of traverse */

int searchPos(int key, int *key_arr, int n)
{
    int pos=0;
    while (pos < n && key > key_arr[pos])
        pos++;
    return pos;
}/*End of searchPos()*/

The input file for testing was this:

572, 430, 315, 363, 320, 545, 451, 437, 476, 472, 493, 395, 462, 521, 406, 412, 510, 560, 425, 595, 580, 583, 531, 511, 459, 518, 356, 379, 488, 532

The output generated was this:

Adding the following elements to tree as read from file input.txt:

Adding key 430
Tree with new key:
root node: 430 

Traversing tree inorder:
430, 

Adding key 315
Tree with new key:
root node: 315 430 

Traversing tree inorder:
315, 430, 

Adding key 363
Tree with new key:
root node: 315 363 430 

Traversing tree inorder:
315, 363, 430, 

Adding key 320
Tree with new key:
root node: 315 320 363 430 

Traversing tree inorder:
315, 320, 363, 430, 

Adding key 545
Node has been splitted at key 363
Tree with new key:
root node: 363 
     child node 1: 315 320 
     child node 2: 430 545 

Traversing tree inorder:
315, 320, 363, 430, 545, 

Adding key 451
Tree with new key:
root node: 363 
     child node 1: 315 320 
     child node 2: 430 451 545 

Traversing tree inorder:
315, 320, 363, 430, 451, 545, 

Adding key 437
Tree with new key:
root node: 363 
     child node 1: 315 320 
     child node 2: 430 437 451 545 

Traversing tree inorder:
315, 320, 363, 430, 437, 451, 545, 

Adding key 476
Node has been splitted at key 451
Tree with new key:
root node: 363 451 
     child node 1: 315 320 
     child node 2: 430 437 
     child node 3: 476 545 

Traversing tree inorder:
315, 320, 363, 430, 437, 451, 476, 545, 

Adding key 472
Tree with new key:
root node: 363 451 
     child node 1: 315 320 
     child node 2: 430 437 
     child node 3: 472 476 545 

Traversing tree inorder:
315, 320, 363, 430, 437, 451, 472, 476, 545, 

Adding key 493
Tree with new key:
root node: 363 451 
     child node 1: 315 320 
     child node 2: 430 437 
     child node 3: 472 476 493 545 

Traversing tree inorder:
315, 320, 363, 430, 437, 451, 472, 476, 493, 545, 

Adding key 395
Tree with new key:
root node: 363 451 
     child node 1: 315 320 
     child node 2: 395 430 437 
     child node 3: 472 476 493 545 

Traversing tree inorder:
315, 320, 363, 395, 430, 437, 451, 472, 476, 493, 545, 

Adding key 462
Node has been splitted at key 476
Tree with new key:
root node: 363 451 476 
     child node 1: 315 320 
     child node 2: 395 430 437 
     child node 3: 462 472 
     child node 4: 493 545 

Traversing tree inorder:
315, 320, 363, 395, 430, 437, 451, 462, 472, 476, 493, 545, 

Adding key 521
Tree with new key:
root node: 363 451 476 
     child node 1: 315 320 
     child node 2: 395 430 437 
     child node 3: 462 472 
     child node 4: 493 521 545 

Traversing tree inorder:
315, 320, 363, 395, 430, 437, 451, 462, 472, 476, 493, 521, 545, 

Adding key 406
Tree with new key:
root node: 363 451 476 
     child node 1: 315 320 
     child node 2: 395 406 430 437 
     child node 3: 462 472 
     child node 4: 493 521 545 

Traversing tree inorder:
315, 320, 363, 395, 406, 430, 437, 451, 462, 472, 476, 493, 521, 545, 

Adding key 412
Node has been splitted at key 412
Tree with new key:
root node: 363 412 451 476 
     child node 1: 315 320 
     child node 2: 395 406 
     child node 3: 430 437 
     child node 4: 462 472 
     child node 5: 493 521 545 

Traversing tree inorder:
315, 320, 363, 395, 406, 412, 430, 437, 451, 462, 472, 476, 493, 521, 545, 

Adding key 510
Tree with new key:
root node: 363 412 451 476 
     child node 1: 315 320 
     child node 2: 395 406 
     child node 3: 430 437 
     child node 4: 462 472 
     child node 5: 493 510 521 545 

Traversing tree inorder:
315, 320, 363, 395, 406, 412, 430, 437, 451, 462, 472, 476, 493, 510, 521, 545, 

Adding key 560
Node has been splitted at key 521
Node has been splitted at key 451
Tree with new key:
root node: 451 
     child node 1: 363 412 
          child node 1: 315 320 
          child node 2: 395 406 
          child node 3: 430 437 
     child node 2: 476 521 
          child node 1: 462 472 
          child node 2: 493 510 
          child node 3: 545 560 

Traversing tree inorder:
315, 320, 363, 395, 406, 412, 430, 437, 451, 462, 472, 476, 493, 510, 521, 545, 560, 

Adding key 425
Tree with new key:
root node: 451 
     child node 1: 363 412 
          child node 1: 315 320 
          child node 2: 395 406 
          child node 3: 425 430 437 
     child node 2: 476 521 
          child node 1: 462 472 
          child node 2: 493 510 
          child node 3: 545 560 

Traversing tree inorder:
315, 320, 363, 395, 406, 412, 425, 430, 437, 451, 462, 472, 476, 493, 510, 521, 545, 560, 

Adding key 595
Tree with new key:
root node: 451 
     child node 1: 363 412 
          child node 1: 315 320 
          child node 2: 395 406 
          child node 3: 425 430 437 
     child node 2: 476 521 
          child node 1: 462 472 
          child node 2: 493 510 
          child node 3: 545 560 595 

Traversing tree inorder:
315, 320, 363, 395, 406, 412, 425, 430, 437, 451, 462, 472, 476, 493, 510, 521, 545, 560, 595, 

Adding key 580
Tree with new key:
root node: 451 
     child node 1: 363 412 
          child node 1: 315 320 
          child node 2: 395 406 
          child node 3: 425 430 437 
     child node 2: 476 521 
          child node 1: 462 472 
          child node 2: 493 510 
          child node 3: 545 560 580 595 

Traversing tree inorder:
315, 320, 363, 395, 406, 412, 425, 430, 437, 451, 462, 472, 476, 493, 510, 521, 545, 560, 580, 595, 

Adding key 583
Node has been splitted at key 580
Tree with new key:
root node: 451 
     child node 1: 363 412 
          child node 1: 315 320 
          child node 2: 395 406 
          child node 3: 425 430 437 
     child node 2: 476 521 580 
          child node 1: 462 472 
          child node 2: 493 510 
          child node 3: 545 560 
          child node 4: 583 595 

Traversing tree inorder:
315, 320, 363, 395, 406, 412, 425, 430, 437, 451, 462, 472, 476, 493, 510, 521, 545, 560, 580, 583, 595, 

Adding key 531
Tree with new key:
root node: 451 
     child node 1: 363 412 
          child node 1: 315 320 
          child node 2: 395 406 
          child node 3: 425 430 437 
     child node 2: 476 521 580 
          child node 1: 462 472 
          child node 2: 493 510 
          child node 3: 531 545 560 
          child node 4: 583 595 

Traversing tree inorder:
315, 320, 363, 395, 406, 412, 425, 430, 437, 451, 462, 472, 476, 493, 510, 521, 531, 545, 560, 580, 583, 595, 

Adding key 511
Tree with new key:
root node: 451 
     child node 1: 363 412 
          child node 1: 315 320 
          child node 2: 395 406 
          child node 3: 425 430 437 
     child node 2: 476 521 580 
          child node 1: 462 472 
          child node 2: 493 510 511 
          child node 3: 531 545 560 
          child node 4: 583 595 

Traversing tree inorder:
315, 320, 363, 395, 406, 412, 425, 430, 437, 451, 462, 472, 476, 493, 510, 511, 521, 531, 545, 560, 580, 583, 595, 

Adding key 459
Tree with new key:
root node: 451 
     child node 1: 363 412 
          child node 1: 315 320 
          child node 2: 395 406 
          child node 3: 425 430 437 
     child node 2: 476 521 580 
          child node 1: 459 462 472 
          child node 2: 493 510 511 
          child node 3: 531 545 560 
          child node 4: 583 595 

Traversing tree inorder:
315, 320, 363, 395, 406, 412, 425, 430, 437, 451, 459, 462, 472, 476, 493, 510, 511, 521, 531, 545, 560, 580, 583, 595, 

Adding key 518
Tree with new key:
root node: 451 
     child node 1: 363 412 
          child node 1: 315 320 
          child node 2: 395 406 
          child node 3: 425 430 437 
     child node 2: 476 521 580 
          child node 1: 459 462 472 
          child node 2: 493 510 511 518 
          child node 3: 531 545 560 
          child node 4: 583 595 

Traversing tree inorder:
315, 320, 363, 395, 406, 412, 425, 430, 437, 451, 459, 462, 472, 476, 493, 510, 511, 518, 521, 531, 545, 560, 580, 583, 595, 

Adding key 356
Tree with new key:
root node: 451 
     child node 1: 363 412 
          child node 1: 315 320 356 
          child node 2: 395 406 
          child node 3: 425 430 437 
     child node 2: 476 521 580 
          child node 1: 459 462 472 
          child node 2: 493 510 511 518 
          child node 3: 531 545 560 
          child node 4: 583 595 

Traversing tree inorder:
315, 320, 356, 363, 395, 406, 412, 425, 430, 437, 451, 459, 462, 472, 476, 493, 510, 511, 518, 521, 531, 545, 560, 580, 583, 595, 

Adding key 379
Tree with new key:
root node: 451 
     child node 1: 363 412 
          child node 1: 315 320 356 
          child node 2: 379 395 406 
          child node 3: 425 430 437 
     child node 2: 476 521 580 
          child node 1: 459 462 472 
          child node 2: 493 510 511 518 
          child node 3: 531 545 560 
          child node 4: 583 595 

Traversing tree inorder:
315, 320, 356, 363, 379, 395, 406, 412, 425, 430, 437, 451, 459, 462, 472, 476, 493, 510, 511, 518, 521, 531, 545, 560, 580, 583, 595, 

Adding key 488
Node has been splitted at key 510
Tree with new key:
root node: 451 
     child node 1: 363 412 
          child node 1: 315 320 356 
          child node 2: 379 395 406 
          child node 3: 425 430 437 
     child node 2: 476 510 521 580 
          child node 1: 459 462 472 
          child node 2: 488 493 
          child node 3: 511 518 
          child node 4: 531 545 560 
          child node 5: 583 595 

Traversing tree inorder:
315, 320, 356, 363, 379, 395, 406, 412, 425, 430, 437, 451, 459, 462, 472, 476, 488, 493, 510, 511, 518, 521, 531, 545, 560, 580, 583, 595, 

Adding key 532
Tree with new key:
root node: 451 
     child node 1: 363 412 
          child node 1: 315 320 356 
          child node 2: 379 395 406 
          child node 3: 425 430 437 
     child node 2: 476 510 521 580 
          child node 1: 459 462 472 
          child node 2: 488 493 
          child node 3: 511 518 
          child node 4: 531 532 545 560 
          child node 5: 583 595 

Traversing tree inorder:
315, 320, 356, 363, 379, 395, 406, 412, 425, 430, 437, 451, 459, 462, 472, 476, 488, 493, 510, 511, 518, 521, 531, 532, 545, 560, 580, 583, 595, 

References:
http://en.wikipedia.org/wiki/B-tree
yolinux.com/TUTORIALS/C++Enum.html
bluerwhite.org/btree/

Binary Search Tree

The following code implements a BST. For traversing the tree, it uses a stack. The stack file is given in another post.

bst.c =

#include "stack.h" /* function and structures for stack */

struct nodetype {
    int info;
    struct nodetype *left;
    struct nodetype *right;
};
typedef struct nodetype *NODEPTR;
typedef struct nodetype NODE;

void delete_node(NODEPTR *tree, int key)
{
    NODEPTR p;
    p = *tree;
    NODEPTR q = NULL;
    NODEPTR f;
    NODEPTR rp;
    NODEPTR s;

    /* Search for the node with the key key, set p to point to the node and q to its
       parent, if any. */
    while (p != NULL && key != p->info)
    {
        q = p;
        if (key > p->info)
            p = p->right;
        else
            p = p->left;
    }

    if (p == NULL) /* The key does not exists in the tree, leave the tree unchanged */
    {
        printf("Key %d is not in tree\n", key);
        return;
    }
     
    if (p->left == NULL)
        rp = p->left;
    else if (p->right == NULL)
        rp = p->right;
    else
    {
        /* Set rp to the inorder successor of p and f to the parent of rp. */
        f = p;
        rp = p->right;
        s = rp->left; /* s is left child of rp */
        while (s != NULL)
        {
            f = rp;
            rp = s;
            s = rp->left;
        } /* end of while */

        if (f != p) /* at this point, rp is the inorder successor of p */
        {
            f->left = rp->right; /*p is not parent of rp, set it to left(p) */
            rp->right = p->right;
            /* remove node rp and replace */
        } /* end of if (f != p) */
        rp->left = p->left; /* set left child of rp, rp takes place of p */
    } /* end of else */

    /* insert node(rp) into position formerly occupied by node(p) */
    if (q == NULL) // node(p) was the root
       *tree = rp;
    else
    {
        if(p == q->left)
            q->left = rp;
        else 
            q->right = rp;
    }
    free(p);
    printf("node %d deleted\n", key);
    return;
}


void postorder_recursive_traversal(NODEPTR node)
{
    if (node == NULL)
        return;
    else
    {
        postorder_recursive_traversal(node->left);
        postorder_recursive_traversal(node->right);
        printf ("%d, ", node->info); /* visit the node */
    }
}

void postorder_iterative_traversal(NODEPTR node)
{
    /* if node pointer points to null, there is nothing to traverse */
    if (node == NULL)
        return;

    /* initialize stack */
    STACK stack, *pstack;
    stack.top = EMPTYSTACK;
    pstack = &stack;

    push(pstack, node);

    NODEPTR prevNode = NULL;
    NODEPTR currNode;

    /* traverse tree */
    while (empty(pstack) == FALSE)
    {
        currNode = peek(pstack);
        /* go as deep as possible and keep pushing into stack*/
        if (prevNode == NULL || prevNode->left == currNode || prevNode->right == currNode)
        {
            if (currNode->left != NULL) /* go to left */
                push(pstack, currNode->left);
            else if (currNode->right != NULL) /* go to right */
                push(pstack, currNode->right);
        }
        /* got to last left node. keep going to right */
        else if (currNode->left == prevNode) 
        {
            if (currNode->right != NULL)
                push(pstack, currNode->right);
        }
        /* cannot go any deeper. visit node */
        else
        {
             printf ("%d, ", currNode->info); /* visit the node */
             pop(pstack); /* go back to previous node in stack */
        }
        prevNode = currNode;
    }
}      
    

void preorder_recursive_traversal(NODEPTR node)
{
    if (node == NULL)
        return;
    else
    {
        printf ("%d, ", node->info); /* visit the node */
        preorder_recursive_traversal(node->left);
        preorder_recursive_traversal(node->right);
    }
}


void preorder_iterative_traversal(NODEPTR node)
{
    /* initialize stack */
    STACK stack, *pstack;
    stack.top = EMPTYSTACK;
    pstack = &stack;

    while (empty(pstack) == FALSE || node != NULL)
    {
        if (node != NULL)
        {
            push(pstack, node);
            printf ("%d, ", node->info); /* visit the node */
            node = node->left; /* keep going to left */
        }
        /* no more nodes on left. Go back one node and go to right */
        else
        {
            node = pop(pstack);
            node = node->right;
        }
    }
}  

void inorder_recursive_traversal(NODEPTR node)
{
    if (node != NULL)
    {
        inorder_recursive_traversal(node->left); /* traverse the left subtree */
        printf ("%d, ", node->info); /* visit the node */
        inorder_recursive_traversal(node->right); /* traverse the right subtree */
    } 
    return;
} 

void inorder_iterative_traversal(NODEPTR node)
{
    /* initialize stack */
    STACK stack, *pstack;
    stack.top = EMPTYSTACK;
    pstack = &stack;

    while (empty(pstack) == FALSE || node != NULL)
    {
        /* find deepest on left (smallest) */
        if (node != NULL)
        {
            push(pstack, node);
            node = node->left;
        }
        /* if no more nodes on left, go back one node, and go to right */
        else
        {
            node = pop(pstack);
            printf("%d, ", node->info);
            node = node->right;
        }
    }
}


NODEPTR get_treenode ()
{
    NODEPTR p;
    p = (NODEPTR)malloc(sizeof (struct nodetype));
    return (p);
} /* end of getnode function */


NODEPTR maketree (int x)
{
    /* allocates and initializes node */ 
    NODEPTR p;
    p = get_treenode ();
    p->info = x;
    p->left = NULL;
    p->right = NULL;
    return (p);
} /* end of maketree function */

/* inserts node in binary search tree */
void setbintree (NODEPTR p, int x)
{
    NODEPTR s = p;
    /* traverse tree */
    while (s != NULL)
    {
        /* duplicate: BST cannot have duplicates */
        if (s->info == x)
        {
            printf ("skipping %d due to duplicate, ", x);
            return;
        }
        /* go to left */
        if (s->info > x)
        {
            if (s->left == NULL) /* place node here */
            {
                s->left = maketree (x);
                return;
            }
            else /* keep going */
                s = s->left;
        }
        /* go to right */
        else
        {
            if (s->right == NULL) /* place node here */
            {
                s->right = maketree (x);
                return;
            }
            else /* keep going */
                s = s->right;
        }
    } 
    return;
} 

/* find node iteratively */
NODEPTR findbinarysearchtree_iterative(NODEPTR node, int x)
{
    while (node != NULL)
    {
        if (x == node->info) /* node found */
            return node;
        else if (x > node->info) /* go to right */
            node = node->right;
        else if (x < node->info) /* go to left */
            node = node->left;
    }
    return node; /* not found. node will be pointing to NULL */
}

/* find node recursively */
NODEPTR findbinarysearchtree_recursive(NODEPTR node, int x)
{
    if (node == NULL || node->info == x) /* node NULL means it wasnt found */
        return node;
    else
        if (x < node->info)
            return (findbinarysearchtree_recursive(node->left, x)); /* go to left */
        else
            return (findbinarysearchtree_recursive(node->right, x)); /* go to right */
}

The following program uses the implementation above to store numbers read from a file into a BST, and performs some operations on the BST:

/* Preprocessor directives */
#include <stdio.h>
#include <stdlib.h>
#include <string.h> /* for strcmp */
#include "bst.c" /* function and structures for BST */
#define FILENAME "input.txt"
#define FILEOUT "output.txt"

/* main function */
int main()
{
 
    NODEPTR btree = NULL;
    int numb;
    int done = FALSE;
    char input[10];
    NODE *nodefound;
 
    printf("Opening files %s and %s.\n", FILENAME, FILEOUT);
    FILE *fd = fopen(FILENAME, "r");
    fdout = fopen(FILEOUT, "w");
    if (fd == NULL || fdout == NULL)
    {
         perror("Could not open file");
         return -1;
    }

    fscanf (fd, "%d, ", &numb);
    fprintf(fdout, "Making tree with root %d.\n\n", numb);
    btree = maketree (numb);
    fprintf(fdout, "Adding the following elements to tree as read from file %s:\n", FILENAME); 
    while (fscanf (fd, "%d, ", &numb) != EOF)
    {
        fprintf(fdout, "%d, ", numb);
        setbintree (btree, numb);
    } 
    close(fd);

    fprintf (fdout, "\n\ninordered recursive traversal:\n");
    inorder_recursive_traversal(btree);

    fprintf (fdout, "\n\ninordered iterative traversal:\n");
    inorder_iterative_traversal(btree);
 
    fprintf (fdout, "\n\npreordered recursive traversal:\n");
    preorder_recursive_traversal(btree);

    fprintf (fdout, "\n\npreordered iterative traversal:\n");
    preorder_iterative_traversal(btree);

    fprintf (fdout, "\n\npostordered recursive traversal:\n");
    postorder_recursive_traversal(btree);

    fprintf (fdout, "\n\npostordered iterative traversal:\n");
    postorder_iterative_traversal(btree);
    
    done = FALSE;
    printf("Please type number to find and to delete in tree, or 'quit' to quit:");
    fprintf(fdout, "\n\n\nFinding and deleting numbers entered by user:");
    do 
    {
        printf("\n> ");
        scanf("%s", &input);
        if (strcmp(input, "quit") == 0)
            done = TRUE;
        else
        {
            numb = atoi(input);
            if (numb == 0 && strcmp(input, "0")  != 0)
                printf("Could not understand number entered. Please try again.\n");
            else
            {
                fprintf(fdout, "\n\nNumber %d was entered by user\n", numb); 
                fprintf(fdout, "Finding node %d iteratively: ", numb);
                nodefound = findbinarysearchtree_iterative(btree, numb);
                if (nodefound != NULL)
                  fprintf(fdout, "Node %d found in tree\n", nodefound->info);
                else
                  fprintf(fdout, "Node %d not found in tree\n", numb);

                fprintf(fdout, "Finding node %d recursively: ", numb);
                nodefound = findbinarysearchtree_recursive(btree, numb);
                if (nodefound != NULL)
                  fprintf(fdout, "Node %d found in tree\n", nodefound->info);
                else
                  fprintf(fdout, "Node %d not found in tree\n", numb);


                fprintf(fdout, "Deleting node %d: ", numb);
                delete_node(&btree, numb);
                fprintf(fdout, "\nTree after deleting operation: inordered recursive traversal:\n");
                inorder_recursive_traversal(btree);
            }
        }
    } while (done == FALSE);
    
    fprintf(fdout, "\n\nBinary tree after all the deletions: ");
    fprintf (fdout, "inordered recursive traversal:\n");
    inorder_recursive_traversal(btree);

    printf("\nProgram execution completed\n\n");
    return 0;
} 

I used this file with the input numbers:
intput.txt =

55, 62, 89, 85, 97, 56, 71, 82, 38, 49, 25, 67, 58, 92, 100, 44, 69, 72, 65, 52, 41, 84, 21, 60, 95, 12, 35, 42, 105, 99, 34, 47, 35, 79, 95, 50, 25, 51

And this is the output with the program above:

Making tree with root 55.

Adding the following elements to tree as read from file assignment13input.txt:
62, 89, 85, 97, 56, 71, 82, 38, 49, 25, 67, 58, 92, 100, 44, 69, 72, 65, 52, 41, 84, 21, 60, 95, 12, 35, 42, 105, 99, 34, 47, 35, skipping 35 due to duplicate, 79, 95, skipping 95 due to duplicate, 50, 25, skipping 25 due to duplicate, 51, 

inordered recursive traversal:
12, 21, 25, 34, 35, 38, 41, 42, 44, 47, 49, 50, 51, 52, 55, 56, 58, 60, 62, 65, 67, 69, 71, 72, 79, 82, 84, 85, 89, 92, 95, 97, 99, 100, 105, 

inordered iterative traversal:
12, 21, 25, 34, 35, 38, 41, 42, 44, 47, 49, 50, 51, 52, 55, 56, 58, 60, 62, 65, 67, 69, 71, 72, 79, 82, 84, 85, 89, 92, 95, 97, 99, 100, 105, 

preordered recursive traversal:
55, 38, 25, 21, 12, 35, 34, 49, 44, 41, 42, 47, 52, 50, 51, 62, 56, 58, 60, 89, 85, 71, 67, 65, 69, 82, 72, 79, 84, 97, 92, 95, 100, 99, 105, 

preordered iterative traversal:
55, 38, 25, 21, 12, 35, 34, 49, 44, 41, 42, 47, 52, 50, 51, 62, 56, 58, 60, 89, 85, 71, 67, 65, 69, 82, 72, 79, 84, 97, 92, 95, 100, 99, 105, 

postordered recursive traversal:
12, 21, 34, 35, 25, 42, 41, 47, 44, 51, 50, 52, 49, 38, 60, 58, 56, 65, 69, 67, 79, 72, 84, 82, 71, 85, 95, 92, 99, 105, 100, 97, 89, 62, 55, 

postordered iterative traversal:
12, 21, 34, 35, 25, 42, 41, 47, 44, 51, 50, 52, 49, 38, 60, 58, 56, 65, 69, 67, 79, 72, 84, 82, 71, 85, 95, 92, 99, 105, 100, 97, 89, 62, 55, 


Finding and deleting numbers entered by user:

Number 71 was entered by user
Finding node 71 iteratively: Node 71 found in tree
Finding node 71 recursively: Node 71 found in tree
Deleting node 71: node 71 deleted

Tree after deleting operation: inordered recursive traversal:
12, 21, 25, 34, 35, 38, 41, 42, 44, 47, 49, 50, 51, 52, 55, 56, 58, 60, 62, 65, 67, 69, 72, 79, 82, 84, 85, 89, 92, 95, 97, 99, 100, 105, 

Number 51 was entered by user
Finding node 51 iteratively: Node 51 found in tree
Finding node 51 recursively: Node 51 found in tree
Deleting node 51: node 51 deleted

Tree after deleting operation: inordered recursive traversal:
12, 21, 25, 34, 35, 38, 41, 42, 44, 47, 49, 50, 52, 55, 56, 58, 60, 62, 65, 67, 69, 72, 79, 82, 84, 85, 89, 92, 95, 97, 99, 100, 105, 

Reference:

http://en.wikipedia.org/wiki/Binary_search_tree