抽象数据类型（ADT）--树的实现
时间：2010-08-01 来源：chengbin_liu
/* ************************************************************************
* Filename: tree.h
* Description: chengbin_liu
* Version: 1.0
* Created: 2010年08月01日 15时53分14秒
* Revision: none
* Compiler: gcc
* Author: YOUR NAME (),
* Company:
* ************************************************************************/ #ifndef _TREE_H_
#define _TREE_H_ #include <stdlib.h>
#include <stdio.h> #define MAX 10
typedef struct item
{
char petname[20];
char petkind[20];
}Item; typedef struct node
{
Item item;
struct node *left;
struct node *right;
}Node; typedef struct tree
{
Node *root;
int size;
}Tree; void InitializeTree(Tree *ptree);//初始化空树
bool TreeIsFull(const Tree *ptree);//确定树是否已满
bool TreeIsEmpty(const Tree *ptree);//确定树是否为空
int TreeItemCount(const Tree *ptree);//确定树中项目的个数
bool AddItem(const Item *pi,Tree *ptree);//向树中添加一个项目
bool findTree(const Item *pi,const Tree *ptree);//在树中查找项目
bool DelTree(const Item *pi,Tree *ptree);//从树中删除一个项目
void Traverse(const Tree *ptree,void (*fun)(Item item));//把一个函数作用于书中每一个项目
void DeleteAll(Tree *ptree);//从树中删除所有节点 #endif
//======================================================================= /* ************************************************************************
* Filename: tree.c
* Description: chengbin_liu
* Version: 1.0
* Created: 2010年08月01日 16时16分26秒
* Revision: none
* Compiler: gcc
* Author: YOUR NAME (),
* Company:
* ************************************************************************/ #include "tree.h" typedef struct pair
{
Node *parent;
Node *child;
}Pair; //static function
static Node *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(Node *new_node,Node *root);
static void Inorder(const Node *root,void (*fun)(Item item));
static Pair SeekItem(const Item *pi,const Tree *ptree);
static void DeleteNode(Node **ptr);
static void DeleteAllNode(Node *ptr);
//================================================================
void InitializeTree(Tree *ptree)
{
ptree->root=NULL;
ptree->size=0;
}
//=================================================================
bool TreeIsEmpty(const Tree *ptree)
{
if(ptree->root==NULL)
return ture;
else
return false;
}
//=================================================================
bool TreeIsFull(const Tree *ptree)
{
if(ptree->size==MAX)
return true;
else
return false;
}
//=================================================================
int TreeItemCount(const Tree *ptree)
{
return ptree->size;
}
//=================================================================
bool AddItem(const Item *pi,Tree *ptree)
{
Node *new_node;
if(TreeIsFull(ptree))
{
fprintf(stderr,"Tree is full!\n");
return false;
}
if(SeekItem(pi,ptree).child !=NULL)
{
fprintf(stderr,"attemped 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 findTree(const Item *pi,const Tree *ptree)
{
return (SeekItem(pi,ptree).child==NULL)?false:true;
}
//===================================================================
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--;
return true;
}
//===================================================================
void Traverse(const Tree *ptree,void (*fun)(Item item))
{
if(ptree!=NULL)
InOrder(ptree->root,fun);
}
//==================================================================
void DeleteAll(Tree *ptree)
{
if(ptree!=NULL)
DeleteAllNode(ptree->root);
ptree->root=NULL;
ptree->size=0;
}
//====================================================================
static void InOrder(const Node *root,void (*fun)(Item item))
{
if(root!=NULL)
{
InOrder(root->left,fun);
(*fun)(root->item);
InOrder(root->right,fun);
}
}
//=====================================================================
static void DeleteAllNode(Node *root)
{
Node *pright;
if(root!=NULL)
{
pright=root->left;
DeleteAllNode(root->left);
free(root);
DeleteAllNode(pright);
}
}
//=====================================================================
static void AddNode(Node *new_node,Node *root)
{
if(ToLeft(&new_node->item,&root->item))
{
if(root->left==NULL)
root->right=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)
{
int comp1;
if((comp1=strcmp(i1->petname,i2->petname))<0)
return true;
else
if(comp1==0 && strcmp(i1->petkind,i2->petkind)<0)
return true;
else
return false;
}
//===================================================================
static bool ToRight(Item *i1,const Item *i2)
{
int comp1;
if((comp1=strcmp(i1->petname,i2->petname))>0)
return true;
else
if(comp1==0 && strcmp(i1->petkind,i2->petkind)>0)
return true;
else
return false;
}
//==================================================================
static Node *MakeNode(const Item *pi)
{
Node *new_node;
new_node=(Node *)malloc(sizeof(Node));
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(Node **ptr)
{
Node *temp;
puts((*ptr)->item.petname);
if((*ptr)->left==NULL)
{
temp=*ptr;
*ptr=(*ptr)->right;
free(temp);
}
else
if((*pr)->right==NULL)
{
temp=*ptr;
*ptr=(*ptr)->left;
free(temp);
}
else
{
for(temp=(*ptr)->left;temp->right!=NULL;tmep=temp->right)
continue;
temp->right=(*ptr)->right;
temp=*ptr;
*ptr=(*ptr)->left;
free(temp);
}
}
//=====================================================================:wq
* Filename: tree.h
* Description: chengbin_liu
* Version: 1.0
* Created: 2010年08月01日 15时53分14秒
* Revision: none
* Compiler: gcc
* Author: YOUR NAME (),
* Company:
* ************************************************************************/ #ifndef _TREE_H_
#define _TREE_H_ #include <stdlib.h>
#include <stdio.h> #define MAX 10
typedef struct item
{
char petname[20];
char petkind[20];
}Item; typedef struct node
{
Item item;
struct node *left;
struct node *right;
}Node; typedef struct tree
{
Node *root;
int size;
}Tree; void InitializeTree(Tree *ptree);//初始化空树
bool TreeIsFull(const Tree *ptree);//确定树是否已满
bool TreeIsEmpty(const Tree *ptree);//确定树是否为空
int TreeItemCount(const Tree *ptree);//确定树中项目的个数
bool AddItem(const Item *pi,Tree *ptree);//向树中添加一个项目
bool findTree(const Item *pi,const Tree *ptree);//在树中查找项目
bool DelTree(const Item *pi,Tree *ptree);//从树中删除一个项目
void Traverse(const Tree *ptree,void (*fun)(Item item));//把一个函数作用于书中每一个项目
void DeleteAll(Tree *ptree);//从树中删除所有节点 #endif
//======================================================================= /* ************************************************************************
* Filename: tree.c
* Description: chengbin_liu
* Version: 1.0
* Created: 2010年08月01日 16时16分26秒
* Revision: none
* Compiler: gcc
* Author: YOUR NAME (),
* Company:
* ************************************************************************/ #include "tree.h" typedef struct pair
{
Node *parent;
Node *child;
}Pair; //static function
static Node *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(Node *new_node,Node *root);
static void Inorder(const Node *root,void (*fun)(Item item));
static Pair SeekItem(const Item *pi,const Tree *ptree);
static void DeleteNode(Node **ptr);
static void DeleteAllNode(Node *ptr);
//================================================================
void InitializeTree(Tree *ptree)
{
ptree->root=NULL;
ptree->size=0;
}
//=================================================================
bool TreeIsEmpty(const Tree *ptree)
{
if(ptree->root==NULL)
return ture;
else
return false;
}
//=================================================================
bool TreeIsFull(const Tree *ptree)
{
if(ptree->size==MAX)
return true;
else
return false;
}
//=================================================================
int TreeItemCount(const Tree *ptree)
{
return ptree->size;
}
//=================================================================
bool AddItem(const Item *pi,Tree *ptree)
{
Node *new_node;
if(TreeIsFull(ptree))
{
fprintf(stderr,"Tree is full!\n");
return false;
}
if(SeekItem(pi,ptree).child !=NULL)
{
fprintf(stderr,"attemped 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 findTree(const Item *pi,const Tree *ptree)
{
return (SeekItem(pi,ptree).child==NULL)?false:true;
}
//===================================================================
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--;
return true;
}
//===================================================================
void Traverse(const Tree *ptree,void (*fun)(Item item))
{
if(ptree!=NULL)
InOrder(ptree->root,fun);
}
//==================================================================
void DeleteAll(Tree *ptree)
{
if(ptree!=NULL)
DeleteAllNode(ptree->root);
ptree->root=NULL;
ptree->size=0;
}
//====================================================================
static void InOrder(const Node *root,void (*fun)(Item item))
{
if(root!=NULL)
{
InOrder(root->left,fun);
(*fun)(root->item);
InOrder(root->right,fun);
}
}
//=====================================================================
static void DeleteAllNode(Node *root)
{
Node *pright;
if(root!=NULL)
{
pright=root->left;
DeleteAllNode(root->left);
free(root);
DeleteAllNode(pright);
}
}
//=====================================================================
static void AddNode(Node *new_node,Node *root)
{
if(ToLeft(&new_node->item,&root->item))
{
if(root->left==NULL)
root->right=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)
{
int comp1;
if((comp1=strcmp(i1->petname,i2->petname))<0)
return true;
else
if(comp1==0 && strcmp(i1->petkind,i2->petkind)<0)
return true;
else
return false;
}
//===================================================================
static bool ToRight(Item *i1,const Item *i2)
{
int comp1;
if((comp1=strcmp(i1->petname,i2->petname))>0)
return true;
else
if(comp1==0 && strcmp(i1->petkind,i2->petkind)>0)
return true;
else
return false;
}
//==================================================================
static Node *MakeNode(const Item *pi)
{
Node *new_node;
new_node=(Node *)malloc(sizeof(Node));
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(Node **ptr)
{
Node *temp;
puts((*ptr)->item.petname);
if((*ptr)->left==NULL)
{
temp=*ptr;
*ptr=(*ptr)->right;
free(temp);
}
else
if((*pr)->right==NULL)
{
temp=*ptr;
*ptr=(*ptr)->left;
free(temp);
}
else
{
for(temp=(*ptr)->left;temp->right!=NULL;tmep=temp->right)
continue;
temp->right=(*ptr)->right;
temp=*ptr;
*ptr=(*ptr)->left;
free(temp);
}
}
//=====================================================================:wq
相关阅读 更多 +
