1 #ifndef TREE_H_ 2 #define TREE_H_ 3  4 #include <stdbool.h> 5 #define STRSIZE 32 6 #define TREEMAX 10 7  8 typedef struct item 9 {10     char petname[STRSIZE];11     char petkind[STRSIZE];12 } Item;13 14 typedef struct node15 {16     Item item;17     struct node * left;18     struct node * right;19 } Node;20 21 typedef struct tree22 {23     Node * root;24     int size;25 } Tree;26 27 void InitializeTree(Tree * ptree);28 29 bool TreeIsEmpty(const Tree * ptree);30 31 bool TreeIsFull(const Tree * ptree);32 33 int TreeItemCount(const Tree * ptree);34 35 bool AddItem(const Item * pitem, Tree * ptree);36 37 bool DeleteItem(const Item * pitem, Tree * ptree);38 39 bool CheckItem(const Item * pitem, const Tree * ptree);40 41 void Traverse(const Tree * ptree, void (* pfun)(Item item));42 43 void DeleteAll(Tree * ptree);44 45 #endif

  1 #include <stdio.h>  2 #include <string.h>  3 #include "tree.h"  4   5 char menu(void);  6 void addpet(Tree * ptree);  7 void deletepet(Tree * ptree);  8 void checkpet(const Tree * ptree);  9 void numberpets(const Tree * ptree); 10 void showpets(const Tree * ptree); 11 void printitem(Item item); 12  13 int main(void) 14 { 15     Tree pets; 16  17     InitializeTree(&pets); 18  19     char choice; 20     while(‘q‘ != (choice = menu())) 21     { 22         switch(choice) 23         { 24             case ‘a‘: addpet(&pets); 25                       break; 26             case ‘d‘: deletepet(&pets); 27                       break; 28             case ‘c‘: checkpet(&pets); 29                       break; 30             case ‘n‘: numberpets(&pets); 31                       break; 32             case ‘s‘: showpets(&pets); 33                       break; 34             default:  printf("Unknow command!\n"); 35                       break; 36         } 37     } 38     DeleteAll(&pets); 39     printf("Bye!\n"); 40  41     return 0; 42 } 43  44 void eatline(void) 45 { 46     while(‘\n‘ != getchar()) 47         continue; 48 } 49  50 char menu(void) 51 { 52     char ch; 53  54     printf("<a. add    d. delete    c. check    n. number    s. show>\n"); 55     while(EOF != (ch = getchar())) 56     { 57         eatline(); 58         if(NULL == strchr("adcns", ch)) 59         { 60             printf("invalid input!\n"); 61             printf("<a. add    d. delete    c. check    n. number    s. show>\n"); 62             continue; 63         } 64         else 65             break; 66     } 67     if(EOF == ch) 68         ch = ‘q‘; 69  70     return ch; 71 } 72  73 void addpet(Tree * ptree) 74 { 75     if(TreeIsFull(ptree))    76     { 77         fprintf(stderr, "addpet error: tree is full!\n"); 78         return; 79     } 80  81     Item temp; 82  83     printf("Enter pet name to add: "); 84     gets(temp.petname); 85     printf("Enter pet kind to add: "); 86     gets(temp.petkind); 87     AddItem(&temp, ptree); 88 } 89  90 void deletepet(Tree * ptree) 91 { 92     Item temp; 93  94     if(TreeIsEmpty(ptree)) 95     { 96         fprintf(stderr, "deletepet error: tree is empty!\n"); 97         return; 98     } 99 100     printf("Enter pet name to delete: ");101     gets(temp.petname);102     printf("Enter pet kind to delete: ");103     gets(temp.petkind);104     printf("<%s - %s> ", temp.petname, temp.petkind);105     if(DeleteItem(&temp, ptree))106         printf("delete success.\n");107     else108         printf("delete failed.\n");109 }110 111 void checkpet(const Tree * ptree)112 {113     if(TreeIsEmpty(ptree))114     {115         printf("Tree is empty!\n");116         return;117     }118 119     Item temp;120 121     printf("Enter pet name to check: ");122     gets(temp.petname);123     printf("Enter pet kind to check: ");124     gets(temp.petkind);125     printf("<%s - %s> ", temp.petname, temp.petkind);126     if(CheckItem(&temp, ptree))127         printf("check true.\n");128     else129         printf("check false.\n");130 }131 132 void numberpets(const Tree * ptree)133 {134     printf("pets count: %d\n", TreeItemCount(ptree));135 }136 137 void showpets(const Tree * ptree)138 {139     if(TreeIsEmpty(ptree))140         printf("Tree is empty.\n");141     else142         Traverse(ptree, printitem);143 }144 145 void printitem(Item item)146 {147     printf("Name: %s, Kind: %s\n", item.petname, item.petkind);148 }

  1 #include <stdio.h>  2 #include <stdlib.h>  3 #include "tree.h"  4   5 typedef struct pair  6 {  7     Node * parent;  8     Node * self;  9 } Pair; 10  11  12  13 static Pair SeekItem(const Item * pitem, const Tree * ptree); 14 static void InOrder(const Node * root, void (* pfun)(Item item)); 15 static void DeleteNode(Node ** ppnode); 16 static bool ToLeft(const Item * pitem, const Item * pitem2); 17 static bool ToRight(const Item * pitem, const Item * pitem2); 18 static void DeleteAllNodes(Node * root); 19 static void AddNode(Node * pnew, Node * root); 20 static Node * CreateNode(const Item * pitem); 21  22  23 void InitializeTree(Tree * ptree) 24 { 25     ptree->root = NULL; 26     ptree->size = 0; 27 } 28  29 bool TreeIsEmpty(const Tree * ptree) 30 { 31     return 0 == ptree->size; 32 } 33  34 bool TreeIsFull(const Tree * ptree) 35 { 36     return TREEMAX == ptree->size; 37 } 38  39 int TreeItemCount(const Tree * ptree) 40 { 41     return ptree->size; 42 } 43  44 bool AddItem(const Item * pitem, Tree * ptree) 45 { 46     if(TreeIsFull(ptree)) 47     { 48         fprintf(stderr, "Tree is full"); 49         return false; 50     } 51     if(NULL != SeekItem(pitem, ptree).self) 52     { 53         fprintf(stderr, "Add item error: duplicate item.\n"); 54         return false; 55     } 56  57     Node * pnew; 58     pnew = CreateNode(pitem); 59     if(NULL == pnew) 60     { 61         fprintf(stderr, "Create node failed!\n"); 62         return false; 63     } 64  65     if(NULL == ptree->root) 66         ptree->root = pnew; 67     else 68         AddNode(pnew, ptree->root); 69  70     ptree->size++; 71  72     return true; 73 } 74  75 bool DeleteItem(const Item * pitem, Tree * ptree) 76 { 77     Pair look; 78  79     look = SeekItem(pitem, ptree); 80     if(NULL == look.self) 81         return false; 82  83     if(NULL == look.parent) 84         DeleteNode(&ptree->root); 85     else if(look.parent->left == look.self) 86         DeleteNode(&look.parent->left); 87     else 88         DeleteNode(&look.parent->right); 89  90     ptree->size--; 91  92     return true; 93 } 94  95 bool CheckItem(const Item * pitem, const Tree * ptree) 96 { 97     return (NULL == SeekItem(pitem, ptree).self) ? false : true; 98 } 99 100 void Traverse(const Tree * ptree, void (* pfun)(Item item))101 {102     if(NULL != ptree)103         InOrder(ptree->root, pfun);104 }105 106 void DeleteAll(Tree * ptree)107 {108     if(NULL != ptree)109         DeleteAllNodes(ptree->root);110     ptree->root = NULL;111     ptree->size = 0;112 }113 114 static void InOrder(const Node * root, void (* pfun)(Item item))115 {116     if(NULL != root)117     {118         InOrder(root->left, pfun);119         (*pfun)(root->item);120         InOrder(root->right, pfun);121     }122 }123 124 static void DeleteAllNodes(Node * root)125 {126     Node * pleft, * pright;127     128 129     if(NULL != root)130     {131         pleft = root->left;132         pright = root->right;133 134         DeleteAllNodes(pleft);135         free(root);136         DeleteAllNodes(pright);137     }138 }139 140 static void AddNode(Node * pnew, Node * root)141 {142     if(ToLeft(&pnew->item, &root->item))143     {144         if(NULL == root->left)145             root->left = pnew;146         else147             AddNode(pnew, root->left);148     }149     else if(ToRight(&pnew->item, &root->item))150     {151         if(NULL == root->right)152             root->right = pnew;153         else154             AddNode(pnew, root->right);155     }156     else157     {158         fprintf(stderr, "location error in AddNode()\n");159         exit(1);160     }161 }162 163 static bool ToLeft(const Item * pitem, const Item * pitem2)164 {165     int comp;166 167     if((comp = strcmp(pitem->petname, pitem2->petname)) < 0)168         return true;169     else if(0 == comp && strcmp(pitem->petkind, pitem2->petkind) < 0)170         return true;171     else172         return false;173 }174 175 static bool ToRight(const Item * pitem, const Item * pitem2)176 {177     int comp;178 179     if((comp = strcmp(pitem->petname, pitem2->petname)) > 0)180         return true;181     else if(0 == comp && strcmp(pitem->petkind, pitem2->petkind) > 0)182         return true;183     else184         return false;185 }186 187 static Node * CreateNode(const Item * pitem)188 {189     Node * pnew;190 191     pnew = (Node *)malloc(sizeof(Node));192     if(NULL != pnew)193     {194        pnew->item = *pitem;195        pnew->left = NULL;196        pnew->right = NULL;197     }198 199     return pnew;200 }201 202 static Pair SeekItem(const Item * pitem, const Tree * ptree)203 {204     Pair look;205     look.parent = NULL;206     look.self = ptree->root;207 208     if(NULL == look.self)209         return look;210 211     while(NULL != look.self)212     {213         if(ToLeft(pitem, &(look.self->item)))214         {215             look.parent = look.self;216             look.self = look.self->left;217         }218         else if(ToRight(pitem, &(look.self->item)))219         {220             look.parent = look.self;221             look.self = look.self->right;222         }223         else224             break;225     }226 227     return look;228 }229 230 static void DeleteNode(Node ** ppnode)231 {232     Node * temp;233 234     printf("%s\n", (*ppnode)->item.petname);235 236     if(NULL == (*ppnode)->left)237     {238         temp = *ppnode;239         *ppnode = (*ppnode)->right;240         free(temp);241     }242     else if(NULL == (*ppnode)->right)243     {244         temp = *ppnode;245         *ppnode = (*ppnode)->left;246         free(temp);247     }248     else249     {250         for(temp = (*ppnode)->left; NULL != temp->right; temp = temp->right)251             continue;252         temp->right = (*ppnode)->right;253         temp = *ppnode;254         *ppnode = (*ppnode)->left;255         free(temp);256     }257 }