fourth.cpp

二叉排序树（Binary Sort Tree--BST）或者是一棵空树；或者是具有下列性质的二叉树： ⑴ 若左子树不空

#include<string.h>
#include<iostream>
#include<fstream>
using namespace std;




typedef struct BiTNode{
	char data[10];
	struct BiTNode *lchild,*rchild; 
	int n;
}BiTNode,*BiTree;


int length=0;
BiTree head=NULL;


void transfer(char *w){
	char *p;
	for(p=w;p<w+strlen(w);p++)
		if('A'<=*p&&*p<='Z')
			*p=*p+32;
		else if(*p==','||*p=='.')
			*p='\0';
			return ;
}

void insertLeaf(const char *w,BiTNode* &child){
	child=new BiTNode;
	strcpy(child->data,w);
	child->lchild=NULL;
	child->rchild=NULL;
	child->n=1;
	length++;

}


void insert(const char *word){
	if(head==NULL)
		insertLeaf(word,head);
	
	else{
		BiTNode *parent;
			parent=head;
		BiTNode *child;
			child=head;
		while(child!=NULL){
			parent=child;
			if(strcmp(word,child->data)<0)
				child=child->lchild;
			else if(strcmp(word,child->data)>0)
				child=child->rchild;
			else if(strcmp(word,child->data)==0)
			{
				child->n++;
				return;
			}

				
		}
		if(strcmp(word,parent->data)<0)
			insertLeaf(word,parent->lchild);
		if(strcmp(word,parent->data)>0)
			insertLeaf(word,parent->rchild);
		
		}
}


void Visit(BiTNode *bt){
	cout<<bt->data<<"               "<<bt->n<<endl;
	return ;
}
void InOder(BiTree bt){

	 if(bt==NULL)
		 return;
	 InOder(bt->lchild);
	 Visit(bt);
	 InOder(bt->rchild);
 }




int main(){	
	ifstream input;
	char name[10];
	cout<<"input file name:";
	cin>>name;
	input.open(name);

	
	char word[12];
			
	while(input>>word){		
		transfer(word);
		insert(word);		
	}

	cout<<"Word                Count"<<endl;
	cout<<"---------------------------"<<endl;
	InOder(head);
	cout<<"The file contains "<<length<<" distinct words."<<endl;			

	input.close();
	return 0;
}