bst.c

这是用C实现的二叉树的算法程序

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define INF "in.txt"
typedef struct Node
{
 char *word;
 int count;
 struct Node *left,*right;

 }Node,*BiTree;

 int searchBst(BiTree T,char *keyword,BiTree *p)
 {
  int cmpres=0;
  BiTree ptr;
  *p=NULL;ptr=T;
  while(ptr)
  {
   cmpres=strcmp(ptr->word,keyword);
   if(cmpres==0)
   {
    *p=ptr;return 0;
    }
   else
   {
    *p=ptr;
    ptr=cmpres>0?ptr->left:ptr->right;
    }
   }
   return -1;
  }

  int insertBst(BiTree *t,char *keyword)
   {
    BiTree s,p;
    if(searchBst(*t,keyword,&p)==-1)
    {
     s=(Node*)malloc(sizeof(Node));
     if(!s)
     {
      printf("failure!\n");
      return -1;
      }
      s->word=(char*)malloc(strlen(keyword));
      strcpy(s->word,keyword);
      s->left=NULL;s->right=NULL;s->count=1;
      if(p==NULL) *t=s;
      else if(strcmp(p->word,keyword)<0)
      p->right=s;
      else p->left=s;
      }
     else p->count++;
     return 0;
    }

    void InOrder(BiTree root)
    {
     if(root)
     {
      InOrder(root->left);
      printf("%s(%d)\n",root->word,root->count);
      InOrder(root->right);
      }
    }


  void main(void)

  {
   char ch,*word,buffer[100];
   FILE *fin;
   BiTree root=NULL;
   int i=0,tag;
   fin=fopen(INF,"r");
   if(!fin)
   {
    printf("open file %s error!\n",INF);
    return;
    }
   while(!feof(fin))
   {
   ch=fgetc(fin);
   if((ch>='a'&&ch<='z')||(ch>='A'&&ch<='Z'))
   {
    buffer[i++]=ch;tag=1;
    }
    else if(tag)
    {
     buffer[i]='\0';
     word=(char*)malloc(strlen(buffer));
     strcpy(word,buffer);
     if(insertBst(&root,word)==-1)
     return;
     i=0;tag=0;
     }

  }
  fclose(fin);
  InOrder(root);
 }