//* * * * * * * * * * * * * * * * * * * * * * * *
//*CHAPTER          :6  (6_3)                   *
//*PROGRAM          :靜態樹表的查找             *
//*CONTENT          :CreateSOSTree,Search       *
//* * * * * * * * * * * * * * * * * * * * * * * *
#include <dos.h>
#include <conio.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 30  //靜態樹表的記錄的最大個數
enum BOOL{False,True};
typedef struct  BiTNode       //定義二叉樹節點結構
{char  data;                  //數據域
 struct BiTNode *lchild,*rchild; //左右孩子指針域
}BiTNode,*BiTree,*SOSTree; 
typedef struct SSTable //定義有序表的結構
{char elem[MAXSIZE];   //關鍵字
 int weight[MAXSIZE];  //權值 
 int length;           //有序表的當前長度 
}SSTable;
void CreateSOSTree(SOSTree&,SSTable);    //構造一個次優查找樹
void SecondOptimal(BiTree &,SSTable,int sw[],int,int);
SOSTree Search(SOSTree,char); //在查找樹中查找一個記錄
void main()
{SOSTree T,p;
 SSTable ST;
 char ch,j='y';
 int i;
 textbackground(3);  //設定屏幕顏色
 textcolor(15);
 clrscr();
 //-------------------------程序說明-------------------------------
 printf("This program will show how to create a Nearly Optimal Search Tree\nand search a record in the Tree.\n");
 printf("First you input the number of the record:\nfor example:5\n");
 printf("Then you input the records(from small to big) and their weight: for example:\n");
 printf("A,1\nB,1\nC,2\nD,5\nE,3\n");
 printf("A NOSTree will be created and you can search a record.\n");   
 //----------------------------------------------------------------
 printf("Please input the number of the Record:\n");
 scanf("%d",&ST.length); //輸入有序表的長度
 printf("Please input the Records and their weights:\nFormat:Record,weight,for example A,2\n");
 for(i=1;i<=ST.length;i++)
   scanf(" %c,%d",&ST.elem[i],&ST.weight[i]); //從小到大依次輸入各個記錄及其權值
 CreateSOSTree(T,ST);       //構造一顆次優查找樹
 getchar();
 while(j!='N'&&j!='n')
    {printf("Please input the char you want to find:");
     scanf(" %c",&ch); //輸入要查找的記錄的關鍵字
     p=Search(T,ch);   //查找關鍵字為ch的記錄
     if(p==NULL) printf("%c isn't existed!\n",ch); //沒找到
     else printf("%c has been found.\n",ch);     //成功找到
     printf("Do you want to search next one?(Y/N)");
     scanf(" %c",&j);
    }
 printf("The program is over!\n");
}
void CreateSOSTree(SOSTree &T,SSTable ST)
{//由有序表ST構造一顆次優查找樹T,ST的數據元素含有權域weight
 int sw[MAXSIZE];
 int i;
 if(ST.length==0) T=NULL;
 else
   {sw[0]=0;
    for(i=1;i<=ST.length;i++) sw[i]=sw[i-1]+ST.weight[i]; 
       //按照由有敘表ST中各數據元素的weight求累計權值表sw
    SecondOptimal(T,ST,sw,1,ST.length);
   }
}
void SecondOptimal(SOSTree &T,SSTable ST,int sw[],int low,int high)
{//由有序表ST及其累計權值表sw(sw[0]=0)遞歸構造次優查找樹T。
 int i,j,min,dw;
 i=low;
 min=abs(sw[high]-sw[low]);
 dw=sw[high]+sw[low-1];
 for(j=low+1;j<=high;j++)     //選擇最小的△P值
   if(abs(dw-sw[j]-sw[j-1])<min)
     {i=j;min=abs(dw-sw[j]-sw[j-1]);}
 T=(SOSTree)malloc(sizeof(BiTNode));
 T->data=ST.elem[i];        //生成結點
 if(i==low) T->lchild=NULL; //左子樹空
 else SecondOptimal(T->lchild,ST,sw,low,i-1);  //構造左子樹
 if(i==high) T->rchild=NULL; //右子樹空
 else SecondOptimal(T->rchild,ST,sw,i+1,high); //構造右子樹 
}
SOSTree Search(SOSTree T,char ch)
{//在次優查找樹中查找關鍵字為ch的記錄，找到則返回其地址指針，否則返回NULL
 SOSTree p;
 if(T==NULL) return NULL; //根結點為空，返回NULL
 for(p=T;p->data!=ch&&p!=NULL;) 
    if(p->data>ch) p=p->lchild; //若當前結點的關鍵字比ch大，則在其左子樹中繼續查找
    else p=p->rchild;           //若當前結點的關鍵字比ch小，則在其右子樹中繼續查找
 return p;
}