OntarioToronto

QuebecQuebec_City

Saskatchewan Regina

Manitoba Winnipeg

AlbertaEdmonton

British_Columbia Victoria

Nova_ScotiaHalifax

New_Brunswick Frederickton

Prince_Edward_Island Charlottetown

Northwest_TerritoryYellowknife

Yukon_TerritoryWhitehorse

Newfoundland NO_CAPITAL

Just create a file called avl.dat and put these inside.

//**************************************

//     

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

/* Jason F. BoxallCSC 3304/24/97AVL Tree Program */

*/

/* Special thanks to Andy Beal who greatly assisted in the insertion and*/

/*deletion routines utilized here. */

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

/* Preprocessor Directives */

#include 

#include 

#include 

#include 

#include 

#define MAXHEIGHT 5

#define NAMELENGTH 22

#define TIMEOUT 90000000

#define EGO message()

#define PAUSE sleep()

/* AVL Tree Structure template */

    typedef struct tree {

    char name1[NAMELENGTH];

    char name2[NAMELENGTH];

    int id;

    int balance;

    struct tree *leftPtr;

    struct tree *rightPtr;

} TREE;

typedef TREE *TREEPTR;/* pointer to the AVL tree */

/* Global Variables */

enum {FALSE, TRUE};

enum {RIGHT = -1, EVEN, LEFT};

int searchResult = FALSE;

/* Function Declarations */

int read_file(TREEPTR *, int);

int build_tree(TREEPTR *, char *, char *, int *);

TREEPTR get_node(void);

TREEPTR fill_node(TREEPTR, char *, char *, int);

TREEPTR tree_search(TREEPTR, char *);

int insert_avltree(TREEPTR *, TREEPTR);

int insert_avl(TREEPTR *, TREEPTR, int *);

void rotate_right(TREEPTR *);

void rotate_left(TREEPTR *);

int calc_nodes(int);

void menu(TREEPTR *, int *);

void display_info();

void inorder(TREEPTR, int);

void preorder(TREEPTR, int);

void postorder(TREEPTR, int);

void free_tree(TREEPTR);

int delete_avlNode(TREEPTR *, TREEPTR);

int delete_avl(TREEPTR *, TREEPTR, int *);

void del_both_children(TREEPTR *, TREEPTR *, int *);

void balance_right(TREEPTR *, int *);

void balance_left(TREEPTR *, int *);

void message();

void sleep();

void seek_out(TREEPTR, char *);

void balance_checker(TREEPTR, char *);

int count_height(TREEPTR, char *, int);

/* Begin main function */

void main()

    {

    TREEPTR root = NULL;

    int totalNodes = 0;

    EGO;

    totalNodes = read_file(&root, totalNodes);

    menu(&root, &totalNodes);

}

/* Begin read_file function */

int read_file(TREEPTR *root, int totalNodes)

    {

    FILE *fin=fopen("avl.dat","r");

    char province[NAMELENGTH], capital[NAMELENGTH];

    int insertedOK=FALSE;

        while(!feof(fin)){

        fscanf(fin,"%s%s", province, capital);

        insertedOK=build_tree(root, province, capital, &totalNodes);

    }

    if(insertedOK == FALSE)

    puts("Error filling tree!");

    return totalNodes;

}

/* Begin build_tree function */

int build_tree(TREEPTR *root, char str1[], char str2[], int *total)

    {

    TREEPTR newNode1, parent = *root;

    int totalNodes = *total, insertedOK, availableNodes = calc_nodes(MAXHEIGHT)-1;

    if(!(totalNodes < availableNodes)){ /* Is a node available in tree? */

    printf("\nThe tree is full! delete a node first.\a\n");

    return FALSE;

}

if(tree_search(parent, str1)){ /* Check for duplicate entry */

printf("\nThe province is a duplicate item. No node added.\a\n");

return FALSE;

}

if(tree_search(parent, str2)){ /* Check for duplicate entry */

printf("\nThe capital is a duplicate item. No node added.\a\n");

return FALSE;

}

if(!(newNode1 = get_node()))/* no memory */

return FALSE;

else{ /* fill & insert 2 nodes, #1 w/province 1st, #2 w/capital 1st */

newNode1 = fill_node(newNode1, str1, str2, ++totalNodes);

if(insertedOK = insert_avltree(&parent, newNode1)){

*total = totalNodes;

*root = parent;

}

else{

printf("Node insertion problem on province.\a\n");

return FALSE;

}

}

return insertedOK;

}

/* Begin get_node function */

TREEPTR get_node()

{

TREEPTR newNode = (TREEPTR)malloc(sizeof(TREE));

if(!newNode)

printf("No memory available. Node not added.\a\n");

return newNode;

}

/* Begin fill_node function */

TREEPTR fill_node(TREEPTR newNode, char str1[], char str2[], int number)

{

strcpy(newNode->name1, str1);

strcpy(newNode->name2, str2);

newNode->id = number;

newNode->balance = EVEN;

newNode->leftPtr = NULL;

newNode->rightPtr = NULL;

return newNode;

}

/* Begin tree_search function */

TREEPTR tree_search(TREEPTR root, char string[])

{

int target = 1;

while(root && (target != 0)){

target = strcmp(string, root->name1);

if(target < 0)

root = root->leftPtr;

if(target > 0)

root = root->rightPtr;

}

return root;

}

/* Begin insert_avltree function */

int insert_avltree(TREEPTR *root, TREEPTR newNode)

{

int insertedOK = FALSE;

return (insertedOK = insert_avl(root, newNode, &insertedOK));

}

/* Begin insert_avl */

int insert_avl(TREEPTR *root, TREEPTR newNode, int *insertedok)

{

if(*root == NULL){

*root = newNode;

*insertedok = TRUE;

}

else if(strcmp(newNode->name1, (*root)->name1) < 0){/* go to left subtree */

insert_avl(&(*root)->leftPtr, newNode, insertedok);

if (*insertedok)

switch((*root)->balance){

case LEFT: rotate_left(root);

*insertedok = FALSE;

break;

case EVEN: (*root)->balance = LEFT;

break;

case RIGHT: (*root)->balance = EVEN;

*insertedok = FALSE;

}/* end switch */

} /* end else if */

else{ /* go to right subtree */

insert_avl(&(*root)->rightPtr, newNode, insertedok);

if(*insertedok)

switch((*root)->balance){

case LEFT: (*root)->balance = EVEN;

*insertedok = FALSE;

break;

case EVEN: (*root)->balance = RIGHT;

break;

case RIGHT: rotate_right(root);

*insertedok = FALSE;

break;

}/* end switch */

}/* end else */

return TRUE;

}

/* Begin rotate_right function */

void rotate_right(TREEPTR *root)

{

TREEPTR ptr2, ptr3;

ptr2 = (*root)->rightPtr;

if(ptr2->balance == RIGHT){/*rotate once */

(*root)->rightPtr = ptr2->leftPtr;

ptr2->leftPtr = *root;

(*root)->balance = EVEN;

*root = ptr2;

}

else{/* rotate twice */

ptr3 = ptr2->leftPtr;

ptr2->leftPtr = ptr3->rightPtr;

ptr3->rightPtr = ptr2;

(*root)->rightPtr = ptr3->leftPtr;

ptr3->leftPtr = *root;

if(ptr3->balance == LEFT)

ptr2->balance = RIGHT;

else

ptr2->balance = EVEN;

if(ptr3->balance == RIGHT)

(*root)->balance = LEFT;

else

(*root)->balance = EVEN;

*root = ptr3;

}/* end else */

(*root)->balance = EVEN;

}

/* Begin rotate_left function */

void rotate_left(TREEPTR *root)

{

TREEPTR ptr2, ptr3;

ptr2 = (*root)->leftPtr;

if(ptr2->balance == LEFT){/* rotate once */

(*root)->leftPtr = ptr2->rightPtr;

ptr2->rightPtr = *root;

(*root)->balance = EVEN;

(*root) = ptr2;

}

else{/* rotate twice */

ptr3 = ptr2->rightPtr;

ptr2->rightPtr = ptr3->leftPtr;

ptr3->leftPtr = ptr2;

(*root)->leftPtr = ptr3->rightPtr;

ptr3->rightPtr = *root;

if(ptr3->balance == RIGHT)

ptr2->balance = LEFT;

else

ptr2->balance = EVEN;

if(ptr3->balance == LEFT)

(*root)->balance = RIGHT;

else

(*root)->balance = EVEN;

*root = ptr3;

}

(*root)->balance = EVEN;

}

/* Begin calc_nodes function */

int calc_nodes(int levels)

{

float y = (float)levels;

int totalNodes;

totalNodes = (int)pow(2.0, y)-1.0;

return totalNodes;

}

/* Begin menu function */

void menu(TREEPTR *root, int *total)

{

TREEPTR targetNode;

int choice, count, result, selection, insertedOK, delOK, totalNodes=*total;

char newCapital[NAMELENGTH], newProvince[NAMELENGTH];

char target[NAMELENGTH];

display_info();

while((scanf("%d",&choice)!=9)){

switch(choice){

case 1:/* Traverse AVL inorder */

clrscr();

puts("");

puts("--------------------------------------------------");

puts(" Inorder Traversal Menu ");

puts("--------------------------------------------------");

printf("\n");

printf("\t 1 Capitals\n");

printf("\t 2 Provinces\n");

printf("\t 3 Capitals, provinces\n");

printf("\t 4 Provinces, capitals\n");

printf("\n");

printf("Enter your selection: ");

flushall();

scanf("%d", &selection);

if(selection!=1&&selection!=2&&selection!=3&&selection!=4)

printf("\n\nInvalid selection!\a");

else{

clrscr();

puts("");

inorder(*root, selection);

PAUSE;

}

PAUSE;

display_info();

break;

case 2:/* Traverse AVL in preorder */

clrscr();

puts("");

puts("--------------------------------------------------");

puts(" Preorder Traversal Menu ");

puts("--------------------------------------------------");

printf("\n");

printf("\t 1 Capitals\n");

printf("\t 2 Provinces\n");

printf("\t 3 Capitals, provinces\n");

printf("\t 4 Provinces, capitals\n");

printf("\n");

printf("Enter your selection: ");

flushall();

scanf("%d", &selection);

if(selection!=1&&selection!=2&&selection!=3&&selection!=4)

printf("\n\nInvalid selection!\a");

else{

clrscr();

puts("");

preorder(*root, selection);

PAUSE;

}

PAUSE;

display_info();

break;

case 3:/* Traverse AVL in postorder */

clrscr();

puts("");

puts("--------------------------------------------------");

puts(" Postorder Traversal Menu ");

puts("--------------------------------------------------");

printf("\n");

printf("\t 1 Capitals\n");

printf("\t 2 Provinces\n");

printf("\t 3 Capitals, provinces\n");

printf("\t 4 Provinces, capitals\n");

printf("\n");

printf("Enter your selection: ");

flushall();

scanf("%d", &selection);

if(selection!=1&&selection!=2&&selection!=3&&selection!=4)

printf("\n\nInvalid selection!\a");

else{

clrscr();

puts("");

postorder(*root, selection);

PAUSE;

}

PAUSE;

display_info();

break;

case 4:/* Search AVL for a node */

clrscr();

printf("\n\nEnter province or capital to search for: ");

flushall();

scanf("%s", target);

seek_out(*root, target);

if(searchResult==FALSE) printf("\nTarget not in tree!\a\n");

PAUSE;

display_info();

break;

case 5: /* Determine balance factor of a node */

searchResult=FALSE;

clrscr();

printf("\n\nEnter province or capital to determine balance factor of: ");

flushall();

scanf("%s", target);

balance_checker(*root, target);

if(searchResult==FALSE) printf("\nTarget not in tree!\a\n");

PAUSE; PAUSE;

display_info();

break;

case 6:/* Count height of a given node */

count=0;

clrscr();

printf("\n\nEnter province or capital to count height of: ");

flushall();

scanf("%s", target);

result=count_height(*root, target, count);

if(result==-1) printf("\nTarget does not exist.\a");

else

printf("\n%s has a height of %2d.", target, result-1);

PAUSE;

display_info();

break;

case 7:/* Insert node into BST */

clrscr();

printf("\nEnter new province to insert into AVL tree: ");

flushall(); /* Clear input buffer */

scanf("%s", newProvince);

puts("");

printf("Enter new capital to insert into AVL tree: ");

flushall(); /* Clear input buffer */

scanf("%s", newCapital);

insertedOK=build_tree(root, newProvince, newCapital, &totalNodes);

if(insertedOK==FALSE) printf("\nError inserting new items!\a\n");

else printf("\nThe new province and capital were inserted OK.\n");

PAUSE;

display_info();

break;

case 8:/* delete node from AVL tree */

clrscr();

printf("\n\nDeletion is done by province ONLY.\n");

printf("\nEnter province to delete: ");

flushall();

scanf("%s", target);

targetNode=tree_search(*root, target);

if(!targetNode) printf("\nYour selection is not in tree.\a\n");

else{

delOK=delete_avlNode(root, targetNode);

if(delOK==TRUE){

--totalNodes;

printf("\nNode deleted.");

}

else

printf("\nError deleting node.\a\n");

}

PAUSE;

display_info();

break;

case 9:

clrscr();

printf("\n\n\nThe total nodes in the tree are %3d.", totalNodes);

PAUSE;

display_info();

break;

case 0: /* Au Revoir! */

clrscr();

printf("\n\n\n\n\n\n\t\tHave a nice day. Goodbye.");

printf("\n\n\t\tNote: Hit to return to DOS prompt.");

free_tree(*root);

break;

default: /* Let user know they made an invalid choice */

clrscr();

printf("\n\n\n\n\n\n\t\t\tInvalid selection");

PAUSE;

display_info();

break;

}/* End switch */

} /* End while */

}

/* Begin display_info function */

void display_info()

{

clrscr();

printf("\n\n");

puts("--------------------------------------------------");

puts("AVL Tree Menu Options ");

puts("--------------------------------------------------");

printf("\n");

printf("\t 1 Display inorder traversal\n");

printf("\t 2 Display preorder traversal\n");

printf("\t 3 Display postorder traversal\n");

printf("\t 4 Search for a given node\n");

printf("\t 5 Determine balance factor of a given node\n");

printf("\t 6 Count height of a given node\n");

printf("\t 7 Insert a node onto the tree\n");

printf("\t 8 delete a node from the tree\n");

printf("\t 9 Count total nodes in the tree\n");

printf("\t 0 Quit program\n");

printf("\n");

printf("Enter your selection: ");

}

/* Begin inorder function */

void inorder(TREEPTR root, int choice)

{

if(root->leftPtr!=NULL) inorder(root->leftPtr, choice);

if(choice==1) printf("%s\n",root->name2);

if(choice==2) printf("%s\n",root->name1);

if(choice==3) printf("%s %s\n",root->name2,root->name1);

if(choice==4) printf("%s %s\n",root->name1,root->name2);

if(root->rightPtr!=NULL) inorder(root->rightPtr, choice);

}

/* Begin preorder function */

void preorder(TREEPTR root, int choice)

{

if(choice==1) printf("%s\n",root->name2);

if(choice==2) printf("%s\n",root->name1);

if(choice==3) printf("%s %s\n",root->name2,root->name1);

if(choice==4) printf("%s %s\n",root->name1,root->name2);

if(root->leftPtr!=NULL) preorder(root->leftPtr, choice);

if(root->rightPtr!=NULL) preorder(root->rightPtr, choice);

}

/* Begin postorder function */

void postorder(TREEPTR root, int choice)

{

if(root->leftPtr!=NULL) postorder(root->leftPtr, choice);

if(root->rightPtr!=NULL) postorder(root->rightPtr, choice);

if(choice==1) printf("%s\n",root->name2);

if(choice==2) printf("%s\n",root->name1);

if(choice==3) printf("%s %s\n",root->name2,root->name1);

if(choice==4) printf("%s %s\n",root->name1,root->name2);

}

/* Begin free_tree function */

void free_tree(TREEPTR root)

{

if(root!=NULL){/* As long as root isn't null, recursively */

free_tree(root->leftPtr); /* travel tree in postorder freeing the*/

free_tree(root->rightPtr); /* nodes as you go.*/

free(root);

}

}

/* Begin delete_avlNode function */

int delete_avlNode(TREEPTR *root, TREEPTR avlNode)

{

int delOK = FALSE;

delOK = delete_avl(root, avlNode, &delOK);

return delOK;

}

/* Begin delete_avl function */

int delete_avl(TREEPTR *root, TREEPTR avlNode, int *delOK)

{

TREEPTR ptr;

int cmpResult;

cmpResult = strcmp(avlNode->name1, (*root)->name1);

if((*root) == NULL)

*delOK = FALSE;

else if(cmpResult < 0){/* go to left subtree */

delete_avl(&(*root)->leftPtr, avlNode, delOK);

if(*delOK)

balance_right(root, delOK);

/* *delOK = TRUE; ADDED this LINE 4-10-96 */

}

else if(cmpResult > 0){/* go to right subtree */

delete_avl(&(*root)->rightPtr, avlNode, delOK);

if(*delOK)

balance_left(root, delOK);

/* *delOK = TRUE; ADDED this LINE 4-10-96 */

}

else{

ptr = *root;/* node found */

if((*root)->rightPtr == NULL){

(*root) = (*root)->leftPtr;

*delOK = TRUE;

free(ptr);

}

else if((*root)->leftPtr == NULL){

(*root) = (*root)->rightPtr;

*delOK = TRUE;

free(ptr);

}

else{/* node has right and left child */

del_both_children(root, &(*root)->leftPtr, delOK);

if(*delOK)

balance_right(root, delOK);

*delOK = TRUE;

/*free((*root)->leftPtr); this code is an error in the book*/

}

}

return *delOK; /* Return status of delete operation */

}

/* Begin del_both_children function */

void del_both_children(TREEPTR *root, TREEPTR *ptr, int *delOK)

{

TREEPTR temp;

if((*ptr)->rightPtr == NULL){

strcpy((*root)->name1, (*ptr)->name1);

strcpy((*root)->name2, (*ptr)->name2);

(*root)->id = (*ptr)->id;

temp = *ptr;

if((*ptr)->leftPtr == NULL)

*ptr = NULL;

else

*ptr = (*ptr)->leftPtr;

free(temp);

*delOK = TRUE;

}

else{

del_both_children(root, &(*ptr)->rightPtr, delOK);

if(*delOK)

balance_left(ptr, delOK);

}

}

/* Begin balance_right function */

void balance_right(TREEPTR *root, int *delOK)

{

TREEPTR ptr2, ptr3;

int bal2, bal3;

switch((*root)->balance){

case LEFT: (*root)->balance = EVEN;

break;

case EVEN: (*root)->balance = RIGHT;

*delOK = FALSE;

break;

case RIGHT: ptr2 = (*root)->rightPtr;

bal2 = ptr2->balance;

if(bal2 != LEFT){

(*root)->rightPtr = ptr2->leftPtr;

ptr2->leftPtr = *root;

if(bal2 == EVEN){

(*root)->balance = RIGHT;

ptr2->balance = LEFT;

*delOK = FALSE;

}

else{

(*root)->balance = EVEN;

ptr2->balance = EVEN;

}

*root = ptr2;

}

else{

ptr3 = ptr2->leftPtr;

bal3 = ptr3->balance;

ptr2->leftPtr = ptr3->rightPtr;

ptr3->rightPtr = ptr2;

(*root)->rightPtr = ptr3->leftPtr;

ptr3->leftPtr = *root;

if(bal3 == LEFT)

ptr2->balance = RIGHT;

else

ptr2->balance = EVEN;

if(bal3 == RIGHT)

(*root)->balance = LEFT;

else

(*root)->balance = EVEN;

*root = ptr3;

ptr3->balance = EVEN;

}

}

}

/* Begin balance_left function */

void balance_left(TREEPTR *root, int *delOK)

{

TREEPTR ptr2, ptr3;

int bal2, bal3;

switch((*root)->balance){

case RIGHT: (*root)->balance = EVEN;

break;

case EVEN: (*root)->balance = LEFT;

*delOK = FALSE;

break;

case LEFT: ptr2 = (*root)->leftPtr;

bal2 = ptr2->balance;

if(bal2 != RIGHT){

(*root)->leftPtr = ptr2->rightPtr;

ptr2->rightPtr = *root;

if(bal2 == EVEN){

(*root)->balance = LEFT;

ptr2->balance = RIGHT;

*delOK = FALSE;

}

else{

(*root)->balance = EVEN;

ptr2->balance = EVEN;

}

*root = ptr2;

}

else{

ptr3 = ptr2->rightPtr;

bal3 = ptr3->balance;

ptr2->rightPtr = ptr3->leftPtr;

ptr3->leftPtr = ptr2;

(*root)->leftPtr = ptr3->rightPtr;

ptr3->rightPtr = *root;

if(bal3 == RIGHT)

ptr2->balance = LEFT;

else

ptr2->balance = EVEN;

if(bal3 == LEFT)

(*root)->balance = RIGHT;

else

(*root)->balance = EVEN;

*root = ptr3;

ptr3->balance = EVEN;

}

}

}

/* Begin message function */

void message()

{

int x,y;

for(x=0;x<3;++x){

clrscr();

printf("\n\n\n\n\n\n\n\n");

printf("\t\t\tAnother Masterpiece By:\n\n");

for(y=0;y<50000000;++y);

printf("\t\t\tJason Boxall\n");

for(y=0;y<50000000;++y);

}

clrscr();

}

/* Begin sleep function */

void sleep()

{

int x;

for(x=0;xleftPtr!=NULL) seek_out(root->leftPtr, target);

if(strcmp(target, root->name1)==0 || strcmp(target, root->name2)==0){

printf("\n%s, %s exists in the AVL tree.", root->name2, root->name1);

searchResult = TRUE;

}

if(root->rightPtr!=NULL) seek_out(root->rightPtr, target);

}

/* Begin balance_checker function */

void balance_checker(TREEPTR root, char target[])

{

if(root->leftPtr!=NULL) balance_checker(root->leftPtr, target);

if(strcmp(target, root->name1)==0 || strcmp(target, root->name2)==0){

if(root->balance == -1){

printf("\nThe balance factor of %s, %s is -1.\n",

root->name2, root->name1);

printf("\nThis means it has a right tilt.");

}

else if(root->balance == 0)

printf("\nThe balance factor of %s, %s is 0, meaning it is even.\n",

root->name2, root->name1);

else{

printf("\nThe balance factor of %s, %s is 1.\n",

root->name2, root->name1);

printf("\nThis means it has a right tilt.");

}

searchResult = TRUE;

}

if(root->rightPtr!=NULL) balance_checker(root->rightPtr, target);

}

/* Begin count_height function */

int count_height(TREEPTR root, char target[], int count)

{

if(root==NULL) return -1;/* Target doesn't exist */

count++;

if(strcmp(target, root->name1)==0 || strcmp(target, root->name2)==0)

return count; /* Target found */

if(strcmp(target, root->name1)>0 || strcmp(target, root->name2)>0)

return count_height(root->rightPtr, target, count);

if(strcmp(target, root->name1)<0 || strcmp(target, root->name2)<0)

return count_height(root->leftPtr, target, count);

return 8675309; /* Jenny, Jenny */

}