#include<stdio.h>
#include<string.h>
#include<malloc.h>
#include<math.h>
struct Ttree
 {
  char data[20];
  double weight;
  double num;  //一篇文獻中的某一索引詞出現的次數
  double max; //一篇文獻的總字數
  double n;  //索引詞出現在幾個文檔中
  struct Ttree *lchild;   //左兒子
  struct Ttree *rchild;   //右兒子
  };
  struct Ttree *rootW=NULL;
double MF=6;
 FILE *fp=fopen("D:\\mm.txt","w");
Ttree *createTtree(Ttree *root,FILE *fp){
  int i=0,t=0;
  struct Ttree *p,*q;  //定義中間指針變量
  char ch;
  p=(Ttree*)malloc(sizeof(Ttree));  //申請新的存儲空間
  p->data[0]='\0';
  if(fp==NULL)
    {
    printf("\nCannot open file strike any key exit!");
     return NULL;
    }
  ch=fgetc(fp);
  while((ch!=EOF)&&(t==0))
  {    if((ch>='a'&&ch<='z')||(ch>='A'&&ch<='Z')){
          if(ch<='Z') ch=ch+32;
           p->data[i]=ch;
           i++;
          }
       else{ if(p->data[0]=='\0'){ch=fgetc(fp);continue;}
           p->data[i]='\0';
           p->max++;
           p->n=1;
           p->num=1;
           i=0;
           t=1;
           p->lchild=NULL;
           p->rchild=NULL;           //初始化頭節點的左右兒子為空指針
           root=p;
          }
       ch=fgetc(fp);
     }
    q=(Ttree*)malloc(sizeof(Ttree));
    q->data[0]='\0' ;
   while(ch!=EOF){
       if((ch>='a'&&ch<='z')||(ch>='A'&&ch<='Z')){
        if(ch<='Z') ch=ch+32;
           q->data[i]=ch;
           i++;
           ch=fgetc(fp);}
       else {
           if(q->data[0]=='\0'){ch=fgetc(fp);continue;}
           q->data[i]='\0';
           root->max++;
           q->n=1;
           q->num=1;
           i=0;
           q->lchild=NULL;
           q->rchild=NULL;              //初始化頭節點的左右兒子為空指針
           if(p==NULL)p=root;
           ch=fgetc(fp);
           while(p!=NULL)            //尋找待插入節點的位置
            {
              if(strcmp(q->data,p->data)<0){       //如果待插入的節點的值小于當前節點的值，
                  if(p->lchild==NULL)  // 且其左子樹為空
                    {p->lchild=q;        //  則插入
                    p=NULL;}             //并置當前節點為空，退出當前的while循環
                  else
                    p=p->lchild;
               }         // 否則繼續訪問其左子樹
              else if(strcmp(q->data,p->data)>0){                       //如果待插入的節點的值大于當前節點的值
                   if(p->rchild==NULL)     // 且其右子樹為空
                    {p->rchild=q;         //  則插入
                     p=NULL;}             //并置當前節點為空，退出當前的while循環
                   else
                     p=p->rchild;
              }                      // 否則繼續訪問其右子樹
             else {p->num++;p=NULL; }
           }  //while
           q=(Ttree*)malloc(sizeof(Ttree));
           q->data[0]='\0';
       } //else
     }//while
   return root;
}
/*二叉樹查找*/
 Ttree *SearchBinTtree(Ttree *rootx,Ttree *rooty){
    if(rootx==NULL) return NULL;
    if(strcmp(rootx->data,rooty->data)==0) {rooty->n++;return rootx;}
    if(strcmp(rootx->data,rooty->data)>0) return SearchBinTtree(rootx->lchild,rooty);
    return SearchBinTtree(rootx->rchild,rooty);
    }
 /*計算在詞出現在幾個文檔中*/
 void InMidThread(Ttree *rooty,Ttree *rootx){
    if(rooty==NULL) return;
    InMidThread(rooty->lchild,rootx); //中序遍歷二叉樹左子樹 ;
    SearchBinTtree(rootx,rooty);
    InMidThread(rooty->rchild,rootx); //中序遍歷二叉樹右子樹 ;
    }
 /*計算權值*/
void InThread(Ttree *root,Ttree *Mroot){
    if(root==NULL) return;
    InThread(root->lchild,Mroot); //中序遍歷二叉樹左子樹 ;
    root->weight=(root->num/Mroot->max)*log(MF/root->n);
    InThread(root->rchild,Mroot); //中序遍歷二叉樹右子樹 ;
    }
    
 //對權值進行排序
void weight(Ttree *root,Ttree *r,Ttree *p,Ttree *q){
    if(root==NULL) return;
    weight(root->lchild,r,p,q); //中序遍歷二叉樹左子樹 ;
    if(r==NULL)
         {p=(Ttree*)malloc(sizeof(Ttree));  //申請新的存儲空間
          p->data=root->data;
          p->weight=root->weight;
          p->num=root->num;
          p->n=root->n;
          p->lchild=NULL;
          p->rchild=NULL;           //初始化頭節點的左右兒子為空指針
          rootW=p;                              //指針rootW指向頭節點
          r=p;}
    else{
      q=(Ttree*)malloc(sizeof(Ttree));
      q->data=root->data;
      q->weight=root->weight;
      q->num=root->num;
      q->n=root->n;
      q->lchild=NULL;
      q->rchild=NULL;       //初始化頭節點的左右兒子為空指針
      if(p==NULL) p=rootW;       //如果要有新節點插入則，p重新指向根節點，因為 每次比較都要從根節點開始
      while(p!=NULL)            //尋找待插入節點的位置
       {
        if(q->weight>p->weight){       //如果待插入的節點的值小于當前節點的值，
              if(p->lchild==NULL)  // 且其左子樹為空
                {p->lchild=q;        //  則插入
                 p=NULL;}             //并置當前節點為空，退出當前的while循環
              else
              p=p->lchild;}         // 否則繼續訪問其左子樹
       else{                       //如果待插入的節點的值大于當前節點的值
           if(p->rchild==NULL)     // 且其右子樹為空
             {p->rchild=q;         //  則插入
             p=NULL;}             //并置當前節點為空，退出當前的while循環
           else
             p=p->rchild;}        // 否則繼續訪問其右子樹
         }//while
       } //else
      weight(root->rchild,r,p,q);
     }
//輸出權值
 void ThreadWeight(Ttree *root){
    if(root==NULL) return;
    ThreadWeight(root->lchild); //中序遍歷二叉樹左子樹 ;
    fprintf(fp,"%s\t%f\t%f\t%f\t\n",root->data,root->weight,root->num,root->n);
    ThreadWeight(root->rchild); //中序遍歷二叉樹右子樹 ;
    }
void main(){
FILE *fp1,*fp2,*fp3,*fp4,*fp5,*fp6;
Ttree *root1,*root2,*root3,*root4,*root5,*root6,*r=NULL,*p,*q;
fp1=fopen("d:\\p1.txt","r");
root1=createTtree(root1,fp1);
fclose(fp1);
fp2=fopen("d:\\p2.txt","r");
root2=createTtree(root2,fp2);
fclose(fp2);
fp3=fopen("d:\\p3.txt","r");
root3=createTtree(root3,fp3);
fclose(fp3);
fp4=fopen("d:\\p4.txt","r");
root4=createTtree(root4,fp4);
fclose(fp4);
fp5=fopen("d:\\p5.txt","r");
root5=createTtree(root5,fp5);
fclose(fp5);
fp6=fopen("d:\\p6.txt","r");
root6=createTtree(root6,fp6);
fclose(fp6);
InMidThread(root1,root2);
InMidThread(root1,root3);
InMidThread(root1,root4);
InMidThread(root1,root5);
InMidThread(root1,root6);
InMidThread(root2,root1);
InMidThread(root2,root3);
InMidThread(root2,root4);
InMidThread(root2,root5);
InMidThread(root2,root6);
InMidThread(root3,root1);
InMidThread(root3,root2);
InMidThread(root3,root4);
InMidThread(root3,root5);
InMidThread(root3,root6);
InMidThread(root4,root1);
InMidThread(root4,root2);
InMidThread(root4,root3);
InMidThread(root4,root5);
InMidThread(root4,root6);
InMidThread(root5,root1);
InMidThread(root5,root2);
InMidThread(root5,root3);
InMidThread(root5,root4);
InMidThread(root5,root6);
InMidThread(root6,root1);
InMidThread(root6,root2);
InMidThread(root6,root3);
InMidThread(root6,root4);
InMidThread(root6,root5);
fprintf(fp,"第1篇文檔\n");
InThread(root1,root1);
weight(root1,r,p,q);
ThreadWeight(rootW);
fprintf(fp,"第2篇文檔\n");
InThread(root2,root2);
weight(root2,r,p,q);
ThreadWeight(rootW);
fprintf(fp,"第3篇文檔\n");
InThread(root3,root3);
weight(root3,r,p,q);
ThreadWeight(rootW);
fprintf(fp,"第4篇文檔\n");
InThread(root4,root4);
weight(root4,r,p,q);
ThreadWeight(rootW);
fprintf(fp,"第5篇文檔\n");
InThread(root5,root5);
weight(root5,r,p,q);
ThreadWeight(rootW);
fprintf(fp,"第6篇文檔\n");
InThread(root6,root6);
weight(root6,r,p,q);
ThreadWeight(rootW);
}