4
\$\begingroup\$

It takes integers from argv[] and inserts into tree, making sure to allocate memory and free that memory once the program has finished. How can I improve code quality, what are your suggestions?

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

struct treenode {
    int i;
    struct treenode *left;
    struct treenode *right;
};

void insert(struct treenode **t, int v){
    if(*t == NULL){
        struct treenode *x = malloc(sizeof(struct treenode));
        x->i = v;
        x->left = NULL;
        x->right = NULL;
        *t = x;
    } else if ( v < (*t)->i ) {
        insert(&(*t)->left, v);
    } else if (v > (*t)-> i) {
        insert(&(*t)->right, v);
    }
}

void printNode(struct treenode **t){
    if(*t == NULL){
    } else {
        printf("%i \n", (*t)->i);
        printNode(&(*t)->left);
        printNode(&(*t)->right);
    }
}

void freeNode(struct treenode **t){

    if ((*t)->left != NULL) {
        freeNode(&(*t)->left);
    }
    if ((*t)->right != NULL) {
        freeNode(&(*t)->right);
    }
    free(*t);

}


int main(int argc, char* argv[]){
    struct treenode *root = NULL;
    insert(&root, 5);

    for(int i=1; i<argc; ++i){
        insert(&root, atoi(argv[i]));
    }
    printNode(&root);
    freeNode(&root);
}
\$\endgroup\$
3
\$\begingroup\$

Advice 1

struct treenode *root = NULL;

I suggest you roll an explicit struct for the tree with a more describing name:

typedef struct binary_tree_t {
    ...
} binary_tree_t;

Advice 2

printNode() could be modified to do in-order traversal simply by rearranging the three statements:

printNode(&(*t)->left);
printf("%i \n", (*t)->i);
printNode(&(*t)->right);

Advice 3

I suggest you spit your data structure implementation into a header (*.h) and an implementation file (*.c).

Alternative implementation

I had this in mind:

binary_tree.h

#ifndef NET_CODERODDE_BINARY_TREE_H
#define NET_CODERODDE_BINARY_TREE_H

typedef struct binary_tree_node_t {
    int datum;
    struct binary_tree_node_t* left;
    struct binary_tree_node_t* right;
} binary_tree_node_t;

typedef struct binary_tree_t {
    binary_tree_node_t* root;
} binary_tree_t;

int binary_tree_t_init(binary_tree_t* tree);
int binary_tree_t_insert(binary_tree_t* tree, int datum);
void binary_tree_t_print(binary_tree_t* tree);
void binary_tree_t_free(binary_tree_t* tree);

#endif /* NET_CODERODDE_BINARY_TREE_H */

binary_tree.c

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

int binary_tree_t_init(binary_tree_t* tree)
{
    if (!tree)
    {
        return 0;
    }

    tree->root = NULL;
    return 1;
}

int binary_tree_t_insert(binary_tree_t* tree, int datum)
{
    binary_tree_node_t* new_node;
    binary_tree_node_t* curr_node;
    binary_tree_node_t* prev_node;

    if (!tree)
    {
        return 0;
    }

    new_node = malloc(sizeof *new_node);

    if (!new_node)
    {
        return 0;
    }

    new_node->left  = NULL;
    new_node->right = NULL;
    new_node->datum = datum;

    if (!tree->root)
    {
        tree->root = new_node;
    }
    else
    {
        prev_node = NULL;
        curr_node = tree->root;

        while (curr_node)
        {
            if (datum < curr_node->datum)
            {
                prev_node = curr_node;
                curr_node = curr_node->left;
            }
            else if (datum > curr_node->datum)
            {
                prev_node = curr_node;
                curr_node = curr_node->right;
            }
            else
            {
                /* datum already in the tree */
                return 1;
            }
        }

        if (datum < prev_node->datum)
        {
            prev_node->left = new_node;
        }
        else
        {
            prev_node->right = new_node;
        }
    }

    return 1;
}

static void binary_tree_t_print_impl(binary_tree_node_t* node)
{
    if (!node)
    {
        return;
    }

    binary_tree_t_print_impl(node->left);
    printf("%d ", node->datum);
    binary_tree_t_print_impl(node->right);
}

void binary_tree_t_print(binary_tree_t* tree)
{
    if (!tree)
    {
        printf("null tree");
        return;
    }

    binary_tree_t_print_impl(tree->root);
}

static void binary_tree_t_free_impl(binary_tree_node_t* node)
{
    if (!node)
    {
        return;
    }

    binary_tree_t_free_impl(node->left);
    binary_tree_t_free_impl(node->right);
    free(node);
}

void binary_tree_t_free(binary_tree_t* tree)
{
    if (!tree)
    {
        return;
    }

    binary_tree_t_free_impl(tree->root);
}
\$\endgroup\$
4
\$\begingroup\$
  • printNode and freeNode are misnomers. These functions do not print and free the individual node, but the entire tree. printTree and freeTree look more appropriate.

  • An empty if clause in printTree looks unpleasant. Early return is perfectly OK.

  • Passing a double pointer to seems like an overkill. A simple pointer works well and honestly is more readable, e.g.

        void freeTree(struct treenode * root)
        {
            if (root == NULL) {
                return;
            }
            freeTree(root->left);
            freeTree(root->right);
            free(root);
        }
    
  • Insertion doesn't need to be recursive. The compiler may recognize a tail recursion and optimize it out, but I recommend to be explicit.

\$\endgroup\$

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.