/*
* tree.c
* A package for managing generic binary trees.
*/
#include "tree.h"
#include <stdlib.h>
/* Prototypes of
static functions: */
static void
tree_del_node (Tree *p_tree, Node *p_node);
static void
tree_reset_sub_tree (Node *p_node, int
is_owner);
/*
------------------------------------------------------------------------
* Function: tree_init
*/
Tree *tree_init (Comp_func
f_comp, int is_owner)
{
Tree
*p_tree;
/* Sanity check: */
if (f_comp ==
NULL)
return
(NULL);
/* Allocate the
Tree structure. */
p_tree = (Tree *) malloc (sizeof(Tree));
/* Set its fields
(the tree is now empty). */
p_tree->p_root = NULL;
p_tree->n_objects = 0;
p_tree->f_comp = f_comp;
p_tree->is_owner = is_owner;
return
(p_tree);
}
/*
------------------------------------------------------------------------
* Function: tree_insert
*/
void tree_insert (Tree *p_tree, void *p_obj)
{
Node
*p_insert; /* The new node we insert. */
Node
*p_curr; /* The current node we scan. */
/* Sanity check: */
if (p_tree ==
NULL || p_obj == NULL)
return;
/* Create a new
node pointing to the new object. */
p_insert = (Node *) malloc (sizeof(Node));
p_insert->p_parent = NULL;
p_insert->p_object = p_obj;
p_insert->p_right = NULL;
p_insert->p_left = NULL;
/* If the tree is
empty, set the new node as its root. */
if
(p_tree->p_root == NULL)
{
p_tree->p_root = p_insert;
p_tree->n_objects = 1;
return;
}
/* In case the tree
is not empty, start scanning it from its root. */
p_curr = p_tree->p_root;
while (1)
{
/* Compare the
inserted object with the object stored at the current
node. */
if
(p_tree->f_comp (p_curr->p_object, p_obj) < 0)
{
/* The new
object should be inserted at the left sub-tree of p_curr. */
if
(p_curr->p_left == NULL)
{
/* No left
child - insert p_insert as p_curr's left child. */
p_curr->p_left = p_insert;
p_insert->p_parent = p_curr;
break;
}
/* Proceed to
the left sub-tree of p_curr. */
p_curr = p_curr->p_left;
}
else
{
/* The new
object should be inserted at the right sub-tree of p_curr. */
if
(p_curr->p_right == NULL)
{
/* No right
child - insert p_insert as p_curr's right child. */
p_curr->p_right = p_insert;
p_insert->p_parent = p_curr;
break;
}
/* Proceed to
the right sub-tree of p_curr. */
p_curr = p_curr->p_right;
}
}
/* Update the
number of objects in the tree. */
p_tree->n_objects++;
return;
}
/*
------------------------------------------------------------------------
* Function: tree_find
*/
const Node *tree_find (const Tree *p_tree, void
*p_obj)
{
const
Node *p_curr; /* The
current node we scan. */
int res; /*
Current comparison result. */
/* Sanity check: */
if (p_tree ==
NULL || p_obj == NULL)
return
(NULL);
/* Start scanning
the tree it from its root. */
p_curr = p_tree->p_root;
while (p_curr
!= NULL)
{
/* Compare the
queried object with the object stored at the current
node. */
res = p_tree->f_comp
(p_curr->p_object, p_obj);
if (res == 0)
{
/* The object
was found at p_curr. */
return
(p_curr);
}
else if (res < 0)
{
/* Continue
scanning the left sub-tree of p_curr. */
p_curr = p_curr->p_left;
}
else
{
/* Continue
scanning the right sub-tree of p_curr. */
p_curr = p_curr->p_right;
}
}
/* If we reached
here, the queried object was not found. */
return
(NULL);
}
/*
------------------------------------------------------------------------
* Function: tree_delete
*/
int tree_delete (Tree *p_tree, void *p_obj)
{
Node
*p_del; /* Points to the node to be deleted. */
/* Sanity check: */
if (p_tree ==
NULL || p_obj == NULL)
return (0);
/* Find the object
in the tree. */
p_del = (Node *) tree_find (p_tree, p_obj);
if (p_del ==
NULL)
/* The object is
not found in the tree. */
return (0);
/* Delete the node
containing p_obj from the tree: */
tree_del_node (p_tree, p_del);
return (1);
}
/*
------------------------------------------------------------------------
* Function: tree_delete
*/
void tree_reset (Tree *p_tree)
{
/* Sanity check: */
if (p_tree ==
NULL)
return;
/* If the tree is
not empty, delete the sub-tree rooted at the
tree root (i.e. the entire tree). */
if
(p_tree->p_root != NULL)
tree_reset_sub_tree (p_tree->p_root,
p_tree->is_owner);
/* Mark that the
tree is now empty. */
p_tree->p_root = NULL;
p_tree->n_objects = 0;
return;
}
/*
------------------------------------------------------------------------
* Function: tree_min
*/
const Node *tree_min (const Tree *p_tree)
{
const
Node *p_min;
/* Sanity check: */
if (p_tree ==
NULL)
return
(NULL);
/* In case of an
empty tree: */
if
(p_tree->p_root == NULL)
return
(NULL);
/* Find the
leftmost node in the tree and return it. */
p_min = p_tree->p_root;
while
(p_min->p_left != NULL)
p_min = p_min->p_left;
return
(p_min);
}
/*
------------------------------------------------------------------------
* Function: tree_next
*/
const Node *tree_next (const Node *p_node)
{
const
Node *p_succ;
/* Sanity check: */
if (p_node ==
NULL)
return
(NULL);
/* Check if p_node has a right child and act accordingly.
*/
if
(p_node->p_right != NULL)
{
/* If the node
has a right child, its successor is the leftmost
child in the right sub-tree. */
p_succ = p_node->p_right;
while
(p_succ->p_left != NULL)
p_succ = p_succ->p_left;
}
else
{
/* Go up the tree
until reaching an ancestor node from the left.
This ancestor node is the successor of
p_node in the tree. */
p_succ = p_node;
while
(p_succ->p_parent != NULL &&
p_succ ==
p_succ->p_parent->p_right)
{
p_succ = p_succ->p_parent;
}
p_succ = p_succ->p_parent;
}
return
(p_succ);
}
/*
------------------------------------------------------------------------
* Function: tree_max
*/
const Node *tree_max (const Tree *p_tree)
{
const
Node *p_max;
/* Sanity check: */
if (p_tree ==
NULL)
return
(NULL);
/* In case of an
empty tree: */
if
(p_tree->p_root == NULL)
return
(NULL);
/* Find the
rightmost node in the tree and return it. */
p_max = p_tree->p_root;
while
(p_max->p_right != NULL)
p_max = p_max->p_right;
return
(p_max);
}
/*
------------------------------------------------------------------------
* Function: tree_prev
*/
const Node *tree_prev (const Node *p_node)
{
const
Node *p_pred;
/* Sanity check: */
if (p_node ==
NULL)
return
(NULL);
/* Check if p_node
has a left child and act accordingly. */
if
(p_node->p_left != NULL)
{
/* If the node
has a left child, its predecessor is the rightmost
child in the left sub-tree. */
p_pred = p_node->p_left;
while
(p_pred->p_right != NULL)
p_pred = p_pred->p_right;
}
else
{
/* Go up the tree
until reaching an ancestor node from the right.
This ancestor node is the predecessor of
p_node in the tree. */
p_pred = p_node;
while
(p_pred->p_parent != NULL &&
p_pred ==
p_pred->p_parent->p_left)
{
p_pred = p_pred->p_parent;
}
p_pred = p_pred->p_parent;
}
return
(p_pred);
}
/*
------------------------------------------------------------------------
* Function: tree_del_node
* Purpose:
Delete a node from a binary tree.
* Input:
p_tree - The binary tree.
*
p_node - A pointer to the node
to be deleted.
* Returns:
Nothing.
*/
static void
tree_del_node (Tree *p_tree, Node *p_node)
{
/* Check how many
children p_node has and act accordingly. */
if
(p_node->p_left == NULL || p_node->p_right == NULL)
{
/* If one of the
children is not NULL (but the other must be), keep
a pointer to it. */
Node
*p_child = NULL;
if
(p_node->p_left != NULL)
p_child = p_node->p_left;
else if (p_node->p_right != NULL)
p_child = p_node->p_right;
/* If necessary,
free the object stored at p_node. */
if
(p_tree->is_owner)
free (p_node->p_object);
/* Link p_child
directly to p_node's parent. */
if
(p_node->p_parent != NULL)
{
/* Check if
p_node is a left or a right child, and link p_child
instead of it. */
if
(p_node == p_node->p_parent->p_left)
p_node->p_parent->p_left =
p_child;
else
p_node->p_parent->p_right =
p_child;
}
else
{
/* Make p_child
the new tree root. */
p_tree->p_root = p_child;
}
if (p_child
!= NULL)
p_child->p_parent =
p_node->p_parent;
/* Free the node
itself. */
free (p_node);
}
else
{
/* The node to be
deleted has two children: Find its successor, which
is the leftmost node in its right
sub-tree. */
Node
*p_succ;
void *temp;
p_succ = p_node->p_right;
while
(p_succ->p_left != NULL)
p_succ = p_succ->p_left;
/* Swap the
objects pointed by p_node and its successor, so p_succ will
store the object that we wish to delete.
*/
temp = p_node->p_object;
p_node->p_object = p_succ->p_object;
p_succ->p_object = temp;
/* Now we can
simply delete p_succ recursively. Notice that it has one
child at most, so the recursion will
stop there. */
tree_del_node (p_tree, p_succ);
}
return;
}
/*
------------------------------------------------------------------------
* Function: tree_reset_sub_tree
* Purpose:
Delete the entire sub-tree rooted at a given root.
* Input:
p_node - A pointer to the
sub-tree root.
*
is_owner - Does the tree own its objects (and should free them).
* Returns:
Nothing.
*/
static void
tree_reset_sub_tree (Node *p_node, int
is_owner)
{
/* If necessary,
free the object. */
if (is_owner)
free (p_node->p_object);
/* Free the left
and right sub-trees recursively. */
if
(p_node->p_left != NULL)
tree_reset_sub_tree (p_node->p_left,
is_owner);
if
(p_node->p_right != NULL)
tree_reset_sub_tree (p_node->p_right,
is_owner);
/* Free the node
itself. */
free (p_node);
return;
}