抽象数据类型（ADT）--树的实现

/* ************************************************************************
 *       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
#include

#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