Smatchcube's website 🌍


Exercise 17.7

file: 7.c

file: 7_tree.c

#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include "7_tree.h"

typedef struct pair {
	Trnode * parent;
	Trnode * child;
} Pair;

static Trnode * MakeNode(const Item * pi);
static bool ToLeft(const Item * i1, const Item * i2);
static bool ToRight(const Item * i1, const Item * i2);
static void AddNode (Trnode * new_node, Trnode * root);
static void InOrder(const Trnode * root, void (* pfun)(Item item));
static Pair SeekItem(const Item * pi, const Tree * ptree);
static void DeleteNode(Trnode **ptr);
static void DeleteAllNodes(Trnode * ptr);

/* function definitions */
void InitializeTree(Tree * ptree)
{
	ptree->root = NULL;
	ptree->size = 0;
}

bool TreeIsEmpty(const Tree * ptree)
{
	if (ptree->root == NULL)
		return true;
	else
		return false;
}

bool TreeIsFull(const Tree * ptree)
{
	if (ptree->size == MAXITEMS)
		return true;
	else
		return false;
}

int TreeItemCount(const Tree * ptree)
{
	return ptree->size;
}

bool AddItem(const Item * pi, Tree * ptree)
{
	Trnode * new_node;
	if (TreeIsFull(ptree)) {
			fprintf(stderr,"Tree is full\n");
		return false;
	}
	if (SeekItem(pi, ptree).child != NULL) {
		fprintf(stderr, "Attempted to add duplicate item\n");
		return false;
	}
	new_node = MakeNode(pi);
	if (new_node == NULL) {
		fprintf(stderr, "Couldn't create node\n");
		return false;
	}
	ptree->size++;
	if (ptree->root == NULL)
		ptree->root = new_node;
	else
		AddNode(new_node,ptree->root);
	return true;
}

bool InTree(const Item * pi, const Tree * ptree)
{
	return (SeekItem(pi, ptree).child == NULL) ? false : true;
}

Item * FindItem(const Item * pi, const Tree * ptree)
{
	return &(SeekItem(pi, ptree).child->item);
}	

bool DeleteItem(const Item * pi, Tree * ptree)
{
	Pair look;
	look = SeekItem(pi, ptree);
	if (look.child == NULL)
		return false;
	if (look.parent == NULL)
		DeleteNode(&ptree->root);
	else if (look.parent->left == look.child)
		DeleteNode(&look.parent->left);
	else
		DeleteNode(&look.parent->right);
	ptree->size--;
}

void Traverse (const Tree * ptree, void (* pfun)(Item item))
{
	if (ptree != NULL)
		InOrder(ptree->root, pfun);
}

void DeleteAll(Tree * ptree)
{
	if (ptree != NULL)
		DeleteAllNodes(ptree->root);
	ptree->root = NULL;
	ptree->size = 0;
}

/* local functions */
static void InOrder(const Trnode * root, void (* pfun)(Item item))
{
	if (root != NULL) {
		InOrder(root->left, pfun);
		(*pfun)(root->item);
		InOrder(root->right, pfun);
	}
}
static void DeleteAllNodes(Trnode * root)
{
	Trnode * pright;
	if (root != NULL) {
		pright = root->right;
		DeleteAllNodes(root->left);
		free(root);
		DeleteAllNodes(pright);
	}
}
static void AddNode (Trnode * new_node, Trnode * root)
{
	if (ToLeft(&new_node->item, &root->item)) {
		if (root->left == NULL)
			root->left = new_node;
		else
			AddNode(new_node, root->left);
	}
	else if (ToRight(&new_node->item, &root->item)) {
		if (root->right == NULL)
			root->right = new_node;
		else
			AddNode(new_node, root->right);
	}
	else {
		fprintf(stderr,"location error in AddNode()\n");
		exit(1);
	}
}

static bool ToLeft(const Item * i1, const Item * i2)
{
	if (strcmp(i1->word, i2->word) < 0)
		return true;
	else
		return false;
}

static bool ToRight(const Item * i1, const Item * i2)
{
	if (strcmp(i1->word, i2->word) > 0)
		return true;
	else
		return false;
}

static Trnode * MakeNode(const Item * pi)
{
	Trnode * new_node;
	new_node = (Trnode *) malloc(sizeof(Trnode));
	if (new_node != NULL) {
		new_node->item = *pi;
		new_node->left = NULL;
		new_node->right = NULL;
	}
	return new_node;
}

static Pair SeekItem(const Item * pi, const Tree * ptree)
{
	Pair look;
	look.parent = NULL;
	look.child = ptree->root;
	if (look.child == NULL)
		return look;
	while (look.child != NULL) {
		if (ToLeft(pi, &(look.child->item))) {
			look.parent = look.child;
			look.child = look.child->left;
		}
		else if (ToRight(pi, &(look.child->item))) {
			look.parent = look.child;
			look.child = look.child->right;
		}
		else
			break;
	}
	return look;
}

static void DeleteNode(Trnode **ptr)
{
	Trnode * temp;
	if ( (*ptr)->left == NULL) {
	   temp = *ptr;
	   *ptr = (*ptr)->right;
		   free(temp);
	}
	else if ( (*ptr)->right == NULL) {
		temp = *ptr;
		*ptr = (*ptr)->left;
		free(temp);
	}
	else {
		for (temp = (*ptr)->left; temp->right != NULL;
		     temp = temp->right)
			continue;
		temp->right = (*ptr)->right;
		temp = *ptr;
		*ptr =(*ptr)->left;
		free(temp);
	}
}

file: 7_tree.h

#ifndef _TREE_H_
#define _TREE_H_
#include <stdbool.h>
#define MAX_LEN_WORD 50

typedef struct item
{
	char word[MAX_LEN_WORD];
	int occurence;
} Item;

#define MAXITEMS 10

typedef struct trnode
{
	Item item;
	struct trnode * left;
	struct trnode * right;
} Trnode;

typedef struct tree
{
	Trnode * root;
	int size;
} Tree;

/* operation: initialize a tree to empty            */
/* preconditions: ptree points to a tree            */
/* postconditions: the tree is initialized to empty */
void InitializeTree(Tree * ptree);

/* operation: determine if tree is empty             */
/* preconditions: ptree points to a tree             */
/* postconditions: function returns true if tree is  */
/*                 empty and returns false otherwise */
bool TreeIsEmpty(const Tree * ptree);

/* operation: determine if tree is full             */
/* preconditions: ptree points to a tree            */
/* postconditions: function returns true if tree is */
/*                 full and returns false otherwise */
bool TreeIsFull(const Tree * ptree);

/* operation: determine number of items in tree        */
/* preconditions: *ptree points to a tree              */
/* postconditions: function returns number of items in */
/*                 tree                                */
int TreeItemCount(const Tree * ptree);

/* operation: add an item to a tree                    */
/* preconditions: pi is address of item to be added    */
/*                ptree points to an initialized tree  */
/* postconditions: if possible, function adds item to  */
/*                 tree and returns true; otherwise,   */
/*                 the function returns false          */
bool AddItem(const Item * pi, Tree * ptree);

/* operation: find an item in a tree                    */
/* preconditions: pi points to an item                  */
/*                ptree points to an initialized tree   */
/* postconditions: function returns true if item is in  */
/*                 tree and returns false otherwise     */
bool InTree(const Item * pi, const Tree * ptree);

/* operation: delete an item from a tree                */
/* preconditions: pi is address of item to be deleted   */
/* ptree points to an initialized tree                  */
/* postconditions: if possible, function deletes item   */
/*                 from tree and returns true;          */
/*                 otherwise the function returns false */
bool DeleteItem(const Item * pi, Tree * ptree);

/* operation: apply a function to each item in          */
/*            the tree                                  */
/* preconditions: ptree points to a tree                */
/*                pfun points to a function that takes  */
/*                an Item argument and has no return    */
/*                value                                 */
/* postcondition: the function pointed to by pfun is    */
/*                executed once for each item in tree   */
void Traverse (const Tree * ptree, void (* pfun)(Item item));

/* operation: delete everything from a tree           */
/* preconditions: ptree points to an initialized tree */
/* postconditions: tree is empty                      */
void DeleteAll(Tree * ptree);

/* operation:     find the location of an item in a tree
 * precondition:  pi points to an item
 *                ptree points to an initialized tree
 * postconditions: a pointer to the item to corresponding 
 *                 to the item poited by pi is returned
 *                 (in this exercise we search item with specific name)
 *                 return NULL pointer if no match is found
 */
Item * FindItem(const Item * pi, const Tree * ptree);

#endif