Write a program to read integers, store them in a binary tree, display the content of the tree, deletes the tree and exits. Decide in what order the integers are added to the tree and develop a convenient way for displaying the tree.

Source Code

Brief explanation is provided after the source code.

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

struct tnode{
    int number;
    struct tnode *left; /* left Child */
    struct tnode *right; /* right Child */
};

struct tnode *addtree(struct tnode*, int);
void treeprint(struct tnode*);
struct tnode *root;
struct tnode *talloc(void);
int *dupnum(int *);

int main(int argc, char **argv){
    FILE *in;
    const char * fn = "integer_file";
    char buff[0x200];
    root = NULL;  /* empty tree */

    if((in = fopen(fn,"rb")) == NULL){
        printf("Cannot open input file.\n");
        exit(1);
    }

     // Read integers from a file and add to a tree node
    while (fgets(buff, sizeof buff, in)) {
        root = addtree(root, atoi(buff));
    }

    printf("Tree is traversed in-order\n");
    treeprint(root);
    fclose(in);
    return 0;
}

/* addtree: add a node with n, at or below p */
struct tnode *addtree(struct tnode *p, int n){
    int cond;
    if (p == NULL){
        p = talloc();
        p -> number = dupnum(n);
        p -> left = p -> right = NULL;
    }else if (n <= p->number)
        p -> left = addtree(p -> left , n);
    else
        p -> right = addtree(p -> right , n);

    return p;
}

/* treeprint: in-order print of tree p */
void treeprint(struct tnode *p){

    if (p != NULL) {
        treeprint(p -> left);    /* Begin with left sub tree */
        fprintf(stdout,"%d\n" ,p -> number);     /* Output number */
        treeprint(p -> right);   /* then move to right sub tree */
    }
}

/* talloc: make a tnode */
struct tnode *talloc(void) {
    return (struct tnode *) malloc(sizeof(struct tnode)); 
}

/* duplicate a number */
int *dupnum(int *n){
    char *p;
    /* make a duplicate of n */
    p = (int *) malloc(sizeof(int));
    if(p != NULL)
        p = n;
    return p;
    free(p);
}
 

File Content

100
-1
10
-6
12
10
23
-7

When you compile and execute the above program it produces the following result on Linux:

Tree is traversed in-order
-7
-6
-1
10
10
12
23
100

Brief Explanation

  • The file fn is opened in binary mode for reading using the function fopen.
  • Each number in the file is added to a node on a binary tree using the function addtree.
  • The nodes are maintained so that at any node the left subtree contains only numbers that are less than or equal the number at the node, and the right subtree contains only numbers that are greater.
  • The content of the tree is printed using in order traversal to the stdout. By using in order traversal, the numbers will be sorted.

Add comment


Security code
Refresh