Category : Files from Magazines
Archive   : CUJ9208.ZIP
Filename : 1008108A

 
Output of file : 1008108A contained in archive : CUJ9208.ZIP

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

#include
#include
#include
#include

typedef struct node {
char *pstring;
struct node *pleft_child;
struct node *pright_child;
} Node;

#define EXIT 'E'
#define HELP '?'
#define ADD_NODE 'A'
#define REMOVE_NODE 'R'
#define DISPLAY_NODE 'D'
#define PRINT_TREE 'P'
#define COUNT_NODES 'C'
#define FIND_DEPTH 'F'

void help(void);
void add_node(Node **pproot_node);
void remove_node(Node **pproot_node);
void remove_node_1(Node *ploc_node, Node *pparent_node,
Node **pproot_node);
void remove_node_2(Node *ploc_node, Node *pparent_node,
Node **pproot_node);
void display_node(Node *proot_node);
void print_tree(Node *proot_node);
unsigned int count_nodes(Node *proot_node);
unsigned int find_depth(Node *proot_node);
Node *find_node(Node *proot_node, char *pstring,
Node **ppparent_node);

void push(Node *value);
Node *pop(void);

Node *get_free_node(void);
void put_free_node(Node *pnode);

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

main()
{
int inchar = 'x'; /* force initial prompt */
int done = 0;

static Node *proot_node = NULL;

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

while (!done) {
if (inchar != ' ')
printf("\nEnter Action Code (%c for help): ", HELP);
switch(toupper(inchar = getchar())) {

case EXIT:
done = 1;
break;

default:
printf("\n Invalid command. Please try again\n");
break;

case HELP:
help();
break;

case '\n': /* ignore white space on input */
case ' ' :
case '\t':
case '\v':
case '\f':
inchar = ' '; /* indicate white space input */
break;

case ADD_NODE:

add_node(&proot_node);
break;

case REMOVE_NODE:

remove_node(&proot_node);
break;

case DISPLAY_NODE:

display_node(proot_node);
break;

case PRINT_TREE:

print_tree(proot_node);
break;

case COUNT_NODES:

printf("\n There are %u nodes\n", count_nodes(proot_node));
break;

case FIND_DEPTH:

printf("\n Tree depth is %u\n", find_depth(proot_node));
break;

}
}

return (0);
}

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

FUNCTION ADD_NODE: The steps to add a new node to the tree are:

A. Get a string from the user.

B. If this string already exists in the tree complain and get out.

C. Have a unique string so get a free node from free node tree. If
no more, complain and get out.

D. Get space for new node's string. If no more, complain and get
out.

E. Initialize new node's string pointer and left and right child
pointers and copy user string to allocated space.

F. If this is the root (first) node, initialize the the root pointer.

G. Else if its string is less than that of the parent node, insert it
as the left child of that node.

H. Else, insert it as the right child of that node.

I. And if the new node is inserted after the last node in the list,
adjust the tail pointer accordingly.

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

void add_node(Node **pproot_node)
{
Node *pnew_node; /* ptr to new node */
Node *ploc_node; /* ptr to located node */
Node *pparent_node; /* ptr to parent node */
char *pstring; /* ptr to alloced string space */
char string[21]; /* tmp holder for node's string */

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

/*B*/ ploc_node = find_node(*pproot_node, string, &pparent_node);
if (ploc_node != NULL) {
printf("\n Node already exists in tree\n");
return;
}

/*C*/ pnew_node = get_free_node();
if (pnew_node == NULL) {
printf("\n No nodes available\n");
return;
}

/*D*/ pstring = malloc(strlen(string) + 1);
if (pstring == NULL) {
printf("\n No string space available\n");
return;
}

/*E*/ pnew_node->pstring = pstring;
strcpy(pnew_node->pstring, string);
pnew_node->pleft_child = NULL;
pnew_node->pright_child = NULL;

/*F*/ if (pparent_node == NULL) {
*pproot_node = pnew_node;
}
/*G*/ else if (strcmp(pstring, pparent_node->pstring) < 0) {
pparent_node->pleft_child = pnew_node;
}
/*H*/ else {
pparent_node->pright_child = pnew_node;
}

printf("\n Node added\n");
}

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

FUNCTION DISPLAY_NODE: The steps to display a node are:

A. Complain if list empty.

B. Get a string from the user.

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

D. Display node's string value.

E. Say whether node is the root or has a parent.

F. Say whether node has a left child.

G. Say whether node has a right child.

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

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

/*A*/ if (proot_node == NULL) {
printf("\n Tree is empty\n");
return;
}

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

/*C*/ ploc_node = find_node(proot_node, string, &pparent_node);
if (ploc_node == NULL) {
printf("\n No such node exists\n");
}
else {
/*D*/ printf("\n Node %s found\n", ploc_node->pstring);
/*E*/ if (pparent_node == NULL) {
printf(" This node is the tree root\n");
}
else {
printf(" This node's parent is %s\n",
pparent_node->pstring);
}

/*F*/ if (ploc_node->pleft_child == NULL) {
printf(" This node has no left child\n");
}
else {
printf(" This node's left child is %s\n",
ploc_node->pleft_child->pstring);
}

/*G*/ if (ploc_node->pright_child == NULL) {
printf(" This node has no right child\n");
}
else {
printf(" This node's right child is %s\n",
ploc_node->pright_child->pstring);
}
}
}

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

FUNCTION PRINT_TREE: The steps to display all nodes in the tree in
infix order are:

A. Complain if tree empty.

B. Initialize a pointer to the root of the tree.

C. Push a null sentinel on the stack.

D. Push the whole left subtree on the stack.

E. Start backtracking by popping off last node pushed.

F. Backtrack until we run into the sentinel placed on the stack in
Step B.

G. Display node's value.

H. If the current node has a right branch follow that branch and go
to Step C.

I. Pop the next node off stack.

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

void print_tree(Node *proot_node)
{
Node *pnode;
unsigned int count = 0;

/*A*/ if (proot_node == NULL) {
printf("\n Tree is empty\n");
return;
}

putchar('\n');

/*B*/ pnode = proot_node;
/*C*/ push(NULL);

/*D*/
loop: while (pnode != NULL) {
push(pnode);
pnode = pnode->pleft_child;
}

/*E*/ pnode = pop();
/*F*/ while (pnode != NULL) {
++count;
/*G*/ printf("%7u %-10s L: %-10s R: %-10s\n",
count, pnode->pstring,
(pnode->pleft_child != NULL)
? pnode->pleft_child->pstring : "-",
(pnode->pright_child != NULL)
? pnode->pright_child->pstring : "-");

/*H*/ if (pnode->pright_child != NULL) {
pnode = pnode->pright_child;
goto loop;
}
/*I*/ pnode = pop();
}
}

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

FUNCTION COUNT_NODES: The steps to count the number of nodes in the
tree are:

A. If we've reached the end of a subtree, set count to zero.

B. Otherwise, the total node count of the subtree from this node on
down is the sum of the counts of the left and right subtrees plus
1 for this (parent) node.

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

unsigned int count_nodes(Node *proot_node)
{
/*A*/ if (proot_node == NULL) {
return 0;
}

/*B*/ return (count_nodes(proot_node->pleft_child) +
count_nodes(proot_node->pright_child) + 1);
}

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

FUNCTION FIND_DEPTH: The steps to find the depth of the tree are:

A. If we've reached the end of a subtree, set count to zero.

B. Otherwise, find the depth of the left and right subtrees of this
node.

C. Return the larger of the left and right subtree depths adding 1 to
account for the current node.

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

unsigned int find_depth(Node *proot_node)
{
unsigned int left_depth;
unsigned int right_depth;

/*A*/ if (proot_node == NULL) {
return 0;
}

/*B*/ left_depth = find_depth(proot_node->pleft_child);
right_depth = find_depth(proot_node->pright_child);

/*C*/ if (left_depth >= right_depth) {
return left_depth + 1;
}
else {
return right_depth + 1;
}
}

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

FUNCTION FIND_NODE: The steps to find a node and its parent node are:

A. If the root is empty we have no tree so there is no parent and no
match.

B. If the string matches that of the root there is is no parent and
we return the root's address.

C. Decide whether to go down the root's left or right child.

D. Remember that root is the parent at this point.

E. Do steps F-H until we get to the end of the path.

F. If we have a match, save parent address and return address of
match.

G. Else, if string is less than current node's, set parent to current
and follow left child.

H. Else, set parent to current and follow right child.

I. Have exhausted search so return last node as parent and indicate
no match found.

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

Node *find_node(Node *proot_node, char *pstring,
Node **ppparent_node)
{
int comp; /* comparison flag */
Node *pnode; /* used to traverse tree */
Node *psave_node; /* used to keep track of parent */

/*A*/ if (proot_node == NULL) {
*ppparent_node = NULL;
return NULL;
}

/*B*/ if ((comp = strcmp(pstring, proot_node->pstring)) == 0) {
*ppparent_node = NULL;
return proot_node;
}

/*C*/ if (comp < 0) {
pnode = proot_node->pleft_child;
}
else {
pnode = proot_node->pright_child;
}

/*D*/ psave_node = proot_node;

/*E*/ while (pnode != NULL) {
/*F*/ if ((comp = strcmp(pstring, pnode->pstring)) == 0) {
*ppparent_node = psave_node;
return pnode;
}
/*G*/ else if (comp < 0) {
psave_node = pnode;
pnode = pnode->pleft_child;
}
/*H*/ else {
psave_node = pnode;
pnode = pnode->pright_child;
}
}

/*I*/ *ppparent_node = psave_node;
return NULL;
}



  3 Responses to “Category : Files from Magazines
Archive   : CUJ9208.ZIP
Filename : 1008108A

  1. Very nice! Thank you for this wonderful archive. I wonder why I found it only now. Long live the BBS file archives!

  2. This is so awesome! 😀 I’d be cool if you could download an entire archive of this at once, though.

  3. But one thing that puzzles me is the “mtswslnkmcjklsdlsbdmMICROSOFT” string. There is an article about it here. It is definitely worth a read: http://www.os2museum.com/wp/mtswslnk/