blinktree.cpp

华南华范大学计机实验2二叉树实验,不含实验报告

//class BLinkTree的实现
#include <iostream>
#include <fstream>
#include <string>
#include "BLinkTree.h"
#include <queue>
#include <stack>
using namespace std;


BLinkTree::BLinkTree(void){ 
	head=NULL;
	number=0;
}

void BLinkTree::Clear(void){ 
	Clear_post(NULL,1);
	head=NULL;
}
void BLinkTree::Clear_post(BTreeNode *t,int first){
	BTreeNode *current;
	if(first){
		current=head;
		first=0;
	}
	else current=t;
	if(current!=NULL){
		Clear_post(current->lchild,first);
		Clear_post(current->rchild,first);
		delete current;
		current=NULL;
		number--;
	}
}


void BLinkTree::Insert(void){ 
	BTreeNode *ptr,*current;
	stack(int)s;
	ptr=new BTreeNode;     //读入信息，建立新结点，用指针ptr指向新结点
	cout<<"请输入要添加的学生信息:"<<endl;
    cin>>ptr->data;
	if(head==NULL){    //特殊情况:如果二叉树为空
	    head==ptr;
		number++;
		return ;
	}
	for(int i=(number+1)/2;i>1;i=i/2)s.push(i);     //用双亲编号公式,算出新结点到根
	                                                //的各个双亲结点的编号并用栈保存
	current=head;      //parent从根开始，顺着栈里的双亲结点编号往下走
    while(!s.empty()){
		s.pop();
		if(i%2==1)current=current->rchild;
		else current=current->lchild;
	}        //经过以上循环，parent应指向新结点的双亲结点
	if((number+1%2==1) current->rchild=ptr;
	else current->lchild=ptr;
	number++;
}
BTreeNode* BLinkTree::Locate(int no[20])   //非递归中序遍历按学号查找学生记录
{
	BTreeNode *current;
	stack <BTreeNode *>s;
	current=head;
	while((!s.empty()||current!=NULL)){
		while(current!=NULL){
			s.push(current);
			current=current->lchild;
		}
		if(!s.empty()){
			current=s.top();
			s.pop();
			if(!strcmp(current->data.no,no))return current;
			current=current->rchild;
		}
	}
	return NULL;
}


void BLinkTree::Delete(void){ 
	int No[20];
	cout<<"请输入要删除的学生学号:";
	cin>>No;
	BTreeNode *ptr;
	ptr=Locate(No);
	if(ptr!=NULL){
		strcpy(ptr->data.no,"deleted");
		cout<<"\n删除成功!\n\n\n";
		return;
	}
	cout<<"\n删除失败!\n\n\n";
	return;
}

void BLinkTree::Load(void){     //文件中的记录按层次遍历序列建立完全二叉树
		char load_name[50];
	ifstream file;
	cout<<"1.打开“student.dat”\n2.打开其他保存的文件\n";
	int x; cout<<"请选择:"; cin>>x;
	if (x==1)
		file.open("student.dat",ios::in|ios::binary);
	else{
		cout<<"请输入文件名:";
		cin>>load_name;
		file.open(load_name,ios::in|ios::binary);
	}
	if(!file){
		int sc;
		cout<<endl;
		cout<<"文件打开失败,是否重新读取?\n";
		cout<<"1. 是  2. 否\n请选择:";
		cin>>sc;
		if(sc==1) Load();
	}
	else
	{
		queue <BTreeNode *>st_ptr;
		DataType st;
		BTreeNode *current;
		BTreeNode *ptr;
		while (file.read((char*)&st,sizeof st))
		{
			if(st_ptr.empty())current=NULL;
			else current=st_ptr.front();
			ptr=new BTreeNode;		
            ptr->data=st; 
	    	st_ptr.push(ptr);
	    	if (current==NULL){head=ptr;number++;}
			else
			{
				current->lchild=ptr;number++;
				if(file.read((char*)&st,sizeof st)) 
				{
					ptr=new BTreeNode;		
			    	ptr->data=st;   
		            st_ptr.push(ptr);
		        	current->rchild=ptr;number++;
		        	st_ptr.pop();
				}
			}
		}
		file.close(); 
	}
}

void BLinkTree::Save(void){       //按层次队列把完全二叉树中的结点依次写入文件，被删除的结点不写入文件
		char save_name[50];
	ofstream file;
	cout<<"1.保存在“student.dat”文件里面\n2.保存为新文件\n";
	int x; cout<<"请选择:"; cin>>x;
	if (x==1)
		file.open("学生健康信息.dat",ios::out|ios::binary);
	else{
		cout<<"请输入保存文件名:";
		cin>>save_name;
		file.open(save_name,ios::out|ios::binary);
	}
	queue<BTreeNode *>st_ptr;
	BTreeNode *ptr;
	DataType st;
	if(head!=NULL) st_ptr.push(head);
	while(!st_ptr.empty()){
		ptr=st_ptr.front();
		if(strcmp(ptr->data.no, "deleted")){
			st=ptr->data;
		    file.write((char *) &st, sizeof(st));
		}
		st_ptr.pop();
		if(ptr->lchild!=NULL) st_ptr.push(ptr->lchild);
		if(ptr->rchild!=NULL) st_ptr.push(ptr->rchild);
	}
	cout<<endl;
	cout<<"保存成功!\n\n";
	cout<<endl;
}

void BLinkTree::SearchNo(void){
	//按前序遍历次序查找，被删除的结点不比较
	int no[20];
	cout<<"请输入要查询的学生学号:";
	cin>>No;
	BTreeNode *ptr;
	ptr=Locate(No);
	if(ptr!=NULL)
	{
		cout<<"\n查找成功,该学生的信息如下:\n\n";
		cout<<ptr->data;
		cout<<"\n\n";
	}
	else cout<<"\n该学号的记录不存在!\n\n\n";
}

void BLinkTree::Display(void){    //按前序遍历输出  
		if (head==NULL)return;
	Display_pre(head);
}
void BLinkTree::Display_pre(BTreeNode *t)
{
	if(strcmp(t->data.no,"deleted"))
	{

		cout<<t->data;
	    cout<<endl;
	}
	if(t->lchild!=NULL)
		Display_pre(t->lchild);
	if(t->rchild!=NULL)
		Display_pre(t->rchild);
}
ostream& operator<<(ostream& os,DataType& st)
{
	if (os==cout)
		os<<"学生姓名:"<<st.name<< "; 学号:"<<st.no<<"; 生日:"
		<<st.birthdate<<"; 性别:"<<st.sex<<"; 健康情况:"
		<<st.health<<"."<<endl ;
	else
		os <<st.name <<endl<<st.no<<endl<<st.birthdate<<endl
		<<st.sex<<endl<<st.health<<endl;
	return os;
}
istream& operator>>(istream& is,DataType& st)
{
	if (is==cin) {
	cout<<"输入姓名(char[20]):";
	is>>st.name; 
	cout<<"输入学号(int[20]):";
	is>>st.no;
	cout<<"输入生日(如:870101):";
	is>>st.birthdate;
	cout<<"输入性别(male/female):";
	is>>st.sex;
	cout<<"输入健康情况(如:bad/ordinary):";
	is>>st.health;
	}
	else {
		
		is>>st.name;
		is>>st.no;
		is>>st.birthdate;
		is>>st.sex;
		is>>st.health; 
	}
	return is;
}