As pointed out before, the struct (structure) is equivalent to a class in C. Thus, to create a tree node, we define:

struct tree_node {
	int value;
	struct tree_node * left;
	struct tree_node * right;
};

Unfortunately, any time you want to define a varaible to be of this type, you must continue to use the struct keyword. Thus, we would be forced to define, for example, the root of the tree as

struct tree_node * root;

and every function call would be littered with the struct keyword. (Imagine having to put the keyword class in front of every appearence of the name of a class.)

To solve this problem, C uses the typedef keyword:

typedef struct tree_node Node;

Note that, like sizeof, the keyword typedef is undestood and interpreted by the compiler and does not affect the resulting code.

Memory Allocation and Initialization

The next step is memory allocation. The void * malloc( int n ) function requests n bytes of memory from the OS and returns the address of the first byte. (void * represents a general pointer.) You can allocate memory using

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

The sizeof keyword is interpreted by the compiler which determines the number of bytes required by Node (on ecelinux, this is 12 bytes). Unfortunately malloc, unlike a constructor, does not initialize the object and therefore initialization must be performed separately. To initialize a node, we create the following function:

void init( Node ** node, int n ) {
	*node = malloc( sizeof( Node ) );
	*node -> value = n;

	*node -> left =  NULL;
	*node -> right = NULL;
}

We are passing a pointer to a pointer to a Node, however, in reality, we would pass the address of a pointer to a node to initialize it. For example:

	Node * ptr;

	init( &ptr );  // pass a pointer to ptr

Thus, inside the init function, ptr would be assigned the address returned by malloc and the values would be initialized.

Insertion

Suppose we are generating a binary search tree. The following function takes a pointer to the root of the tree and:

• If the root is null, it assigns the root a new node, otherwise,
• It traverses the tree to determine where the insertion should take place.

This is a procedural approach to making an insertion into a tree, as opposed to an object-oriented approach seen in ECE 250.

void insert( Node ** root, int n ) {
	/* Deal with the special case where the root
	   is unassigned. */

	if ( *root == NULL ) {
		*root = malloc( sizeof( Node ) );
		init( root, n );
		return;
	}

	/* Otherwise, step through the tree to find 
	   where an insertion should occur. */

	Node * ptr = *root;

	while( 1 ) {
		if ( n < ptr -> value ) {
			if ( ptr -> left == NULL ) {
				init( &(ptr -> left), n );

				return;
			} else {
				ptr = ptr -> left;
			}
		} else if ( n > ptr -> value ) {
			if ( ptr -> right == NULL ) {
				ptr -> right = malloc( sizeof( Node ) );
				init( &(ptr -> right), n );

				return;
			} else {
				ptr = ptr -> right;
			}
		}

		/* do not insert repeated values */
	}
}

Tree Traversals

The tree tranversal algorithm below is broken into two components: the top-level traversal function ensures that the root is not NULL. In this case, it calls a recursive routine (rec) which performs the actual travesal. Here we present a simple traversal which prints the node value based on whether we want:

• a pre-order traversal (-1),
• an in-order traversal (0), or
• a post-order traversal (1).

void traversal_rec( Node * node, int which ) {
	if ( which == -1 ) {
		printf( "%3d ", node -> value );
	}

	if ( node -> left != NULL ) {
		traversal_rec( node -> left, which );
	}

	if ( which == 0 ) {
		printf( "%3d ", node -> value );
	}

	if ( node -> right != NULL ) {
		traversal_rec( node -> right, which );
	}

	if ( which == 1 ) {
		printf( "%3d ", node -> value );
	}
}

void traversal( Node * root, int which ) {
	if ( root == NULL ) {
		return;
	}

	traversal_rec( root, which );

	printf( "\n" );
}

Cleaning Up

Like new and delete in C++, memory must be allocated and freed in C. To free all of the nodes, we perform a post-order traversal, and when it comes time to visit the node, this indicates that the memory for either the left or right child (if any) has already been freed. As we don't want to call free on NULL, we use the same idea of a top-level function and a recursive function as we saw in the previous example of a traversal.

void clean_rec( Node * node ) {
        if ( node -> left != NULL ) {
                clean_rec( node -> left );
        }

        if ( node -> right != NULL ) {
                clean_rec( node -> right );
        }

        free( node );
}

void clean( Node * root ) {
        if ( root == NULL ) {
                return;
        }

        clean_rec( root );
}

Sample int main() Function

The following puts a sequence of values into the binary tree and then prints a pre-, in-, and post-order traversal of the tree.

int main() {
	Node * root = NULL;
	int i;

	printf( "Adding:     " );

	for ( i = 1; i < 15; ++i ) {
		int val = 59*i % 167;
		printf( "%3d ", val );
		insert( &root, val );
	}

	printf( "\n" );

	printf( "Pre-order:  " );
	traversal( root, -1 );

	printf( "In-order:   " );
	traversal( root,  0 );

	printf( "Post-order: " );
	traversal( root,  1 );

	return 0;
}

For a source file containing all of the code in this block, see tree.c.

Top