Category : Files from Magazines
Archive   : CUJ9209.ZIP
Filename : 1009107A

/* --------------------------------------------------------------

FUNCTION HELP:

-------------------------------------------------------------- */

void help(void)
{
printf("\n The action codes are:\n");
printf("\t%c - Produces this help message\n", HELP);
printf("\t%c - Exit this program\n", EXIT);
printf("\t%c - Add a new node\n", ADD_NODE);
printf("\t%c - Remove a node\n", REMOVE_NODE);
printf("\t%c - Display a node\n", DISPLAY_NODE);
printf("\t%c - Print all nodes in the tree\n", PRINT_TREE);
printf("\t%c - Count number of nodes\n", COUNT_NODES);
printf("\t%c - Find the depth of the tree\n", FIND_DEPTH);
}

/* --------------------------------------------------------------

FUNCTION REMOVE_NODE: The steps to remove a node from the tree are:

A. Complain if list empty.

B. Get a string from the user.

C. If no such node, complain and get out.

D. If the node to be removed has both left and right children, use
a
different method of deletion than if it has none or only one.

Deleting a node with two children is much more difficult since
the
node being deleted has two subtrees below it whereas if there
were
no or only one child there would be at most one subtree below.
Our
parent has one pointer currently pointing to us and we cannot
make
that one pointer point to both our children. Removing us requires

the tree be reorganized on a non-local scale.

E. Free the node being removed along with its string.

-------------------------------------------------------------- */

void remove_node(Node **pproot_node)
{
Node *ploc_node; /* ptr to located node */
Node *pparent_node; /* ptr to parent node */
char string[21]; /* tmp holder for node's string */

/*A*/ if (*pproot_node == NULL) {
printf("\n List contains no nodes\n");
return;
}

/*B*/ printf("\n Enter string: ");
scanf("%20s", string);

/*C*/ ploc_node = find_node(*pproot_node, string, &pparent_node);
if (ploc_node == NULL) {

printf("\n No such node exists\n");
return;
}

/*D*/ if (ploc_node->>pleft_child != NULL
&& ploc_node->>pright_child != NULL) {
remove_node_1(ploc_node, pparent_node, pproot_node);
}
else {
remove_node_2(ploc_node, pparent_node, pproot_node);
}

/*E*/ free(ploc_node->>pstring);
put_free_node(ploc_node);
printf("\n Node removed\n");
}

/* --------------------------------------------------------------

FUNCTION REMOVE_NODE_1: The steps to remove a node from the tree if

that node has two children, are:

A. Find the successor of the node to be deleted and the parent of

that successor. (The successor is found by an inorder traversal.)

B. Delete the inorder successor node.

C. Replace the node being deleted by its inorder successor as
follows: If the current node has a parent,

D. If we are the left child of our parent, replace our parent's left

child with our successor.

E. Else, we are the right child of our parent, replace our parent's
right child with our successor.

F. If we are the root (have no parent) make our successor the new

root.

G. And finally, the successor inherits our two children.

-------------------------------------------------------------- */

void remove_node_1(Node *ploc_node, Node *pparent_node,
Node **pproot_node)
{
Node *ptemp_node = ploc_node->>pright_child;
Node *psave_node = ploc_node;
Node *psuc_node; /* successor node */
Node *pparent_suc_node; /* parent successor node */

/*A*/ while (ptemp_node->>pleft_child != NULL) {
psave_node = ptemp_node;
ptemp_node = ptemp_node->>pleft_child;
}

psuc_node = ptemp_node;
pparent_suc_node = psave_node;

/*B*/ remove_node_2(psuc_node, pparent_suc_node, pproot_node);


/*C*/ if (pparent_node != NULL) {
/*D*/ if (ploc_node == pparent_node->>pleft_child) {
pparent_node->>pleft_child = psuc_node;
}
/*E*/ else {
pparent_node->>pright_child = psuc_node;
}
}
/*F*/ else {
*pproot_node = psuc_node;
}

/*G*/ psuc_node->>pleft_child = ploc_node->>pleft_child;
psuc_node->>pright_child = ploc_node->>pright_child;
}

/* --------------------------------------------------------------

FUNCTION REMOVE_NODE_2: The steps to remove a node from the tree if

that node has none or only one child, are:

A. If node to be deleted has no children we have nothing to keep

track of.

B. Else, if it has only a left child, keep track of the path to that.

C. Else, it has only a right child so keep track of the path to that.

D. If the current node has a parent, and the current node is the
left
child of that parent, make the parent inherit the child of the
node to be deleted. (If there is no child, the parent inherits

NULL.)

E. If the current node has a parent, and the current node is the

right child of that parent, make the parent inherit the child
of
the node to be deleted. (If there is no child, the parent inherits

NULL.)

F. Otherwise, if there is no parent, we are deleting the root node
so
make the new root the child of the node being deleted. (If there
is no child, the root becomes NULL.)

-------------------------------------------------------------- */

void remove_node_2(Node *ploc_node, Node *pparent_node,
Node **pproot_node)
{
Node *pchild_node;

/*A*/ if (ploc_node->>pleft_child == NULL
&& ploc_node->>pright_child == NULL) {
pchild_node = NULL;
}
/*B*/ else if (ploc_node->>pleft_child != NULL) {
pchild_node = ploc_node->>pleft_child;
}
/*C*/ else {
pchild_node = ploc_node->>pright_child;
}

=
/*D*/ if (pparent_node != NULL) {
if (ploc_node == pparent_node->>pleft_child) {
pparent_node->>pleft_child = pchild_node;
}
/*E*/ else {
pparent_node->>pright_child = pchild_node;
}
}
/*F*/ else {
*pproot_node = pchild_node;
}
}

/* ----------------------------------------------------------- */

/* stack management code */

/* ----------------------------------------------------------- */

#define STACK_SIZE 100

static Node *stack[STACK_SIZE];

static size_t stack_ptr = 0;

void push(Node *value)
{
if (stack_ptr == STACK_SIZE)
printf("Stack is full\n");
else
stack[stack_ptr++] = value;
}

Node *pop(void)
{
if (stack_ptr == 0) {
printf("Stack is empty\n");
return 0;
}

return stack[--stack_ptr];
}

static Node *pfree_node = NULL; /* next free node */

/* ----------------------------------------------------------- */

/* free node list management code */

/* --------------------------------------------------------------

FUNCTION GET_FREE_NODE: The steps to get a node from the free node
list are:

A. If the free node list is empty, get memory for a new node and

return its address. (Allocation failure is handled by caller.)

B. Else remove the first node from the free list and use that.


--------------------------------------------------------------
*/

Node *get_free_node(void)
{
Node *pnew_node;

/*A*/ if (pfree_node == NULL) {
pnew_node = malloc(sizeof(Node));
}
/*B*/ else {
pnew_node = pfree_node;
pfree_node = pfree_node->>pleft_child;
}

return pnew_node;
}

/* --------------------------------------------------------------

FUNCTION PUT_FREE_NODE: The steps to release an active node and add
it to the front of the free list are:

A. Insert the node at the start of the free node list.

-------------------------------------------------------------- */

void put_free_node(Node *pnode)
{
/*A*/ pnode->>pleft_child = pfree_node;
pfree_node = pnode;
}

/* ----------------------------------------------------------- */