#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <malloc.h>
#include <assert.h>
#include "utils.h"

Typedefs
typedef struct BiTreeNode_ *	BiTreeNode

typedef struct BiTree_ *	BiTree

Functions
BiTree	BITREEinit (void(destroy)(void data))

void	BITREEdestroy (BiTree tree)

void	BITREEsetcompare (BiTree tree, int(compare)(const void key1, const void *key2))

int	BITREEinsleft (BiTree tree, BiTreeNode node, const void *data)

int	BITREEinsright (BiTree tree, BiTreeNode node, const void *data)

int	BITREEinsert (BiTree tree, const void *data)

int	BITREElookup (BiTree tree, void **data)

int	BITREEremove (BiTree tree, void **data)

void	BITREEremleft (BiTree tree, BiTreeNode node)

void	BITREEremright (BiTree tree, BiTreeNode node)

BiTree	BITREEmerge (BiTree left, BiTree right, const void *data)

int	BITREEsize (BiTree tree)

BiTreeNode	BITREEroot (BiTree tree)

int	BITREEis_eob (BiTreeNode node)

int	BITREEis_leaf (BiTreeNode node)

void *	BITREEdata (BiTreeNode node)

BiTreeNode	BITREEleft (BiTreeNode node)

BiTreeNode	BITREEright (BiTreeNode node)

int	BITREEheight (BiTree tree)

void	BITREEprint (BiTree tree, void(callback)(const void data))

void	BITREEpreorder (BiTree tree, void(callback)(const void data))

void	BITREEinorder (BiTree tree, void(callback)(const void data))

void	BITREEpostorder (BiTree tree, void(callback)(const void data))

Typedef Documentation

typedef struct BiTree_* BiTree

Use a typedef - to hide the interior of BiTree_ - in the implementation file. This is how data hiding can be done in C.

Definition at line 50 of file bitree.h.

typedef struct BiTreeNode_* BiTreeNode

Use a typedef - to hide the interior of BiTreeNode_ - in the implementation file. This is how data hiding can be done in C.

Definition at line 43 of file bitree.h.

Function Documentation

void* BITREEdata ( BiTreeNode node )

Get a reference to node data

Parameters

[in] node - reference to current node

Returns: Generic reference to node data.

Definition at line 371 of file bitree.c.

void BITREEdestroy ( BiTree tree )

Destroy the tree

The tree is destroyed - that is, all dynamically allocated memory occupied by the nodes - will be destroyed. It is the user-defined callback function destroy, given as an argument to BITREEinit(), that is responsible for freeing dynamically allocated node data, when this function is called. If, on the other hand, destroy is set to NULL when BITREEinit() is called, all node data will be left untouched after the tree is dismounted and destroyed. When all nodes and data have been deallocated - the rest of the tree is freed, too.

Parameters

[in] tree - a reference to current tree.

Returns: Nothing.

See Also: BITREEinit()

Definition at line 76 of file bitree.c.

int BITREEheight ( BiTree tree )

Get the tree height(=nr of levels).

Parameters

[in] tree - reference to current tree

Returns: Tree height - i.e. the max. number of levels in the tree.

Definition at line 386 of file bitree.c.

BiTree BITREEinit ( void(*)(void *data) destroy )

Initialize the tree

Parameters

[in] destroy - a reference to a user-defined function, reponsible for freeing node data, when the tree is destroyed. If destroy is set to NULL - then node data will be left untouched upon tree destruction.

Returns: A reference - to a new, empty tree - if dynamic memory allocation for the ADT was successful - or NULL otherwise. Take really good care of this return value, since it will be needed as a parameter in subsequent calls - to the majority of other tree functions in this function interface - i.e. a sort of "handle" to the tree.

Definition at line 62 of file bitree.c.

void BITREEinorder	(	BiTree	tree,
		void()(const void data)	callback
	)

Traverse the entire tree - in inorder.

Inorder traversal means the following, where recursion is obvious:

As long as we are visiting a valid(=not NULL) node - do:

First - goto the left subtree of the root node - and traverse this subtree in inorder...
..visit the root node...
..and finally goto the right subtree - and traverse this subtree, too - in inorder.

Parameters

[in]	tree	- reference to current tree.
[in]	callback	- reference to user-defined callback function, that gets read access to element data via its parameter data - to do whatever is relevant. In could be a matter of formatting data for printing on screen, for example.

Returns: Nothing.

Definition at line 403 of file bitree.c.

int BITREEinsert	(	BiTree	tree,
		const void *	data
	)

Insert a new node with data - into the tree

First a search is made to determine if a node with data equal to parameter data already exists in the tree. If so, the function returns immediately - with value 1. Otherwise a new node is created, to be inserted into the tree according to the rules for a binary search tree - that is, at any given node - all nodes in the left subtree hold data less than data of the new node - and all nodes of the right subtree has data larger than that of the new node. It is the responsability of the caller to ensure, that this memory is valid as long as it is present in the tree.

Parameters

[in]	tree	- reference to current tree.
[in]	data	- reference to data to be inserted into the tree. It is the responsability of the caller to ensure, that this memory is valid as long as it is present in the tree.

Returns: Value 0, if insertion was succesful.
Value -2, if BITREEsetcompare() not has been called prior to this call.
Value 1, if data already exists in the tree.
Value -1, indicates fatal error.

Definition at line 166 of file bitree.c.

int BITREEinsleft	(	BiTree	tree,
		BiTreeNode	node,
		const void *	data
	)

Insert a new node as a left child node of parameter node.

The insertion of a new node will only be succesful, if parameter node has no left child. If parameter node is set to NULL, the new node will be inserted as the root node of the tree. This can only take place - if the tree is empty prior to the call. The data to be inserted, is referenced by parameter data. It is the responsability of the caller to ensure, that this memory is valid as long as it is present in the tree.

Parameters

[in]	tree	- a reference to current tree.
[in]	node	- a reference to the parent node of the new, left child, which implies, that the parent must not have any left child prior to the call. If node is set to NULL, the new node will be the root node of the tree. This will only happen if the tree is empty prior to call.
[in]	data	- a reference to data to be inserted into the tree.

Returns: Value 0 if insertion was successful - or -1 otherwise, i.e. if parameter node already has a left child - or, if node is set to NULL and the tree is not empty.

Definition at line 90 of file bitree.c.

int BITREEinsright	(	BiTree	tree,
		BiTreeNode	node,
		const void *	data
	)

Insert a new node as a right child node of parameter node.

The insertion of a new node will only be succesful, if parameter node has no right child. If parameter node is set to NULL, the new node will be inserted as the root node of the tree. This can only take place - if the tree is empty prior to the call. The data to be inserted, is referenced by parameter data. It is the responsability of the caller to ensure, that this memory is valid as long as it is present in the tree.

Parameters

[in]	tree	- a reference to current tree.
[in]	node	- a reference to the parent node of the new, right child, which implies, that the parent must not have any right child prior to the call. If node is set to NULL, the new node will be the root node of the tree. This will only happen if the tree is empty prior to call.
[in]	data	- a reference to data to be inserted into the tree.

Returns: Value 0 if insertion was successful - or -1 otherwise, i.e. if parameter node already has a right child - or, if node is set to NULL and the tree is not empty.

Definition at line 128 of file bitree.c.

int BITREEis_eob ( BiTreeNode node )

Determines whether the parameter node is NULL - i.e. "end-of-branch" - or not

Parameters

[in] node - the node to be tested

Returns: Value 1 if node is the end of a branch in the tree - or 0 otherwise.

Definition at line 361 of file bitree.c.

int BITREEis_leaf ( BiTreeNode node )

Determines if the the parameter node is a leaf node, i.e. has no children - or not

Parameters

[in] node - the node to be tested

Returns: Value 1 if node is a leaf node - or 0 otherwise.

Definition at line 366 of file bitree.c.

BiTreeNode BITREEleft ( BiTreeNode node )

Get a reference to left child node.

Parameters

[in] node - reference to current node

Returns: A reference to left child of parameter node.

Definition at line 376 of file bitree.c.

int BITREElookup	(	BiTree	tree,
		void **	data
	)

Lookup data in the tree - without removing it.

Determines whether a node, with key data matching the data referenced by the parameter data - is present in the current tree. This 2nd parameter, data, should reference an (external, user-defined) pointer, that points to the search key data. After the call - this referenced, external pointer has been redirected by this function, to point to the data of the node hit - if the call was succesful. Moreover, a user-defined callback function, responsible for doing the matching of node data - and data referenced by parameter data - must exist for this function to work. This user-supplied callback is set with a prior call to function BITREEsetcompare().

Parameters

[in]	tree	- reference to current tree.
[in,out]	data	- a reference to an external pointer, pointing at the data to be searched for - at the call. Upon return - this pointer has been redirected by this function - and points instead to data contained in the node hit - if any.

Returns: Value 0 - if call was successful.
Value -2, if BITREEsetcompare() not has been called prior to this call.
Value -1, if searched node not found.

Definition at line 209 of file bitree.c.

BiTree BITREEmerge	(	BiTree	left,
		BiTree	right,
		const void *	data
	)

Merge two trees as subtrees to a new root node - containing parameter data as root node data.

This function merges the two trees referenced by parameters left and right - into a new, single binary tree - returned by the function, if the call was successful. After merging, the new, merged tree will have a root node containing parameter data as node data - and the trees referenced by left and right, respectively - as left and right subtrees. The size of the new, merged tree will be updated accordingly. Finally, the two trees left and right are detached from their tree nodes - leaving only the tree headers - and setting tree size to 0. It is the responsability of the caller to care for the future of these two, empty trees - destroying them when appropriate.

Parameters

[in]	left	- reference to a tree, that will serve as the left subtree of the new, merged tree - returned by this function.
[in]	right	- reference to a tree, that will serve as the right subtree of the new, merged tree - returned by this function.
[in]	data	- data to be inserted in the root node of the new, merged tree.

Returns: A new, merged tree if the merge was successful - or NULL otherwise.

Definition at line 318 of file bitree.c.

void BITREEpostorder	(	BiTree	tree,
		void()(const void data)	callback
	)

Traverse the entire tree - in postorder.

Postorder traversal means the following, where recursion is obvious:

As long as we are visiting a valid(=not NULL) node - do:

First - goto the left subtree of the root node - and traverse this subtree in postorder...
..then goto the right subtree of the root node - and traverse this subtree in postorder...

..and finally - visit the root node.

Parameters

[in]	tree	- reference to current tree.
[in]	callback	- reference to user-defined callback function, that gets read access to element data via its parameter data - to do whatever is relevant. In could be a matter of formatting data for printing on screen, for example.

Returns: Nothing.

Definition at line 408 of file bitree.c.

void BITREEpreorder	(	BiTree	tree,
		void()(const void data)	callback
	)

Traverse the entire tree - in preorder

Preorder traversal means the following, where recursion is obvious:

As long as we are visiting a valid(=not NULL) node - do:

First - visit the root node...
..then goto the left subtree of the root node - and traverse this subtree in preorder...
..and finally goto the right subtree - and traverse this subtree, too - in preorder.

Parameters

[in]	tree	- reference to current tree.
[in]	callback	- reference to user-defined callback function, that gets read access to element data via its parameter data - to do whatever is relevant. In could be a matter of formatting data for printing on screen, for example.

Returns: Nothing.

Definition at line 398 of file bitree.c.

void BITREEprint	(	BiTree	tree,
		void()(const void data)	callback
	)

Print all tree nodes, with their data, on screen.

Parameters

[in]	tree	- reference to current tree.
[in]	callback	- reference to user-defined callback function, that gets read access to element data via its parameter data - to do whatever is relevant. In this case it is a matter of formatting data for printing on screen. The printed data should be kept to a minimum (the key value, for example) in order not to clutter the screen. This function is primarily for small trees - and educational/debugging purposes.

Returns: Nothing.

Definition at line 391 of file bitree.c.

void BITREEremleft	(	BiTree	tree,
		BiTreeNode	node
	)

Remove the left subtree

This function removes the subtree rooted as the left child of parameter node. The removal is accomplished by a postorder traversal beginning at this left child of parameter node. However, if node is set to NULL, the removal will instead start at the root of the tree - and thereby remove the entire tree. The function referenced by destroy, initially passed as a parameter to BITREEinit(), will be called exactly once for each destroyed node - provided destroy was not set to NULL - when BITREEinit() was called.

Parameters

[in]	tree	- reference to current tree.
[in]	node	- reference to a node - or set to NULL.

Returns: Nothing.

See Also: BITREEinit()

Definition at line 250 of file bitree.c.

int BITREEremove	(	BiTree	tree,
		void **	data
	)

Physically remove a node - with its data from the tree.

This function, when successful, removes the searched node from the tree - and hands node data back to the caller - while preserving the validity of the tree as a binary search tree. When called, the 2nd parameter of this function, data, should reference an (external, user-defined) pointer, that points to the search key data. After the call - this referenced, external pointer has been redirected by this function, to point to the data of the removed element - if the call was succesful. The caller is responsible for the future of this memory - deallocating it, if needed, for example. Moreover, a user-defined callback function, responsible for doing the matching of node data - and data referenced by parameter data - must exist for this function to work. This user-supplied callback is set with a prior call to function BITREEsetcompare().

Parameters

[in]	tree	- reference to current tree.
[in,out]	data	- a reference to an external pointer, pointing at the data to be removed - at the call. Upon return - this pointer has been redirected by this function - and points instead to data contained in the node hit - if any.

Returns: Value 0 - if call was successful.
Value -2, if BITREEsetcompare() not has been called prior to this call.
Value -1, if searched node not found.

See Also: BITREEsetcompare()

Definition at line 238 of file bitree.c.

void BITREEremright	(	BiTree	tree,
		BiTreeNode	node
	)

Remove the right subtree

This function removes the subtree rooted as the right child of parameter node. The removal is accomplished by a postorder traversal beginning at this right child of parameter node. However, if node is set to NULL, the removal will instead start at the root of the tree - and thereby remove the entire tree. The function referenced by destroy, initially passed as a parameter to BITREEinit(), will be called exactly once for each destroyed node - provided destroy was not set to NULL - when BITREEinit() was called.

Parameters

[in]	tree	- reference to current tree.
[in]	node	- reference to a node - or set to NULL.

Returns: Nothing.

See Also: BITREEinit()

Definition at line 284 of file bitree.c.

BiTreeNode BITREEright ( BiTreeNode node )

Get a reference to right child node.

Parameters

[in] node - reference to current node

Returns: A reference to right child of parameter node.

Definition at line 381 of file bitree.c.

BiTreeNode BITREEroot ( BiTree tree )

Get the root node of the tree

Parameters

[in] tree - a reference to the current tree

Returns: A reference to the root node of the tree.

Definition at line 356 of file bitree.c.

void BITREEsetcompare	(	BiTree	tree,
		int()(const void key1, const void *key2)	compare
	)

Set the compare callback function

Parameters

[in]	tree	- a reference to current tree.
[in]	compare	- reference to a user-defined callback function responsible for comparing node data. This callback function should return a value of -1 if data referenced by key1 is less than data referenced by key2 - or 0 if they are equal - or 1 otherwise. The purpose of this function is to implement node data searching - and it must be called (at least) - once - prior to calls of such searching functions - for example, BITREEinsert(), BITREElookup() and BITREEremove().

Returns: Nothing.

Definition at line 85 of file bitree.c.

int BITREEsize ( BiTree tree )

Get the size of the tree

Parameters

[in] tree - a reference to the current tree

Returns: The size, i.e. the number of nodes in the tree.

Definition at line 351 of file bitree.c.

Typedefs

Functions

Typedef Documentation

Function Documentation