Cfrtjryk

I started working on an implementation for a BST, just for myself to have some C projects. this is what I've done so far.

tree.h

#include <stdio.h>

#include <stdlib.h>

#include <limits.h>



#ifndef MIN

    #define MIN(X, Y) (((X) > (Y)) ? (X) : (Y))

#endif

#ifndef MAX

    #define MAX(X, Y) (((X) < (Y)) ? (X) : (Y))

#endif



typedef struct Node { /* The tree struct */

    int val; /* The value in the node */

    struct Node *l, *r; /* Pointer to the next nodes, l = left r = right */

} Node;



int minDepth (Node *root);

int maxDepth (Node *root);

void printTree (Node *root);

void printTreeValues (Node *root);

int exist (Node *root, int value);

Node *createNode (int value);

void insertNewNumber (Node **root, int value);

int numberOfElements (Node *root);

int isMaxHeap (Node *root);

int maxElement (Node *root);

int minElement (Node *root);

void freeTree (Node *root);

tree.c

I won't post here the entire code since It's a bit long (I'll delete functions like maxDepth...)

#include "tree.h"



int minDepth (Node *root) /* A recursive function returns the shortests distance from the root node to a leaf */

{

    /* Corner case. Should never be hit unless the code is */

    /* called on root = NULL */

    if (root == NULL)

        return 0;



    /* Base case : Leaf Node. This accounts for height = 1. */

    if (root->l == NULL && root->r == NULL)

       return 1;



    /* If left subtree is NULL, recur for right subtree */

    if (!root->l)

       return minDepth(root->r) + 1;



    /* If right subtree is NULL, recur for left subtree */

    if (!root->r)

       return minDepth(root->l) + 1;



    /* Return the smallest result */

    if (minDepth(root->l) > minDepth(root->r))

        return minDepth(root->r) + 1;

    else if (minDepth(root->l) < minDepth(root->r))

        return minDepth(root->l) + 1;

    else

        return minDepth(root->l) + 1;

}



void printTreeRec (Node *root) { /* A recursive function which prints the tree by given root */

    /* Prints the tree the way it looks */

    if(!root) {

        printf("NULL");

        return; 

    }

    printf("%d (", root->val);

    printTreeRec(root->l);

    printf(",");

    printTreeRec(root->r);

    printf(")");

}

void printTree (Node *root) { /* A recursive function which prints the tree by given root */

    printTreeRec(root);

    printf("n");

}



void printTreeValuesRec (Node *root) {

    /* In this kind of printing if the tree is also sorted the vals will be printed by up going order */

    if(!root) {

        return; 

    }

    printTreeValuesRec(root->l);

    printf("%d->", root->val);

    printTreeValuesRec(root->r);

}

void printTreeValues (Node *root) {

    printTreeValuesRec(root);

    printf("NULLn");

}



int exist (Node *root, int value) { /* A function that checks if a node with the value 'value' is in the tree. Returns 1 if he is -1 if he isn't */

    if (!root)

    {

        return -1;

    }

    if (root->val > value)

    {

        return exist(root->l, value);

    }

    else if (root->val < value)

    {

        return exist(root->r, value);

    }

    return 1;

}



Node *createNode (int value) { /* Creating a new node */

    Node *newNode = (Node*) malloc(sizeof(Node)); 

    if (newNode == NULL)

    {

        fprintf(stderr, "Error allocating memory, Exitingn");

        exit(1);

    }

    newNode->val = value;

    newNode->l = NULL;

    newNode->r = NULL;

    return newNode;

}



void insertNewNumber (Node **root, int value) { /* A function that adds a node to the tree */

    Node *newNode = createNode(value);

    if(!*root) { /* We need to add the number here */

        *root = newNode; 

        return; 

    }

    if ((*root)->val > value) /* (*root)->val is bigger than value so we will go left  */

    {

        insertNewNumber(&(*root)->l, value);

    }

    else if ((*root)->val < value) /* (*root)->val is smaller than value so we will go right  */

    {

        insertNewNumber(&(*root)->r, value);

    }

    else { /* Node with the value value is already exist in the tree */

        free(newNode);

        return;

    }

}



int numberOfElements (Node *root) { /* Count the number of numbers in the tree */

    if (root == NULL)

    {

        return 0;

    }

    else

    {

        return numberOfElements(root->r) + numberOfElements(root->l) + 1;

    }

}



int isMaxHeap (Node *root) { /* Max Heap description http://courses.cs.vt.edu/cs2604/spring02/Notes/C07.Heaps.pdf */

    if (root == NULL)

    {

        return 1;

    }

    else if (root->r != NULL && root->l != NULL)

    {

        if (root->r->val < root->val && root->l->val < root->val) 

        {

            return MIN(isMaxHeap(root->r), isMaxHeap(root->l));

        }

        return -1;

    }

    else if (root->r != NULL)

    {

        if (root->r->val < root->val) 

        {

            return isMaxHeap(root->r);

        }

        return -1;

    }

    else if (root->l != NULL)

    {

        if (root->l->val < root->val) 

        {

            return isMaxHeap(root->l);

        }

        return -1;

    }

    return 1;

}



int minElement (Node *root) {/* A function to find min element in the tree recursively */

    if (root == NULL)

    {

        return INT_MAX;

    }

    else if (root->l != NULL)

    {

        return minElement(root->l);

    }

    else {

        return root->val;

    }

}



void freeTree (Node *root) { /* A function to free the tree recursively */

    if(!root)

        return; 

    freeTree(root->l);

    freeTree(root->r);

    free(root);

}



int main(int argc, char const *argv)

{

    Node *root = createNode(9);



    insertNewNumber(&root,5);

    insertNewNumber(&root,1);

    printf("%dn",isMaxHeap(root));

    printTree(root);

    printTreeValues(root);

    printf("%dn", minElement(root));

    freeTree(root);

    return 0;

}

And finally

Makefile

tree: tree.c

    gcc -Wall -ansi -pedantic tree.c -o tree

clean:

    rm tree

I would like to hear if you have ideas to new functions, how to improve old ones, and please comment if some part of the code isn't clear enough.

Thanks in advance.

You have way overcomplicated minDepth():

/* 

 * A recursive function returns the shortests distance

 * from the root node to a leaf

 */

int minDepth (Node *root)

{

    if (root == NULL) {

        return 0;

    }

    return 1 + MIN(minDepth(root->l), minDepth(root->r));

}

(but see the notes below on the MIN() macro expanding its arguments multiple times)

Your insertNewNumber() leaks very badly. You are creating a new node on each call. But only putting it in the tree at the root.

void insertNewNumber(Node **root, int value)

{

    (*root) = insertNewNumberAtLeaf(*root, value);

}

Node* insertNewNumberAtLeaf(Node *root, int value)

{

     if (root == NULL) {

         return createNode(value);

     }

     if (root->val > value) {

         root->right = insertNewNumberAtLeaf(root->right, value);

     }

     else {

         root->left  = insertNewNumberAtLeaf(root->left,  value);

     }

     return root;

}

I think your definition of MIN and MAX is wrong.

#ifndef MIN

    #define MIN(X, Y) (((X) > (Y)) ? (X) : (Y))

#endif

#ifndef MAX

    #define MAX(X, Y) (((X) < (Y)) ? (X) : (Y))

#endif

Also if they are already defined is it OK to continue? Do you think everybody has the same definition as you? If either of these is already defined I would error out rather than continue.

I would also note that these macros make you call the function multiple times.

Taken from your code:

 return MIN(isMaxHeap(root->r), isMaxHeap(root->l));

This expands to:

 return (((isMaxHeap(root->r)) > (isMaxHeap(root->l))) ? (isMaxHeap(root->r)) : (isMaxHeap(root->l)));

The compiler can't assume the function returns the same value each time (unless it is doing a lot of extra analysis). So this would be equivalent to:

 int tmpL = isMaxHeap(root->r);

 int tmpR = isMaxHeap(root->l);



 // Then call again to get the result.

 int rest = (tmpL > tmpR) ? isMaxHeap(root->r) : isMaxHeap(root->l);

 return rest;

The return value of exist() is strange. I don't know if -1 for false is a convention from some other language, but C treats zero as a false value, and non-zero as true. This is what users expect: the expectation is that a predicate function could be used directly in if or while statements, for example.

There's even a <stdbool.h> header that gives us a bool type with values true and false:

#include <stdbool.h>



bool exist(Node *root, int value);

Next, observe that there's no need for this function to change root, so accept a pointer to const to indicate that intent:

bool exist(const Node *root, int value);

Unfortunately, we can't enforce that the const also applies to interior nodes (as we could in C++), but this declaration does help programmers to understand the function. The same observation applies to a few other methods - in fact, all except insertNewNumber() and freeTree().

My re-written exist() is:

/** @return true if a node with the value 'value' is in the tree,

    otherwise false. */

bool exist(const Node *root, int value)

{

    if (!root) {

        return false;

    }

    if (root->val == value) {

        /* found it */

        return true;

    }

    /* search again in left or right subtree */

    const Node *subtree = root->val < value ? root->l : root->r;

    return exist(subtree, value);

}

We have tail recursion there, but we can't depend on a C compiler to perform tail-call elimination, so we might choose to write it iteratively; for my money, that's also simpler to read and understand:

bool exist(const Node *root, int value)

{

    while (root) {

        if (root->val == value) { return true; }

        root = root->val < value ? root->l : root->r;

    }

}

Don't cast the return value of malloc() and family. Also, prefer to use the size of the (derefenced) variable than the type (not so important here, but improves robustness and clarity when the variable's declaration is a long way from the assignment).

    Node *newNode = (Node*) malloc(sizeof(Node));

is better written as

    Node *newNode = malloc(sizeof *newNode);

Minor: if we're not using the command-line arguments in main(), declare it as the simpler alternative:

int main(void)