利用c语言实现一颗二叉树的功能

#include<stdio.h> #include<string.h> #include<stdlib.h> #include<conio.h> #include"tree.h" int max=10; void InitTree(Tree *t) { t->root=NULL; t->size=0; } int TreeIsEmpty(Tree *t) { if(t->size==0) return 1; else return 0; } int TreeIsFull(Tree *t) { if(t->size==max) return 1; else return 0; } int TreeItemCount(Tree *t) { return t->size; } static int Toleft( const Item *s1,const Item *s2) { int i; if((i=strcmp(s1->petname,s2->petname))<0) return 1; else if(i==0 && strcmp(s1->petkind,s2->petkind)<0) return 1; else return 0; } static int ToRight(const Item *s1,const Item *s2) { int i; if((i=strcmp(s1->petname,s2->petname))>0) return 1; else if(i==0 && strcmp(s1->petkind,s2->petkind)>0) return 1; else return 0; } static void AddNode(Node *p,Node *root) { if(Toleft(&p->item,&root->item)) { if(root->left==NULL)//空树 root->left=p; else AddNode(p,root->left); //递归调用 } else if (ToRight(&p->item,&root->item)) { if(root->right==NULL) root->right=p; else AddNode(p,root->right); } else { fprintf(stderr,"fail to add item!\n"); exit(1); } } int AddItem(Tree *t,const Item *p) { Node *newpet; if(TreeIsFull(t)) { fprintf(stderr,"tree is full!\n"); return 0; } //seekitem(t,p); newpet=(Node*)malloc(sizeof(Node)); if(newpet==NULL) { printf("fail to allacate memory!\n"); exit(1); } newpet->item=*p; newpet->left=NULL; newpet->right=NULL; t->size++; //printf("%d\n",t->size); if(t->root==NULL) t->root=newpet; else AddNode(newpet,t->root); return 1; } Pair SearchTree(Tree *t,const Item *p) { Pair look; look.parent=NULL; look.self=t->root; if(look.self==NULL) return look;//此时返回则look为null while(look.self!=NULL) { if(Toleft(p,&look.self->item)) { look.parent=look.self;//保存父指针 look.self=look.self->left; } else if(ToRight(p,&look.self->item)) { look.parent=look.self; look.self=look.self->right; } else break; } return look; } //中序遍历，先左再根再又 static void inorder(Node *root) { if(root!=NULL) { inorder(root->left); // (*printfun)(root->item); printf("%s---%s\n",root->item.petname,root->item.petkind); inorder(root->right); // getch(); } } //前序遍历先根再左再右 static void preorder(Node *root) { if(root!=NULL) { printf("%s---%s\n",root->item.petname,root->item.petkind); preorder(root->left); preorder(root->right); } } //后序遍历，先左，再右，再根 static void postorder(Node *root) { if(root!=NULL) { postorder(root->left); postorder(root->right); printf("%s---%s\n",root->item.petname,root->item.petkind); } } void Traversal(Tree *t) { if(t!=NULL) { //postorder(t->root); inorder(t->root); //preorder(t->root); } } static void DeleteNode(Node **ptr ) { Node *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 { temp=(*ptr)->left; while(temp->right!=NULL) temp=temp->right; temp->right=(*ptr)->right; temp=*ptr; *ptr=(*ptr)->left; free(temp); } } int DelItem(Tree *t,const Item *p) { Pair look; look=SearchTree(t,p); // printf("dd"); if(look.self==NULL) return 0; if(look.parent==NULL)//根节点 DeleteNode(&t->root); else if(look.parent->left==look.self)//左子节点 DeleteNode(&look.self); //DeleteNode(&look.parent->left); else DeleteNode(&look.parent->right); t->size--; return 1; }